Введение в математическое моделирование. Математические методы и моделирование горной промышленности. Количественные методы анализа хозяйственной деятельности, страница 6

Исходная или прямая задача – максимизировать при ограничениях по наличию ресурсов, за независимые переменные Х и У принимаются объем выпуска товаров А и В.

D=70х+60у max

3х+2у<3000

5х+6у<7500

Х, У>0

Двойственная или обратная задача – минимизировать затраты на ресурсы при ограничениях по прибыли на 1 единицу товаров А и В. За независимые переменные U и W примем оценки стоимости ресурсов 1 и 2.

Двойственную задачу мы запишем:

D=3000u+7500w min

3u+5w>70

2u+6w>60

U, W>0

Особенности двойственной задачи линейного программирования:

·  Если исходная задача является задачей максимизации, то двойственная – задачей минимизации.

·  Коэффициенты целевой функции исходной задачи становятся свободными членами ограничений двойственной задачи.

·  Свободные члены ограничений исходной задачи становятся коэффициентами целевой функции двойственной задачи.

·  Матрицу ограничений двойственной задачи получают транспонированием ограничений исходной.

·  Знаки неравенств ограничений меняются на обратные.

·  Число переменных исходной задачи равно числу ограничений двойственной задачи.

·  Число переменных двойственной задачи равно числу ограничений исходной задачи.

Математическая и экономическая связь между исходной и двойственной задачами, если исходная задача имеет оптимальное решение, то и двойственная задача имеет оптимальное решение и значение целевых функций совпадает, следовательно, оптимальному плану выпуска продукции соответствует система минимальных оценок ресурсов, причем прибыль, получаемая при составлении оптимального плана равна суммарной оценке ресурсов, поэтому оценки ресурсов, получаемые при решении двойственной задачи обеспечивают выполнение оптимального плана, который балансирует затраты и расходы.

Сущность двойственного симплекс-метода.

Если в задаче количество ограничений превышает число переменных или в исходной матрице строка целевой функции положительна при решении задачи на максимум, то она может быть преобразована в двойственную задачу, а затем решена с помощью симплексного метода.

Пример.

D=80x+110y min

4x+5y>2000

x+2y>700

20x+16y>7800

x, y>0

c=2000u+700v+7800w max

4u+v+20W<80

5u+2v+16w<110

U, w, v>0

Задача

Ряд	Базис	1	a	b	с	1	2	3	4	5	6	7
1	0	1500	-4	0	3	0	0	0	0	0	0	0
2	1	900	-1	0	0	1	0	0	0	0	0	0
3	2	850	0	-1	0	0	1	0	0	0	0	0
4	3	700	0	0	-1	0	0	1	0	0	0	0
6	4	250	1	0	0	0	0	0	1	0	0	0
	5	100	0	1	0	0	0	0	0	1	0	0
	6	100	0	0	1	0	0	0	0	0	1	0
	7	-150	1	1	1	0	0	0	0	0	0	0
	Z	0	-1	-1	-1	0	0	0	0	0	0	0