Математическое программирование (линейное программирование). Киселева Э.В - 56 стр.

на видов А, В и С). Так как х1*=5>0, то согласно второй теореме,        Пример 7.8. Провести анализ дефицитности ресурсов (при-
ограничение у1 + у3 ≥ 4 в двойственной задаче ее оптимальным        мер 7.1), решив исходную задачу симплекс-методом.
                                                                        Решение. Напомним математическую модель примера 7.1:
планом должно обратиться в равенство, т.е. у1* + у 3* = 4. Анало-                       Z = x1 + 4 x2 + 2 x3 + 5 x4 → max
гично из того, что x*2 = 1 > 0 , следует у2*+2у3*=7. Итак, имеем    при ограничениях:
систему уравнений:                                                                        ⎧ 2 x1 + x2 + 3x3 + x4 ≤ 260,
                              ⎧⎪ y1* + y 3* = 4,                                          ⎪
                               ⎨ *                                                        ⎨ x1 + 2 x2 + x3 + 2 x4 ≤ 400,
                               ⎪⎩ y 2 + 2 y 3* = 7.                                       ⎪ 2 x + x + 2 x ≤ 240,
                                                                                          ⎩       1    3     4
    Кроме того, в оптимальном плане Х * = (5, 1) Т первое и
                                                                                                   x j ≥ 0 ( j = 1,4).
третье ограничения прямой задачи выполняются как равенства
(5=5; 5+2·1=7). Это означает, что глина видов А и С используется        Для решения симплекс-методом запишем исходную задачу в
полностью, являясь дефицитной. Дальнейшее увеличение запасов        виде:
глины видов А и С целесообразно. Если же ресурс расходуется не                        Z1 = − x1 − 4 x2 − 2 x3 − 5 x4 → min
полностью, то он избыточен, его дальнейший рост не повлияет на      при ограничениях:
эффективность работы завода. Таким ресурсом является глина
                                                                                        ⎧ 2 x1 + x2 + 3x3 + x4 + x5 = 260,
вида В. Действительно, так как второе ограничение x2 ≤ 3 в оп-                          ⎪
                                                                                        ⎨ x1 + 2 x2 + x3 + 2 x4 + x6 = 400 ,
тимальном плане x*2 = 1 выполняется как строгое неравенство 1                           ⎪ 2 x + x + 2 x + x = 240,
< 3, то глина вида В избыточна, и согласно второй теореме двой-                         ⎩       1    3     4     7

ственности ее оценка равна нулю (у2*=0).                                                           x j ≥ 0 ( j = 1,7).
     Из системы находим
                                                                        Очевидно, что первоначальным опорным планом является
                                7           1
                             у = ;
                              *
                              3          у = .
                                         *
                                         1
                                                                    неотрицательное базисное решение:
                                2           2
    Получим                                                                          X = ( 0 , 0, 0, 0, 260, 400, 240 )T ≥ 0,
                                    1     7
                             Y * = ( , 0,   ).                      где x5, x6, x7 – базисные переменные, а х1=х2=х3=х4=0 – свободные
                                    2     2                         переменные. При этом Z(X)=0.
    Тогда                                                                Замечаем, что полученный опорный план не является опти-
                             1              7                       мальным, так как в функции цели Z, выраженной только через
                Wmin = 5 ⋅     + 3 ⋅ 0 + 7 ⋅ + 145 = 172 ,          свободные переменные, все коэффициенты отрицательны. При-
                             2              2
что совпадает с экстремальным значением функции W, уже най-         чем для получения нового опорного плана в базис можно ввести
денным с помощью первой теоремы двойственности.                     любую из свободных неизвестных: х1, х2, х3 или х4.
    Кроме того, замечаем, что глина вида С является более де-            Введем в базис х4. Следовательно, в симплекс-таблице (см.
                                                                    ниже) разрешающим становится четвертый столбец. Возникает
фицитной, чем глина вида А, так как у3* > y1* .                     вопрос, какая из базисных переменных х5, х6 или х7 перейдет в
                                   113                                                                      114