Решение задач линейной оптимизации с использованием MathCad и Excel. Бундаев В.В. - 8 стр.

                                 15                                                                     16


при дополнительных переменных х3, х4 и х5 равны +1, то оче-                             0,5 x1 + x 2 + 5 x3 = 60,
видно, что набор х1 = х2 = 0, х3 = 12, х4 = 10, х5 = 21 образуют
начальное базисное допустимое решение. Эти значения указаны                            0,15 x1 − 0,5 x3 + x 4 = 4,                   (5.3)
в столбце С таблицы. Коэффициенты при неизвестных хi, i =                              0,15 x1 − 1,5 x3 + x5 = 3,
1,2,3,4,5 введены в ячейки блока D2:H4, а коэффициенты целе-                        − 25 x1 + 400 x3 = − F + 4800
вой функции (-F) - в строку 5.
    Поскольку функция цели (-F) в (5.2) выражена через неба-               Коэффициенты системы (5.3) вычисляются в ячейках блока
зисные переменные х1 и х2, а коэффициенты при х1 и х2 отрица-          A6:H10 , составляющей вторую симплекс-таблицу (рис. 5.2).
тельны, то любое изменение неотрицательных переменных при-             При этом в ячейку C7 введена следующая формула: =C$2/$E$2,
водит к убыванию (-F). Для простоты будем увеличивать пере-            которая скопирована в ячейки D7:H7 этой же строки. В ячейку
менную с большим по модулю коэффициентом, т.е. х2. Однако              С8 - =C3-C$2/$E$2*$E3 (или =C3-C$7*$E3). Формула скопиро-
такое увеличение х2 будет сопровождаться изменением пере-              вана в ячейки блока C8:H8.
менных х3 и х4 , так как они связаны соотношениями (5.1). Сле-             Система уравнений (5.3) также является канонической фор-
довательно, х2 не может увеличиваться неограниченно. Из пер-           мой исходной задачи (3.1) – (3.3), но уже для базиса х2 , х4 и х5.
вого равенства системы (5.1) следует, что х3 = 0 при х2 = 12/0,2 =     Теперь эти переменные х2 , х4 и х5 составляют базисное допус-
60, из второго – х4 = 0 при х4 = 0 при х2 = 10/0,1 = 100, а из         тимое решение, а переменные х1 и х3 стали небазисными.
третьего – х5 = 0 при х2 =21/0,3 = 70. Так как х3, х4 и х5 неотрица-       Отметим, что дальнейшего уменьшения функции (-F) можно
тельны, то мы не можем увеличивать х2 до значения более, чем           добиться только за счет увеличения х1 , поскольку коэффициент
60, т.е.                                                               при х1 в выражении для функции цели в (5.3) отрицательный.
                                                                       Найдем пределы изменения х1 из условия неотрицательности х2 ,
                            12  10        21 
             max x 2 = min  ,       ,          = 60.                 х4 и х5. Из первого уравнения (5.3) следует, что х2 = 0 при х1 =
                            0,2 0,1       0,3                        60/0,5 =120, из второго уравнения (5.3) – х4 = 0 при х1 = 4/0,15 =
    Т.о, положительный наибольший элемент диапазона D2:H2              26,7 , из третьего уравнения (5.3) – х5 = 0 при х1 = 3/0,15 = 20.
находится в ячейке Е2. Следовательно, столбец Е – разрешаю-            Следовательно, переменную х1 нельзя увеличивать более, чем
щий столбец. Наименьшее отношение положительных свобод-                до 20, т.е.
ных членов ограничений (5.1) к положительным элементам это-                                      60           4        3 
го столбца соответствует элементу ячейки Е2, который и будет                       max x1 = min  ,               ,         = 20.
разрешающим элементом таблицы. Он обозначен в правом                                             0,5        0,15     0,15 
верхнем углу ячейки треугольником.                                         Т.о, положительный наибольший элемент диапазона D9:H9
    Разделив первое ограничение на коэффициент 0,2 при х2 ,            находится в ячейке D9. Следовательно, столбец D – разрешаю-
получим 0,5·х1 + х2 + 5·х3 = 60. Предварительно умножив это            щий столбец. Наименьшее отношение положительных свобод-
преобразованное ограничение на соответствующие коэффициен-             ных членов ограничений (5.3) к положительным элементам это-
ты при х2 во 2-м, 3-м и 4-м равенствах системы (5.1) и, вычтя его      го столбца соответствует элементу ячейки D9, который и будет
из этих равенств, исключим переменную х2 отовсюду, кроме               разрешающим элементом таблицы. Он обозначен в правом
первого, куда она входит с коэффициентом +1, т.е.                      верхнем углу ячейки треугольником.
                                                                           Третье ограничение в (5.3) разделим на коэффициент при х1 ,
                                                                       равный 0,15 , и, умножив полученное равенство на соответст-