pizhurin_a_a_pizhurin_a_a_modelirovanie_i_optimizaciya_proce

ограничения двойственной задачи. Она совпадает с первой строкой, со­ ставленной из коэффициентов в ограничениях исходной задачи. То же от­ носится к любой другой паре из графы и строки. Коэффициентами целевой функции двойственной задачи служат свободные члены ограничений пря­ мой задачи, а свободными членами ограничений двойственной задачи - ко­ эффициенты целевой функции исходной ЗЛП.

С использованием отмеченных взаимосвязей легко составить двой­ ственную задачу к любой исходной ЗЛП. В этой паре задач линейного про­ граммирования любую из них можно выбрать в качестве исходной. Тогда другая ЗЛП окажется двойственной к ней. Так, взяв в качестве исходной задачу (3.67) и перейдя по описанным выше правилам к двойственной, вернемся к ЗЛП (3.66).

Рассмотрим ЗЛП с ограничениями-равенствами:

п

W= 'YjCjXj —>max;

м

п

Y<aijxj = bi> i = j =i

Xj> 0, y = l,..., п.

Задача, двойственная к ней, формулируется следующим образом:

т

1=1

т

'Laijyi ^ cj> У = 1.2..... П.

i=1

В данном случае не требуется неотрицательности переменных двойственной задачи.

Приведем теперь прямую и двойственную задачи (3.64) и (3.65) к ОЗЛП введением дополнительных переменных. Запишем первое из огра­ ничений исходной ЗЛП (3.64) в виде Ьх~ а ихх- а 12х2 - . . . - а 1пхп >0.

Введем дополнительную неотрицательную переменную хп+1, рав­

ную левой части этого ограничения. Тогда его мохсно записать в виде ра-

венства Ь, - а ихг - апх2 -... - а ихп = хп+1.

Аналогичным образом вводим дополнительную неотрицательную переменную для каждого из остальных ограничений задачи (3.64), всего, следовательно, т дополнительных переменных. Целевую функцию в ОЗЛП следует минимизировать, поэтому знаки коэффициентов в ней из­ меняем на противоположные. Теперь исходная задача (3.64) примет сле­ дующий вид:

	72
	w = Yl(-сj )xj -+ min;			(3.68)
	*«+. =Ь\ - { а \\Х1+ а \2Х2 + -- + аиХЛ
	Xn+2 = b 2 ~ («21*1 + a 22X2 + •••+ a 2nXn k
				(3.69)
	Xn+m= K - { am1*. + am2X2 + -		+ amnXn)>J
	Xj >0, y = l, 2	,	|	(3.70)
	xn+i >0, z = l, 2,...,/w.		j

Система равенств (3.69) написана здесь в стандартной форме по об­ разцу системы (3.48).

Обратимся к двойственной задаче (3.65). Первое из ее ограничений имеет вид ах + а21у 2 + • • • + ат\Ут~ с\ - 0. Введением дополнительной

неотрицательной переменной у т+1 оно преобразуется в равенство аиу х+ + а2Л + '" + ат\Ут ~ с\~ У т+\‘ Для подобных преобразований всех п не­ равенств задачи (3.65) потребуется введение п дополнительных неотрица­ тельных переменных y m+j (j = 1, 2,..., п). После этого двойственная задача примет вид следующей ОЗЛП:

т		(3.71)
F = 'Zb,y. —^min;
У т +l ~ ~ С1~(~а иУ1~а2\У2 -■■■-а т \У т У>
		(3.72)
У т + п = - С „ - { - а \п У \ -	а 2 п У г - -	- а тпУт )> ,
		(3.73)
Задачи (3.68) - (3.70) и (3.71) -	(3.73) имеют одинаковое число пе­

ременных, равное (т + п). При этом базисными в прямой задаче являются переменные хи+1,..., хм+„, ав двойственной- у т^,..., у т+п.

Запишем стандартную симплексную таблицу, соответствующую прямой ЗЛП (3.68)-(3.70) (табл. 3.18).

					Т а б л и ц а 3.18
	Базисная	Свободный		Свободные переменные
	переменная	член	*i	*2	Хп
	%п+1	bi
			а\\	ап	Q\n
	Хп+2	ь2	а2\	ац	Clin
	%п+т	Ът	Qm\	Qml	&тп
	W	0	С\	сг	Cn

Стандартная таблица для двойственной задачи (3.71) - (3.73) имеет другой вид (табл. 3.19).

				Т а б л и ц а 3.19
Базисная	Свободный		Свободные переменные
переменная	член	У\	У2	Ут
	- с \
Ут+1		- а и	- а 2\	~ Ящ]
Ут+2	- с г	- а п	- а 22	~ &т2
Ут*п	- сп	- а Хп	~ &2п	~ Qmn
F	0	- b i	-Ъг	- Ь т

Можно заметить, что матрица коэффициентов в табл. 3.19 с точно­ стью до знака совпадает с матрицей в табл. 3.18, повернутой на 90°. Отсю­ да следует, что, решив прямую ЗЛП, мы уже фактически решили задачу, двойственную к ней.

Действительно, пусть при решении прямой ЗЛП на последней ите­ рации симплекс-метода получена симплексная таблица вида табл. 3.18. Это означает (см. п. 3.4.3), что в этой таблице все bt > 0, все с( <0, и опти­

мальное решение прямой задачи имеет вид

*Г=Х2= • • • = < =°;

Х л + 1 = ^1> Х п + 2 ~ ^ 2 ’ - - - ’ Х п + т ~ Ь т -

На той же итерации симплексная таблица двойственной задачи бу­ дет иметь вид табл. 3.19. Но тогда ее столбец свободных членов состоит из элементов (- сД и все они неотрицательны, а элементы строки F - это зна­ чения (- Ы), и все они неположительны. Значит, на этой же итерации полу­ чено и оптимальное решение двойственной задачи, которое имеет вид

74

у'\ =у1= - = Ут = ° ;

Ут+\ = ~CV Ут+2 ~ ~С29’'*» -У/я+л = '

Таким образом, для получения решения двойственной задачи дос­ таточно решить прямую ЗЛП, а в качестве значений базисных переменных двойственной задачи взять с противоположным знаком элементы строки W прямой ЗЛП из ее последней симплексной таблицы. Значения же свобод­ ных переменных двойственной задачи следует принять равными нулю (см. две приведенные выше системы равенств). Отмеченная противополож­ ность знаков для элементов строки W в табл. 3.18 и столбца свободных членов в табл. 3.19 объясняется лишь тем, что решение как прямой, так и двойственной задачи было сведено к ОЗЛП с минимизируемой целевой функцией.

Как выяснилось, базисным переменным прямой ЗЛП соответствуют свободные переменные двойственной, а свободным переменным исходной задачи - базисные переменные двойственной ЗЛП. Для того чтобы сразу получать решение двойственной задачи по результатам решения прямой ЗЛП, следует установить соответствие между переменными той и другой задачи. Оно вытекает из сравнения табл. 3.18 и 3.19 и представляется в

следующем виде: с переменными	ь Хп+2,..., хп+тпрямой ЗЛП приводят в
соответствие переменные у\,	у т двойственной задачи (в соответст­

вующем порядке), с переменными дгь х2,..., хп прямой задачи приводят в соответствие переменные ут+\, у т+2,..., ут+пдвойственной ЗЛП.

Пример. Обратимся вновь к ЗЛП, решенной в п. 3.4.4. Ее оптимальное реше­ ние приведено в табл. 3.11 и имеет вид

х* = х* = х* = 0; х\ = 4/5; х* = 18/5.

Здесь х4 и х5 - дополнительные переменные, которые в табл. 3.11 были обо­ значены через у , и у 2 соответственно.

Задача, двойственная к исходной ЗЛП, имеет вид

F= 6 у 1- 4 у 2 —» min;

Уг 2 ^ - 2 ;

3>,-5>2*-3;

*у г *уг

7 , > 0; у 2 > 0 .

Установим соответствие между переменными прямой и двойственной задач: *4 * * у х; х5 о у 2;

х2 **Уа> Х3+*У5-

В табл. 3.11 базисными переменными являются х4 и х2. Им соответствуют свободные переменные двойственной задачи у { и у 4 , оптимальные значения которых

равны нулю: у\ = 0;	у\ = О. Свободные переменные в табл. 3.11 -		это х5 ,	Xj, х3 . Им
соответствуют базисные переменные двойственной задачи: у 2,		у 3,	у 5. Их оптималь­
ные значения сразу получаем согласно сформулированному выше правилу из строки W
табл. 3.11, взяв ее	элементы с противоположными знаками:	у*2 =Ъ/5,		у \ = 4/5,
y's =11/5 ■

3.6.2. Экономическая интерпретация прямой и двойственной ЗЛП

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

Пример. Для исходной ЗЛП из п. 3.4.4 оптимальное значение максими­

зируемой	целевой функции WXonm равно (- 12/5).		Минимальное значение целевой
функции	F	двойственной задачи получим, подставив		в выражение для нее
F = 6 y }- 4 y 2		оптимальные значения переменных:	у* = 0;	у\ =3/5. Как легко убе­
диться, результат подстановки тоже равен (- 12/5).

Для уяснения содержательного смысла решения двойственной за­ дачи обратимся к экономической интерпретации прямой ЗЛП (3.64). Рас­ смотрим с этой целью следующий пример.

Предположим, что предприятие вырабатывает п видов продукции. Для ее изготовления требуется т видов ресурсов - сырья, оборудования, рабочей силы и т. д. Имеющиеся объемы ресурсов каждого вида составля­ ют Ьи Ьт. Для выработки единицы продукцииj -го вида (/=1,2,...,

п) необходимы затраты /-го ресурса в количестве atj (i = 1, 2,..., т). Из­

вестна величина прибыли, получаемой от реализации единицы продукции 7-го вида, равная с-. Требуется определить объемы выпуска продукции

каждого вида: соответственно jc1? х2,...9хп, при которых расход каждого из ресурсов не превышает заданного его количества, а суммарная прибыль от производства всех видов продукции окажется максимальной. Легко убе­ диться, что математической моделью этой задачи будет ЗЛП (3.64).

В рассмотренную схему укладывается целый ряд практических за­ дач. Например, в задаче формирования производственной программы ме­ бельной фабрики (пример. 3.1.1) различными видами продукции были шкафы, столы и стулья, а ресурсами - машинное время по каждому типу оборудования.

Пусть **, х*2,..., х*п - оптимальное решение исходной ЗЛП (3.64), а

УиУ2 ^--уУт “ оптимальное решение двойственной задачи (3.65). Количе­ ство т переменных в ней равно числу видов ресурсов в прямой ЗЛП.

Для экономического анализа двойственной ЗЛП важны следующие положения, являющиеся основными следствиями теорем, доказанных в теории двойственности:

1) если в оптимальном решении исходной задачи некоторый /-й ре­ сурс используется не полностью, т. е. имеет место строгое неравенство

п	*	в оптимальном решении
^cijjXj < b t, то соответствующая переменная

М

двойственной задачи равна нулю: у* = 0. Если же данный ресурс согласно оптимальному решению расходуется полностью (соответствующее огра­ ничение выполняется как строгое равенство), то значение у* положитель­ но;

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

т

b ty \ .

1= 1

Отсюда следует, что двойственная переменная у *, являясь коэффи­ циентом при Ъt, характеризует зависимость максимального значения целе­ вой функции исходной задачи от изменения ресурсов (речь идет об отно­ сительно малых изменениях их объемов). Действительно, из последнего равенства следует, что

y',=dWm ldblt i =

откуда

Следовательно, величина двойственной переменной в оптимальном решении показывает, насколько возросло бы максимальное значение целе­ вой функции исходной задачи, если бы количество данного ресурса увели­ чилось на единицу. (Двойственные переменные У\, у 2>"-> Ут част0 назы­ вают условными или двойственными оценками соответствующих видов ресурсов.) Поэтому наибольшую величину двойственной оценки в опти­ мальном решении будет иметь наиболее дефицитный ресурс. Ресурсу, имеющемуся в избытке, соответствует условная оценка, равная нулю.

Вернемся к примеру из п. 3.1.1, относящемуся к задаче фор­ мирования производственной программы.

Ее математическая модель представляет собой ЗЛП, описываемую соотноше­ ниями (3.1) - (3.5). Эта задача была решена симплекс-методом. Ее оптимальное реше­

ние: х* = 360; х2 = 200; х\ = 400, т. е. максимальная прибыль будет получена при из­

готовлении 360 шкафов, 200 столов и 400 стульев. Соответствующее значение целевой функции равно 3200 руб.

Составим задачу, двойственную к данной ЗЛП. Она имеет следующий вид:

F = 250у j+ 300у2 + 320^ - 150>>4 - 200>>5 - 400.у6 -» min;

0,25уJ+ 0,1Ъу2 + 0,24у3 - у 4 > 5;

0^,+ 0,13л +<У9Л - у 5>3;

0,3.у j+ ОД 1у 2 + 0,14^ - у 6 > 2,

у > 0; i = l,2 ,..., 6.

Результаты ее решения:

Л* = 20; у1 = у 1=/4= 0; у\ =1; у\ =4; Fmm=3200.

Нулевые значения переменных у* и уъ свидетельствуют об избыточности ре­

сурсов в ограничениях (3.3) и (3.4) прямой ЗЛП, т. е. ресурсов машинного времени для сверлильных и шлифовальных станков. В самом деле, подставив в них найденные вы­ ше оптимальные значения х \9х \ ъ х \, легко убедиться, что эти ограничения выпол­

няются как строгие неравенства. В то же время значение у \ не равно нулю, что означа­

ет дефицит ресурса машинного времени для фрезерных станков - ограничение (3.2). Действительно, подставив в это ограничение оптимальные значения переменных пря­ мой задачи, убеждаемся, что оно выполняется как равенство. Приняв во внимание най­ денное значение у\= 20, можно сделать следующий вывод: увеличение ресурса ма­

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

3.7.Транспортные задачи линейного программирования

3.7.1.Математическая модель транспортной задачи

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

сфабрик в магазины и т. д. Во всех задачах подобного рода имеется не­ сколько пунктов отправления - поставщиков, - где сосредоточены запасы груза, и несколько пунктов назначения - потребителей груза. Необходимо составить экономичный план перевозок грузов от поставщиков к потреби­ телям. В исследовании операций подобные задачи известны под названием

транспортных задач (ТЗ).

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

Пример. Предположим, что груз, подлежащий перевозке, сосредоточен в трех пунктах отправления: А ь Aj, Аз, запасы груза в которых равны соответственно а , = 35;

а2 =45 и а3 =50 единиц (табл. 3.20).

Поставщик

Обозначение	Запас груза
Л>	ил
	СП II
	д 2 = 45
Лз	а 3 = 50

			Т а б л и ц а	3.20
	Потребитель
*i	В2	*3	*4
5		13	6	11
*п	*12	*13	*14
4		7	12	8
*21	*22	*23	*24
9		2	3	10
*31	*32	*33	*34

Потребность в грузе	*j = 30	Ь2 = 10	6 3= 65	*4 = 25
Груз надо доставить четырем потребителям: В 1# В2, В3, # 4,				подавшим заявки

на 30, 10, 65 и 25 единиц груза соответственно. При этом суммарный запас груза у по­ ставщиков равен сумме потребностей в нем у потребителей:

Я 1+^2 ■*"^3 =^1 +^2 +^3 "^^4 =130.

Известна стоимость перевозки единицы груза от каждого поставщика к каждо­ му потребителю. Эти величины приведены в углах соответствующих клеток табл. 3.20. Требуется указать, сколько груза должен получить каждый потребитель от каждого по­ ставщика. При этом необходимо удовлетворить заявки всех потребителей, вывезти груз из всех пунктов отправления и обеспечить минимум затрат'на перевозку всего груза. Предполагается, что для каждого маршрута эти затраты пропорциональны количеству перевозимого груза.

Обозначим через xtj количество груза, перевозимое от /-го потребителя к у-му поставщику. Эти искомые переменные служат элементами решения. В нашей задаче их будет 12. jsc jjj * ]2, ^ 13*^ ]4>^21>■^12»*23>*24**31**32>^зз >*34 • Запишем условие того, что выполнена заявка первого потребителя. Это означает, что количество груза, получен­ ное им от первого, второго и третьего поставщиков, в сумме должно быть равно 30, т. е. * 11+*21 +Х3|=30

Аналогично записываются условия выполнения заявок для остальных по­ требителей: * ,2+*22 +*32=10, Xj3+ *23 + X33= 65, * 14+ *24+*34=25.

Рассмотрим ограничения, связанные с требованием вывезти весь груз каждого пункта отправления. Первый поставщик должен отправить в адрес первого, второго, третьего и четвертого потребителей соответственно * п , * 12, * 13 и * 14 единиц груза,

всего 35 единиц: х,,+ ;с12+ х 13+х14=35. Соответствующие ограничения для остальных

поставщиков имеют следующий вид: х 2]+х22 + х23+ х24 = 45; x 3l+x32 + * 33+*34 =50.

Для получения целевой функции задачи надо сложить затраты на перевозку по всем маршрутам: каждое слагаемое в этой сумме равно произведению количества пере­ возимого груза на стоимость перевозки единицы груза по данному маршруту. Так, стоимость перевозки груза из А 2 в В 3 равна 12х23. Целевая функция поэтому имеет

следующий вид:

W - 5x11+13xj2+ 6 x 13+11x14+4jc21 + 7 х 22 + 12х23 + 8х24 + 9*31 + 2х32 +

+ Зх33 + 10х34	m*n •
Полученные соотношения вместе с требованием неотрицательности перемен­
ных Ху > 0 (/' = 1, 2,3; j = 1, 2,3,4) образуют	математическую модель транспортной
задачи.

Рассмотрим теперь эту модель в общем виде. Имеем т поставщиков и п потребителей (табл. 3.21). Запасы груза у поставщиков равны соответ­ ственно a {ia29...,am. Заявки потребителей составляют Ъх\ Ь2;...; Ъп. Из­

вестна стоимость Су перевозки единицы груза от /-го поставщика к /-му

потребителю, / = 1, 2,..., т; j = 1, 2,..., п. Предполагается, что суммарные запасы груза равны суммарным потребностям в нем:

			т	п
			/=1	;=1	а	74)
					Т а б л и ц а	3.21
Поставщик				Потребитель
Обозна­	Запас		В 2	b j	в„
чение	груза
^1	«1	с \\	с п	С1У	с и
л 2	*2	С2\	С22	Су	С2	п
•	•	•	•	*	*
Л,	я,	С,1	,2	сч	С in
			С
	•	•	•	•	•
А т	ат		Ст2	Cmj	Стп
Потребность			h	bj	К
в грузе

Искомый план перевозок, т. е. совокупность значений переменных Ху, должен удовлетворять тем же условиям, что и в рассмотренном выше

числовом примере.

Запишем ограничения задачи, связанные с требованием удовлетво­ рить заявку каждого потребителя:

+ х 21 + ... + Хт

+ х 77 +

--Ь2;

(3.75)

++... + =*»•

Требование вывезти весь груз из каждого пункта отправления реа­ лизуется следующими ограничениями:

х„ + л : „ + . = я 1>

+х22 + ■■■+ х2„ - а2;

(3.76)

ml т	m2
Целевая функция задачи
	т	п	(3.77)
W = Y,'Lcijxy ->min.
	м м
Переменные xtj должны быть неотрицательными:
ху >0,	/ =	т\	(3.78)

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

Рассмотренная выше модель транспортной задачи, предполагающая равенство суммарного спроса суммарным запасам, т. е. наличие ограниче­ ния (3.74), называется закрытой моделью транспортной задачи. Можно доказать, что эта задача всегда имеет оптимальное решение.

Решение транспортной задачи часто называют планом перевозок. Вместо слов «допустимое решение транспортной задачи» говорят «допус­ тимый план», вместо слов «опорное решение»-«опорный план перевозок».