Математика для экономистов - Красс М.С.
ISBN 5-94723-672-9
Скачать (прямая ссылка):
Аналогично, не изменяя оптимальное решение (рис, 14.5), прямую
(11.5) можно перемещать параллельно самой себе вверх до пересечения с осью OX1 в точке R (0; 456,25) или вниз до пересечения с прямой
(14.6) в точке D (312,5; 300).
Рис. 14.4 Рис. 14.5
Таким образом, при неизменном оптимальном решении покупатать-ский спрос на шоколадное мороженое может изменяться в диапазоне от 300 до 456,25 кг.
Проведем теперь анализ задачи по пределам возможного изменения коэффициентов целевой функции, т. е. но диапазону оптовых цен на мороженое, при котором не происходит изменение оптимального решения. Изменение коэффициентов целевой функции оказывает влияние на наклон линии уровня. Уравнение линии уровня записывается в общем виде: с,.т, + C3T2-= const.
Из рис. 14.6 видно, что при увеличении C1 или уменьшении C2 линия уровня вращается вокруг точки D по часовой стрелке, Если по условию задачи C1 = 14, то с, можно увеличивать до совпадения линии уровня с прямой (14.5). Угловой коэффициент линии уровня
K^-CJc7 = -с,/14.
Угловой коэффициент прямой (И.5)
Рис. 14,6
U.Z. Симплексный метод 267
Kn, = -8/5.
Так как прямые совпадают, An)г откуда си)ІИІИ = 22,4. Коэффициент С(1) можно уменьшать до совпадения линии уровня с. прямой (14,6), поэтому
C111/» =1/2. си)т,ц=1.
Таким образом, оптимальное решение задачи не изменится, если отпускная цена I кг сливочного мороженого лежит в диапазоне от 7 до 22,4 ден. ед., при этом доход фирмы будет от 6387,5 до 11 200 леи. ед.
Аналогичные рассуждения для случая с(])= 16 позволяют сделать вывод, что оптимальное решение задачи не изменится, если отпускная пена 1 кг шоколадного мороженого лежит в диапазоне от 10 до 32 ден. ед., при этом доход фирмы будет от 8000 до 14 600 ден. ед.
14,2. Симплексный метод
Идея симплексного метода {.метода последовательного улг/чшения) заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному. Симплекс-метод является универсальным, так как позволяет решить практически любую задачу линейного программирования, заданную в каноническом виде. Значение целевой функции при этом перемещении для задач на максимум не убывает. Так как число опорных решений конечно, то через конечное число шагов получим оптимальное опорное решение.
14.2.1. Симплексные таблицы и алгоритм решения
Приведем здесь алгоритм решения задач симплексным методом.
1. Математическая модель задачи должна быть канонической. Если в исходной формулировке задача неканоническая, то ее надо привести к каноническому виду.
2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу. Все строки таблицы 1-го шага, за исключением строки Aj (индексная строка), заполняем поданным системы ограничений и целевой функции.
Симплексная таблица имеет следующий вид. is-
268 Глава 14. Линейное программирование
Ьа^нинаи Пфі-мец-м ал
Cl
C2
с.
Ш)
х,
X2
х*
А"»
ь,
с,
1
0
0
А
0
1
0
п2.¦m* 1
А
с»
х.
0
0
I
^яі.т (¦ 1
L
(I
0
0
- і дп
L(X1)
Индексная строка Д, для переменных находится по формуле
ist
и по формуле
т t-l
для свобод]юго члена. Возможны следующие случаи при решении задачи на максимум;
• если все оценки Д,гО, то найденное решение оптимальное;
• если хотя бы одна оценка Д;< О, но при соответствующей переменной .г, нет пи одного положительного коэффициента, решение задачи прекращается, так как ?(.?)-» °о, т. е. целевая функция не ограничена в области допустимых решений;
• если хотя бы одна оценка отрицательная, а при соответствующей переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению;
• если отрицательных оценок в индексной строке несколько, то в столбец базисной переменной (БП) вводят ту неременную, которой соответствует наибольшая по абсолютной величине отрицательная оценка.
Пусть одна оценка Д(<0 или наибольшая по абсолютной величине &і < 0, тогда к-н столбец принимаем за ключевой. За ключевую строку принимаем ту, которой соответствует минимальное отношение свободных членов (A1) к положительным коэффициентам А-го столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называют ключевілм элементом.
14,2. Симплексный метод 269
3. Заполняем симплексную таблицу 2-го іиаі-а:
• переписываем ключевую строку, разделив ее на ключевой элемент;
• заполняем базисные столбцы;
« остальные коэффициенты таблицы находим по правилу ч-пряно-угольника*. Оценки можно считать по приведенным ранее формулам или по правилу «прямоугольника». Получаем новое опорное решение, которое проверяем на оптимальность и т. д.
Примечания:
1. Если целевая функция L(x) требует нахождения минимального значения, то критерием оптимальности задачи является неположительность оценок Aj при всех j =\ п.
