значения в каждой строке на значения опорной строки, начиная с резервного столбца и далее слева направо. Уходящая переменная соответствует наименьшему отношению в первом столбце с неравными отношениями.
в. Образовать новую опорную строку следующей таблицы: разделить каждое число в строке уходящей переменной на значения опорной строки. Введите эти значения в следующую таблицу в тех же самых позициях строки.
г. Вычислить новые значения для оставшихся строк ограничений: для каждой строки, умножьте значения в новой опорной строке на значение опорной строки ограничения, и вычтите результат, столбец за столбцом, из первоначальных значений строки. Введите их в новую таблицу на те же самые позиции, что и в первоначальной строке.
д. Вычислите значения для строк Z и C-Z .
е. Проверьте, есть ли в строке C-Z положительные значения; если есть, то повторите пункты 2а - 2е. Если нет, то мы получили оптимальное решение.
Задачи минимизации
Симплексный метод обрабатывает задачи минимизации практически тем же способом, что и задачи максимизации. Однако имеются некоторые различия. Это - потребность давать поправку на ограничения типа >, которые требуют введения как искусственных переменных, так и резервных переменных. Этот фактор обуславливает широкое применение ручных решений. Второе существенное различие - проверка на оптимум: решение оптимально, если строка C-Z не содержит отрицательных значений.
ПРИМЕР 3
Решите следующую задачу для количеств и xg, которые минимизируют затраты. Минимизировать: Z=]2xi+10x2 Ограничения: X]-i-4x2>8
Зх]-н2х2>6 х,,Х2>0
Решение:
1. Перепишем ограничения в нужной форме:
х. -н 4x2 > 8 становится х., -н 4X3 - Is., - OSg -н la., -н Оа = 8 Зх. -н 2x2 > 6 становится Эх., -н 2X3 - Osl - ISj + Оа -н lag = 6
2. Перепишем целевую функцию (коэффициенты в строке С): 12х -н 10x2 -I- Os + + 999а + 999а2
3. Вычислим значения для строк Z и C-Z.
| | | | | | | Количество |
| 1(999) | 4(999) | -1(999) | 0(999) | 1(999) | 0(999) | 8(999) |
| 3(999) | 2(999) | 0(999) | -1(999) | 0(999) | 1(999) | 6(999) |
| 3996 | 5994 | -999 | -999 | | | 13986 |
| -3984 | -5984 | | | | | |
4. Составим начальную таблицу. (Обратите внимание, что начальное решение содержит все искусственные переменные.)
999 999
| Переменные в решении | | | «1 | | | | Количество решения |
| | | | | | | | |
| | | | | | | | |
| | 3996 | 5994 | -999 | -999 | | | 13986 |
| | -3984 | -5984 | | | | | |
Найдем входящую переменную (самое большое отрицательное значение C-Z: столбец Xg) и уходящую переменную (меньшее из 8/4 = 2 и 6/2 = 3; следовательно, строка а.).
Разделим каждое число в уходящей строке на опорное значение (4, в данном случае), чтобы получить опорную строку второй таблицы:
1/4, 4/4=1, -1/4, 0/4, 1/4, 0/4, 8/4=2
Вычислим значения для других строк; а:
Количество
Текущее значение 3
-2 х(новый опорный ряд) -2/4 Новый ряд 10/4
8. Вычислим новую строку Z:
2 О -2 2/4 О +2/4
-10 16
-0/4 -2/4 -0/4 -4 -1
-2/4
| Затраты | | | | | | | Кол-во |
| | 10(1/4) | 10(1) | 10(-1/4) | 10(0) | 10(1/4) | 10(0) | 10(2) |
| | 999(10/4) | 999(0) | 999(2/4) | 999(-1) | 999(-2/4) | 999(1) | 999(2) |
| | 2500 | | | -999 | -497 | | 2018 |
9. Вычислим строку C-Z:
| | | «1 | | | |
| | | | | | |
| 2500 | | | -999 | -497 | |
| -2488 | | -497 | | 1496 | |
10. Составим вторую таблицу:
| | | | | | | | |
| Переменные в решении | | | | | | | Коли-честао |
| | | | | | | | |
| | 10/4 | | | | -2/4 | | |
| | 2500 | | | -999 | -497 | | 2018 |
| | -2488 | | -497 | | 1496 | | |
ill- Повторим процедуру:
а. Проверим оптимальность: если строка C-Z содержит отрицательные элементы - оптимум не достигнут.
б. Определим переменную ввода: наибольшее отрицательное значение в столбце х. I
в. Определим переменную выхода: 2/(1/4) = 8, 2/(10/4) = 0,8. Следовательно, i это--строка I
г. Найдем новое значение опорной строки, используя опорное значение 10/4 1
1 О 0,2 -0,4 -0,2 0,4 0,8
д. Определим значения для новой строки х:
О 1 -0,3 0,1 0,3 -0,1 1,8
е. Определим новые значения для строки Z;
Ряд Зат- Кол- раты X, Sj aj во
Xg 10 10(0) 10(1) 10(-0,3) 10(0,1) 10(0,3) 10(-0,1) 10(1,8)
X, 12 12(1) 12(0) 12(0,2) 12(-0,4) 12(-0,2) 12(0,4) 12(0,8)
Z 12 10 -0,6 -3,8 0,6 3,8 27.6
Ж. Определим значения для строки C-Z:
3. Составим следующую таблицу. Поскольку среди значений C-Z нет отрицательных, решение оптимально. Следовательно, х., = 0,8, х2 = 1,8 и минимальные затраты-27,60.
| | | | | | | | | |
| Переменные | | | | | | | Коли- | |
| в решении | | | | | | | чество | |
| | | | -0,3 | | | -0,1 | | |
| | | | | -0,4 | -0,2 | | | |
| | | | -0,6 | -3,8 | | | 27,6 | |
| | | | | | 998,4 | 995,2 | | |
| | | | | | | | | .r:i::s;5.o.:.v |
чнализ чувствительности
асто случается, что принимающий производственные решения руководитель хочет юлучить нечто большее, чем сиюминутное решение проблемы. Он может получить юльшую и многообразную пользу из анализа чувствительности решения. При подго-"овке задачи к решению методом линейного программирования, менеджер может давать субъективные оценки некоторым параметрам (например, коэффициентам огра-мчений, коэффициентам целевой функции и значениям правой части в уравнениях •граничений). Вполне естественно, что он хочет знать: насколько чувствительным яв-1яется оптимальное решение к изменениям в значении одного или нескольких таких параметров. Если решение относительно устойчиво к разумным изменениям, то ме-чеджер может чувствовать себя достаточно уверенно, осуществляя свои решения на трактике. Наоборот, если решение чувствительно к подобным изменениям, то менед-ер несомненно захочет получить более точную оценку подозрительных параметров.
Вторая возможная польза от анализа чувствительности касается специфических 1зменений в параметрах. Например, изменение цен может изменить коэффициент в селевой функции. Аналогично, изменение в производственном процессе может потребовать изменения коэффициента при одном из ограничений. И здесь анализ чувствительности может обеспечить менеджера необходимыми данными.