Математика для экономистов - Красс М.С.
ISBN 5-94723-672-9
Скачать (прямая ссылка):
2. Правило «прямоугольника* состоит в следующем. Пусть ключевым элементом предыдущего шага является элемент 1 -й строки (m + 1 )-го столбца A1 я tТогда элемент г-н строки (т + 2)то столбца последующего шага, который обозначим k\ mt3, по правилу «прямоугольника» определяется по формуле
где й, |М + г, А, „ . j — элементы предыдущего шага.
14.2.2. Применение симплексного метода в задачах ЛП Поясним применение симплексного метода.
Предприятие располагает тремя производственными ресурсами (сырьем, оборудованием, электроэнергией) и может организовать производство продукции двумя различными способами. Расход ресурсов и амортизация оборудования за один месяц и общий ресурс при каждом способе производства дан в таблице (в ден. ед.).
Tl роиэ ВО ДСТНРН11 !.1 fr ресурс
Раскол ресурсов за 1 месяц
Общші ресурс
-1
I -м способ
2-Гг способ
Сырье
L
2
Оборудование
1
1
3
Электроэнергия
2
1
8
При первом способе производства предприятие выпускает за один месяц 3 тыс. изделий, при втором — 4 тыс. изделий.
270 Глава 14. Линейное программирование
Cv
3
А
0
0
0
J
-?
-*u
Vs
ь,
0
¦•'a i I
2
1
0
0
4
0
1
1
q
l
0
3
u
2
1
0
u
1
8
-3
а
0
0
0
Сколько месяцев должно работать предприятие каждым из этих способов, чтобы при наличных ресурсах обеспечить максимальный выпуск продукции?
Решение. Составим математическую модель задачи. Для этого введем обозначения:
• Xx — время работы предприятия первым способом,
• .Vj - время работы предприятия вторым способом.
Тогда задача ЛП формулируется следующим образом: найти максимум целевой функции
LCx) = За"і + Ax2 —> max
при ограничениях
+2х.2 <4,
¦ .t1 + .y3 < 3,
2jt, +X2 <8, дг, >0. X1 >0.
Приведем задачу к каноническому виду, для чего добавим в правые части ограничений дополнительные неизвестные х3. xt и xs (балансовые переменные) при ограничениях
.V1 + Ix1 + хЛ =4,
< X1 + X2 -KV4 = 3,
2г, +X7 +X5 = 8,
X a 0 / = ЇХ Теперь составим симплексную таблицу 1-го шага:
14,2. Симплексный метод 271
X1 =(0. 0, 1 а 8), L(X)=Q.
В индексной строке Aj имеются две отрицательные оценки, значит, найденное решение не является оптимальным и его можно улучшить. Б качестве ключевого столбца следует принять столбец базисной
переменной ХЬ а за КЛЮЧевуЮ СфОКу — Строку ПеремеННОЙ Jf3, где
min (\/2, 3/1. 8/1) = min (2, 3, 8) = 2.
Ключевым элементом является *2>. Вводим и столбец БП переменную хг, выводим jfj. Составляем симплексную таблицу 2-го шага:
БП
3
4
0
0
0
JfI
х2
ч
.T4
¦Ч
ь>
А
1/2
1
1/2
0
0
2
0
X4
V2
0
-1/2
1
0
I
0
3/2
0
-V2
0
1
е
-1
0
2
Q
0
~ В
X1 =(0, 2, О, І, 6), L(X2 )=&
В индексной строке имеется одна отрицательная оценка. Полученное решение можно улучшить. Ключевым злементом является «1/2». Составляем симплексную таблицу 3-го шага:
3
1
0
0
0
W)
*1
¦*2
х1
*5
4
х?
0
1
1
-1
0
І
3
х\
1
0
-1
2
0
2
0
Ч_
0
0
1
-3
I
3
<V
U
0
I
2
0
10
Uce оценки свободных неременных Д>0, следовательно, найденное опорное решение является оптимальным:
X^ =(2, 1, 0, 0, 3), і(т)„ =10.
Ответ. Первым способом предприятие должно работать два месяца, вторым — один месяц, при этом максимальный выпуск продукции составит 10 TbLC ед.
272 Глава 14. Линейное программирование
14.3. Двойственные задачи
Каждой задаче линейного программирования можно определенным образом поставить в соответствие другую задачу тоже линейного программирования, которую называют двойственной по отношению к данной (исходной) задаче. Исходная и двойственная задачи тесно связаны между собой и образуют единую пиру двойственных задач,
1EaCTO бывает так, что задача в исходной формулировке сложна для решения - проте перейти к двойственной задаче, решить сс и затем пересчитать и исследовать решение исходной задачи.
В зависимости от структуры модели исходной задачи различают симметричные, несимметричные и смешанные двойственные задачи.
14.3.1. Виды математических моделей двойственных задач Симметричные двойственные задачи
Рассмотрим неканоническую модель исходной задачи Л П. Ищется максимум целевой функции
I(.r) = C1Xj + C3-Ti + ¦-¦ + с1:хц -> max ?14.9)
при ограничениях
a,.xt + al2x2 + ... + а!л.т„ 5A1 \уг
a2irt +a.i2x, + ... + alrxK <b, \ у,, (\4\Q)
U1nX1 + amx-, + ... + лт„х„ < Ь„ ]
X1 > О, J = 1, п, І = !, т.
Составим математическую модель двойственной задачи следующим образом:
• каждому неравенству системы ограничений исходной задачи приводити в соответствие переменную у-,
• составляем целевую функцию, коэффициентами которой являются свободные члены системы ограничении исходной задачи;
• составляем систему ограничений. Коэффициенты системы ограничений образуют транспонированную матрицу коэффициентов системы оіранпчений исходной задачи. При этом знаки неравенств меняются на противоположные. Свободными членами системы