Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 90 стр.

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


                                                                      2u1 + u 2 + 6u 3 - u 4 - 9u 5 ® max
           3 x - 2 y ® max,
                                                                      u1 + u 2 + 7u 3 - 3u 4 - 7u 5 = 13,
           -x + 2 y ³ 2,
      а)                                                           б) u1 + 2u 2 + 13u 3 + 2u 4 -14u5 = 20,
           7 x + 10 y £ 28,
                                                                      u1 + 3u 2 + 20u 3 + 6u 4 - 23u 5 = 19,
           x ³ 0, y ³ 0.
                                                                      u1 ³ 0, u 2 ³ 0, u 3 ³ 0, u 4 ³ 0, u 5 ³ 0.

                    ìï      æ 1ö                                        üï
                     ïï   çç u ÷÷                                        ïï
      2. Пусть U = ïíu = çççL÷÷÷÷ Î R n ai , u £ bi , i = 1,L, m, m ³ nïý . Показать, что точка
                      ïï   çç n ÷÷                                        ïï
                       ï    è u ø÷                                         ï
                       îï                                                  þï
v Î U будет угловой для множества U тогда и только тогда, когда в ней

обращаются в точные равенства не менее чем n неравенств ai , u £ bi , i = 1,L, m ,

среди которых есть n линейно независимых.
      3.    Сформулировать             правило                   нахождения        разрешающего элемента
симплекс таблицы и критерий остановки счета в симплекс-методе.
      4.    Сформулировать             критерий                   неограниченности              решения             задачи
линейного        программирования                  на            минимум          симплекс-методом.                  Дать
геометрическую интерпретацию неограниченности решения в плоском случае.
                                                   æ 0ö÷
                                                   çç ÷
                                                    çç 0÷÷
                                                     çç ÷÷÷
      5. Показать, что точка                  v = çç1 ÷÷          является угловой для допустимого
                                                      çç ÷÷÷
                                                       çç 2÷÷
                                                        çç1 ÷÷
                                                         è ø÷

множества в следующей задаче линейного программирования:
                                  u1 + 2u 2 + u 3 + 3u 4 + u 5 ® max,
                                  u1 + u 2 + 2u 4 + u 5 = 5,
                                  u1 + u 2 + u 3 + 3u 4 + 2u 5 = 9,
                                  u 2 + u 3 + 2u 4 + u 5 = 6,
                                  u1 ³ 0, u 2 ³ 0, u 3 ³ 0, u 4 ³ 0, u 5 ³ 0.

    Начав       с    точки    v       как      с        начальной,             решить         задачу        линейного
программирования симплекс-методом.
      6. Построить начальную угловую точку и решить симплекс-методом
следующие задачи линейного программирования:



                                                            90