книги / Математические методы принятия решений

со знаком минус, поэтому и рассматривались неотрицательные ко­ эффициенты.

Рассмотрим графическое решение этой задачи. Поскольку зада­ ча двумерная, то решим ее графически. Система неравенств-огра­ ничений определяет многоугольник допустимых решений (рис. 2.3).

Рис. 23. Графическое решение задачи планирования выпуска продукции пошивочного предприятия

Сначала определим полуплоскости, задаваемые неравенствамиограничениями задачи. Для этого построим прямые, заменив в огра­ ничениях знаки неравенств на знаки равенств. Чтобы выяснить, какую часть плоскости описывает неравенство, подставим в него пробную точку, например (0,0), и установим, удовлетворяет ли она неравенству. Если неравенство выполнено, то искомая полуплос­ кость включает точку (0,0). В противном случае выбирают другую половину плоскости.

Для первого неравенства прямую 1\: х\ + 3,5хг = 350		—строим
по точкам xi = 0 , хг = 350/3,5 = 100 и хг = 0, х\	= 350.	Пробная
точка (0,0) удовлетворяет неравенству 0 < 350,	т. е. точка (0,0)

входит в искомую полуплоскость (она отмечена стрелками от пря­ мой li). Прямую I2 : 2х\ + 0,5x2 = 240 — строим аналогично по двум точкам: х\ = 0 , хг = 240/0,5 = 480 и x j = 0, х\ = 240/2 = 120.

Точка (0,0) принадлежит искомой полуплоскости. Рассмотрим последнее неравенство 10xi + 20x2 ^ 1400; ему соответствует пря­ мая xi + 2x2 = 140, —также построенная по двум точкам: х\ = 0, Х2 = 140/2 = 70 и Х2 = 0, х\ = 140. Точка (0,0) не удовлетворяет неравенству 0 ^ 1400, т. е. необходимо рассматривать полуплос­ кость, не содержащую точку (0,0). Пересечение пяти полуплос­ костей дает выпуклый пятиугольник A B C D E . Для нахождения максимума функции /(х ) надо построить линию уровня. Пусть /(х ) = 0; тогда уравнение линии уровня I будет прямая 10xi + + 20x2 = 0, проходящая через начало координат параллельно пря­ мой I5. Градиент целевой функции V / = {10; 20} показывает на­ правление ее возрастания. Прямую I перемещаем параллельно самой себе в направлении V / до тех пор, пока она не выйдет из об­ ласти D. Получаем точку С —точку пересечения прямых 1\ и1у.

Xi+3,5x2= 350, x i+ Х2= 150.

Решая полученную систему уравнений, находим оптимальное решение — координаты точки С (х\ = 70, хг = 80) и вычисляем мак­ симальное значение целевой функции

/тах(я) = Ю • 70 + 20 • 80 = 2300 (уел. ед.).

Замечание. Допустим, что в рассматриваемой задаче требова­ лось найти минимум целевой функции

/(х ) = lOxi + 20x2.

В этом случае линия уровня «вошла» бы в область по линии I5, т. е. все точки отрезка А Е являлись бы оптимальным решением (беско­ нечное множество решений).

§ 2.5. Двойственность в задачах линейного программирования

В § 1.6 было показано, что иногда проще решать двойствен­ ную задачу математического программирования, чем прямую. Со­ гласно теории двойственности (см. §1.6) для каждой задачи ЛП можно построить другую задачу линейного программирования,

называемую двойственной. Переход к решению двойственной зада­ чи в ряде случаев имеет преимущества при построении алгоритмов решения задач ЛП.

Запишем обе задачи.

Прямая задача:

минимизировать функцию

		П
	f i x ) =	2 C j X j
при условиях		3 = 1
п
^	1 Q>ij3Cj ^	i	1) 2 , • . . , A/j
j =	\
n	~~
^		î —A ~1“ 1, . • •, m,
j=l

J= 1,2,..., J,

^• ^ 0 , j = Z+ l , . . . , n .

Двойственная задача:

максимизировать функцию

771

ф(у) = 2 biyi

г=1

при условиях

Уг^О, *= 1,2, ...,fc,

Уг^О, t = fc+

771	CjiVi ^
^		J =	••*»!»
г=1
m	tojiVi = Cj,	J = i + 1, • • •, П.
2
i=l

Симметричность обеих задач очевидна. Неравенству одной из них соответствует неотрицательная переменная другой, а равен­ ству — свободная переменная другой. Задача, двойственная к двой­ ственной задаче, есть исходная (прямая) задача. Таким образом, любую из этой пары задач можно считать прямой.

Для стандартного и канонического видов задачи ЛП двойствен­ ные задачи можно записать следующим образом.

С т а н д а р т н ы й в и д

Прямая задача:				Двойственная задача:
минимизировать функцию				максимизировать функцию
			П			771
f i x	) =	2 c j X j		ф(у) =		2
при условиях		3 =1		при условиях		г=1
п				т
2 CHjXj ^	è j ,	i	= l , 2 , . . . , 77i,	2 ^jiVi ^	Cji	j = 1 >2, ..., 72,
3=1				i = 1
X j ^ 0 ,	j	=	1,2, ... ,n .	Уг^О,	г = 1 ,2 ,...,m.

К а н о н и ч е с к и й ви д

Прямая задача:

минимизировать функцию

п

/(ж ) = 2 cj xj

j = 1

при условиях

71

У! CiijXj = Ь{9 i = 1,2,..., 771, j=l

Xj ^ 0 , j = 1,2, ...,77.

Двойственная задача:

максимизировать функцию

т

ф(у) = Е biVi г=1

при условиях

т

djiVi ^

J

b ^

г=1

г = 1,2, ...,тп.

Сравнивая обе задачи, нетрудно видеть, что:

1) составленную из коэффициентов при переменных в исходной задаче матрицу

( оц	а 12	а\п \
021	À22	0>2п
А =
\Omi	атп2	О'гпп/

и аналогичную матрицу в двойственной задаче

( «и	а ц	ат1 ^
On	а>22	Ûm2
и
\Oln	а2п	0>тп/

получают друг из друга простой заменой строк столбцами с сохра­ нением их порядка (такую операцию называют транспонированием

иобозначают верхним индексом «т»);

2)в исходной задаче имеются п переменных и т ограничений;

вдвойственной — т переменных и п ограничений;

3)в правых частях систем ограничений каждой из задач стоят коэффициенты целевой функции, взятой из другой задачи;

4)в исходной задаче в систему ограничений входят неравен­ ства типа > и требуется минимизировать целевую функцию /(х);

вдвойственной задаче в систему ограничений входят неравенства

типа ^ и требуется максимизировать целевую функцию ф(у).

В теории двойственности доказана следующая

Теорема. Пусть дана пара двойственных задач линейного про­ граммирования (заданных в стандартном виде).

Тогда справедливо одно и только одно из следующих утвер­ ждений:

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

min f(x) = m ax ср(у);

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

3) ни одна пара задач не имеет допустимых решений.

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

у ( А х - Ь ) = 0 ,	(2.5)
(с - уА)х = 0.	(2.6)

Условие (2.5) равносильно условиям:

Т1

а) если y i > 0, то X a ijXj = bit г = 1 , 2 , . . . , т ;

пJ'=1

б) если	X aijXj > bi,		то	yi = 0,		г =	1,2, ... ,т .
	j = \
Условие (2.6) равносильно условиям:
	771	<4 jyù		Xj = 0,	j
в) если	Cj > X		то			=	1,2 , ... , n;
			m		j
г) если	Xj > 0,	то Cj = X		ацУи		=	\,2 , . . . , п.
			г= 1

Эти условия представляют собой условия дополняющей нежест­ кости в слабой форме. Выпишем условия дополняющей нежестко­ сти в сильной форме:

	Уг = О, то	п	ац хз ~ к > О,	i =	1,2,..., т;
д) если		2
	п
е) если	2 aijxj ~ к = О, то у* > О,			г =	1, 2, ... , ш.
Может	случиться,	что	условия у* = 0 и		2 CHjxj = к выпол-
					з=i

иены одновременно. Однако всегда существует по крайней ме­

ре одна пара оптимальных решений, для которых условия у* = О

71

и 2 aijXj = к не могут выполняться одновременно.

3 =1

Нетрудно проверить, что, если вектор х —решение прямой за­ дачи, а вектор у —решение двойственной задачи, то сумма произ­ ведений соответствующих координат векторов х н у равна нулю (скалярное произведение векторов х и у равно нулю).

Рассмотрим геометрическую интерпретацию теории двойствен­ ности в задачах ЛП. Выберем задачу линейного программирования стандартного вида: минимизировать функцию

			71
	f(x) =		2 CjXj
при условиях	п		J=l
	dijXj ^	к.	i ~ 1 >2, ... , 771,
	3 = 1	j	= 1,2, ...,тг.
	X j^O ,

В § 1.3-1.5 было показано, что обычным условием существова­ ния безусловного экстремума функции во внутренней точке являет­ ся равенство нулю градиента функции в этой точке. Если при этом должны выполняться некоторые ограничения, налагаемые на пере­ менные, в виде равенств, то условием существования экстремума в допустимой точке является требование, чтобы в этой точке гради­ ент функции и нормали к поверхностям, заданным соответствую­ щими ограничениями, были «сонаправлены». Более точно, градиент функции в этой точке должен быть неотрицательной линейной ком­ бинацией нормалей к поверхностям-ограничениям. В задаче ЛП каждое неравенство определяет допустимую область — полупро­ странство. Для того чтобы допустимая точка х была оптимальной, необходимо, чтобы градиент целевой функции в точке х выражал­ ся в виде неотрицательной линейной комбинации направляющих

векторов тех и только тех ограничений, которые в точке х обраща­ ются в равенства, т. е. градиент целевой функции (вектор с) есть неотрицательная линейная комбинация нормалей (векторов) а* для ограничений, обращающихся в равенство

771+71

с = 2 У*а*’ У* > 0 =>(ai ’x ) = b*, i=l

где ^ — соответствующие коэффициенты линейной комбинации векторов о*.

Из условий дополняющей нежесткости в слабой форме следует:

а) если	yi> 0, то (а*, х) — Ь{ = 0,	г = 1, 2, ...,то + п;
б) если	(o j,х) — bi > 0, то yi = 0,	г = 1 ,2, . . . , т 4- п.
Из условий дополняющей нежесткости в сильной форме сле­
дует:	yi = 0, то (а*, я) —£>i > О,	г = 1, 2, . . . , т + п;
а) если
б) если	(a,i,x) — b i—0, то уг> 0,	г = 1, 2, . . . , т + п.

На рис. 2.4 изображены три гиперплоскости (щ, x) — bi = О, г = 1,2,3, и нормали к ним a i, аг, аз. Если вектор с такой, как пока­ зано на рис. 2.4, то он может быть выражен в виде неотрицательной линейной комбинации векторов ai и аг\ вершина, обозначенная кружком, соответствует оптимальному решению. Здесь выполнены условия дополняющей нежесткости как в слабой, так и в сильной

форме: î/з > 0 (аз, х) -	63 > 0,	у\ > 0	(ai, х) - i>i = 0, у2 > 0 *>
о (аг, х) —62 = 0. Если	вектор	с таков,	как показано на рис. 2.5,

т. е. с — нормаль к одной из гиперплоскостей, (ai ,x ) — b\ = 0, то оп­ тимальная вершина, обозначенная кружком, не удовлетворяет

Рис. 2.4. Пример выпол-	Рис. 2.5. Пример нарушения
нения условия дополня-	сильной формы условия до-
ющей нежесткости	полняющей нежесткости

сильной	форме условия		дополняющей	нежесткости, поскольку
и J/2 = 0,	и	(<i2, х) — Ъ2 = 0. Однако точка, помеченная крестом на
рис. 2.5	и	являющаяся	оптимальным	решением, удовлетворяет

и слабой, и сильной формам дополняющей нежесткости:

< *(аих)-Ь\ = 0, у2 = 0 <&(а2, х ) - Ь 2 > 0 , у3 =0<&(а3,х) - Ь3 >0.

Для решения задач ЛП разработан так называемый двойствен­ ный симплекс-метод. Процедуру начинают с нахождения двойст­ венно допустимого решения, когда одновременно 6» ^ 0 и Cj ^ 0, г = 1,2,..., т, j = 1,2,..., п, и сохраняют условие двойственной допустимости на протяжении всех шагов. Этот метод реализует­ ся посредством таких же таблиц, как и в прямом симплекс-ме­ тоде.

Двойственный симплекс-метод позволяет решать задачи ЛП и в случае, когда, сформировав единичную матрицу из коэффи­ циентов для т базисных переменных, мы получаем отрицательные значения некоторых элементов в столбце свободных членов Ь», т. е. мы не находимся в области допустимых решений. Получим так называемый псевдоплан, если Д j ^ 0,

	т
Д^* Cj Zj Cj	Cîüîj, j	1,2,..., Tl,
	г=1

где Ci, i = 1,..., m, —коэффициенты целевой функции исходной за­ дачи, стоящие в базисных столбцах; оу — соответствовующие коэф­ фициенты условий-ограничений в симплекс-таблице.

Если в псевдоплане	есть хотя бы одно отрицательное чис­
ло bi < 0 такое, что для	него все соответствовующие оу ^ 0, j =

= 1 , ... ,п , то исходная задача не имеет решения. Если в псев­ доплане имеются числа bi < 0 такие, что для некоторых из них существуют числа ûÿ < 0, то можно перейти к новому псевдопла­ ну (при котором значение целевой функции задачи на максимум не уменьшится). Когда все bi будут неотрицательными, а все Д , ^ 0, то получено оптимальное решение. Но здесь сначала определяется, какая переменная должна быть выведена из базиса, а затем —какая должна быть введена в базис.

Поцедура двойственного симплекс-метода состоит в следующем:

1)находим псевдоплан задачи;

2)проверяем оптимальность этого псевдоплана:

—псевдоплан оптимален;

—задача не разрешима;

—переход к новому псевдоплану;

3)выбираем разрешающую строку с помощью определения наибольшего по абсолютной величине отрицательного элемента Ь*

встолбце свободных членов и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения

m i n ( ^ - ) , a,ij < 0, Д ^ < 0 , j = 1 , 2 , . . n;

4)переводим г-ю базисную переменную в свободные, при этом переменная j-ro столбца становится базисной переменной;

5)переходим к п. 2).

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

В симплекс-таблице оптимального решения прямой задачи ЛП записано и решение двойственной к ней задаче. Чтобы это понять, надо элементы строки, в которой выписаны коэффициенты целе­ вой функции, представить в виде Cj —Zj, Zj = cTbyj, j = 1,2,..., n, где сь —вектор, состоящий из коэффициентов целевой функции ис­ ходной задачи, стоящих в базисных клетках оптимального реше­ ния, Uj —элементы j -то столбца симплекс-таблицы оптимального решения, и добавить в симплекс-таблицу дополнительную стро­ ку Zj. На пересечении строки Zj и столбцов базисных переменных исходной задачи (обычно это последние m столбцов) находится оптимальное решение двойственной задачи. Таким образом, опти­ мальное решение у* двойственной задачи —это тп последних эле­ ментов строки Zj оптимальной симплекс-таблицы прямой задачи; а оптимальным решением х* прямой задачи являются п последних элементов строки Zj оптимальной таблицы двойственной задачи.

Известны, кроме того, методы одновременного решения прямой

и двойственной задач, например метод последовательного сокра-

п

щения невязок, где величина 2 OijXj — b{, i = 1,2,..., т, является

з- 1

невязкой при фиксированных значениях Xj.

§ 2.6. Задача оптимальной организации поставки грузов от поставщиков к потребителям (транспортная задача)

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

	Задача. Перевозится однородный груз из трех		пунктов Л ь
Ау, Аз к четырем местам назначения В\, Bi, By,			В4. Из пунк­
та	А\ может быть направлено 50 т, из A i —40 т,		из A 3 —20 т.
В пункты		назначения должен поступить груз: в пункт В\ —30 т,
в	Бг —25	т, в By —35 т, в £4 — 20 т. Расстояния	Cij, i = 1,2,3,

j = 1,..., 4, от г-го поставщика j -му потребителю приведены в уг­ лах клеток табл. 2.6.

Таблица 2.6

Исходные данные

Пункт

л,

Аг

Л3

Потребности

в,

3

я н

2*21

3*31

О-

II U) О

Вг Вг

2	*12	4	*13
3	*22	1	*23
2	х 32	4	*зз
	Ьг = 25		by = 3	5

в4

'*14

5 *24

4 *34

S'­ il К) о

Запасы

ai = 50

Ü2 = 4 0

аз = 20

п о

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

Мы сформулировали сбалансированную транспортную задачу при условии, что количество груза, имеющееся у поставщиков,