лекции(II курс)

Выпуклыми множествами могут быть не только многоугольники. Примерами выпуклого множества являются круг, сектор, отрезок, куб, пирамида, прямая, полуплоскость, полупространство и др.

Среди точек выпуклого множества можно выделить внутренние, граничные и угловые.

Определение. Точка множества называется внутренней, если в некоторой ее окрест-

ности содержатся точки только данного множества.

Определение. Точка множества называется граничной, если в любой ее окрестности содержатся как точки, принадлежащие данному множеству, так и точки, не принадлежащие ему.

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

Определение. Точка множества называется угловой (или крайней), если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.

C!н#$%&нняя $очка

	B
	D
A	M

N

E ,%аничная $очка

F

./ло1ая $очка

Важно: Для выпуклого множества угловые точки всегда совпадают с вершинами мно-

гоугольника, в то же время для невыпуклого множества это не обязательно.

Определение. Множество точек называется замкнутым, если включает все свои

граничные точки.

Определение. Множество точек называется ограниченным, если существует шар (круг) радиуса конечной длины с центром в любой точке множества, который полностью содержит в себе данное множество; в противном случае множество называется незамкнутым.

2.3. Геометрический смысл решений неравенств, уравнений и их систем.

Рассмотрим решения неравенств.

Теорема 2.2. Множество решений неравенства с двумя переменными

a11x1 + a12x2 ≤ b1

является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1 + a12x2 = b1, включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравенства

a11x1 + a12x2 ≥ b1.

Пример. Построить множество решений неравенств:

a) 3x1 − 4x2 + 12 ≤ 0; b) 3x1 − 2x2 ≥ 0.

Построим границу полуплоскости.

91

		Y				Y
		3
		2
		1			1
				X				X
-4 -3	-2 -1	0	-4			0	1

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

В качестве контрольной точки удобно брать O(0, 0). В данном случае, решением неравенства а) является нижняя полуплоскость, не содержащая точку O(0, 0), в случае b) в качестве контрольной точки берем B(1, 0), òàê êàê O(0, 0) взять нельзя (она лежит на

построенной прямой) и решением неравенства является нижняя (правая) полуплоскость, содержащая эту точку.

Учитывая, что множество точек, удовлетворяющих уравнению

a11x1 + a12x2 + . . . + a1nxn = b1

ïðè n = 3, является плоскостью, а при n > 3− ее обобщением в n−мерном пространстве

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

Теорема 2.3. Множество всех решений линейного неравенства с n переменными a11x1 + a12x2 + . . . + a1nxn ≤ b1

является одним из полупространств, на которые все пространство делится плоскостью или гиперплоскостью a11x1 + a12x2 + . . . + a1nxn = b1, включая и эту плоскость (гиперплоскость).

Теорема 2.4. Множество решений совместной системы m линейных неравенств с двумя переменными

	a11x1 + a12x2	b1;
	a21x1 + a22x2	≤ b2;
	. . .	≤
		≤ bm.
am1x1 + am2x2

является выпуклым многоугольником (или выпуклой многоугольной областью).

Пример: Построить множество решений системы неравенств

	−5x1 + 4x2 ≤ 20;							(I)
			−	;	≤
x		1		0			24;	(II)
	2x1 + 3x2
x1				3x2		≤3;		(III)
	0 ≤≥x2 ≤ 6.

Для построения искомого множества решений системы неравенств строим последовательно множество решений каждого неравенства. Рекомендуется после нахождения каждой

92

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

	Y
(
8
6	B		C
5
A
				D	(
0		4			X
(			3		12

Отметим, что при построении областей решений систем неравенств возможны следующие случаи:

а) Замкнутый многоугольник; б) Незамкнутая многоугольная область;

B

A

F

в) Одна точка;

C

A

D

E	B	C

г) Пустое множество, когда система неравенств несовместна.

2.4.Свойства задачи линейного программирования.

1)Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым. (геометрически выпуклый многоугольник (многогранник)).

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

3)Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка многогранника решений и наоборот, каждой угловой точке

многогранника решений соответствует допустимое базисное решение.

Вывод: если ЗЛП имеет единственное оптимальное решение, то оно совпадает с одним из ее допустимых базисных решений.

93

Тема 3. Геометрический метод решения задач линейного программирования.

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

Метод соcтоит из нескольких этапов:

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

2)По виду целевой функции строим линии уровня.

Линией уровня линейной функции F называют линию, вдоль которой эта функия принимает одно и то же фиксированное значение c, ò.å. F = c èëè a1x1 + a2x2 = c.

Åñëè c = 0, òî F = 0 называется нулевой линией уровня.

Уравнение линии уровня есть уравнение прямой. При различных уровнях c линии

уровня параллельны, так ка их угловые коэффициенты равны. Таким образом, линии уровня функции F это своеобразные "параллели". Важное свойство линии уровня

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

Для определения направления достаточно изобразить две линии уровня и определить,

на которой из них уровень больше.
3)	Направление возрастания линий уровня обозначим вектором	q .
4)		−→
	Перемещаем линии уровня по многоугольнику решений в направлении возраста-

−→

ния вектора q , если ищется максимум, или в направлении убывания его, если ищется

минимум до встречи с крайней угловой точкой.

5)Находим координаты этой точки x1, x2.

6)Подставляем найденные значения x1, x2 в целевую функцию, записываем ответ. Пример. Решить геометрически задачу (об использовании ресурсов)

F = 2x1 + 3x2 → max

при ограничениях

	x1 + 3x2					18;	(I)
		≤			;
		1	+ x2		≤	16;	(II)
	2x1
x2				5;	≤		(II)
	3x			21			(IV)
x1 ≥≤0, x2 ≥ 0.

Построим многоугольник решений

	Y
		F=24
5		B
F=6	A	C
		Q

0

(	O

F=0

	D
E	X
	7

94

Очевидно, что при F = 0 линия уровня проходит через начало координат (строить ее не обязательно). Построим линию уровня F = 6. Ее расположение указывает на направ-

−→

ление возрастания линейной функции (вектор q ). Так как рассматриваемая задача на отыскание максимума, то оптимальное решение в угловой точке C, находящейся на

пересечении прямых I è II, значит ее координаты определяются решением системы

{

x1 + 3x2 = 18; 2x1 + x2 = 16.

откуда x1 = 6, x2 = 4. Максимум функции F = 2 · 6 + 3 · 4 = 24.

Итак, максимальная прибыль в 24 руб. может быть достигнута при производстве 6

единиц продукции P1 и 4 единиц продукции P2. Пример. Решить геометрически задачу (о рационе)

F = 4x1 + 6x2 → min

при ограничениях

		3x + x2		9;	(I)
	x1		1+ 2x2	≥ 8;	;
				≥	;
Строим многоугольник	x1 + 6x2			≥ 12;
			≥ 0, x2 ≥ 0. .
	x1

решений:

Y

Q

0

X

В данном случае многоугольник решений представляет собой неограниченную многоугольную область. По расположению линии уровня, например F = 12 находим направле-

−→

ние вектора q . Очевидно, что точка минимума это точка B ("входа") в многоугольник

−→

решений, так как при дальнейшем перемещении линии уровня в направлении вектора q значения линейной функции увеличиваются.

Находим координаты точки B(2, 3), ïðè ýòîì Fmin = 4 · 2 + 6 · 3 = 26.

Итак, минимальная стоимость рациона 26 руб., если в него включить 2 единицы корма I и 3 единицы корма II.

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

95

Пример: Решить геометрически следующие задачи

	a)F = 3x1 + 3x2 → max,					b)F = 2x1 − 3x2 + 1 → min,
		x1 + x2			8;		x1 + x2			4,;
		2x1 x2≤			1;		2x1 x2≥			1;
			−	≤				−	≤
	x1		−2x2	≥ 2;		x1		−2x2	≥ 1;
В случае а):
			≥ 0, x2 ≥ 0.					≥ 0, x2 ≥ 0.
	x1					x1

линия уровня с максимальным уровнем совпадает с граничной линией AB многоугольника решений ABCD, т.е. с линией x1 + x2 = 8. Следовательно, на всем отрезке AB ëè- нейная функция F = 3x1 + 3x2 принимает одно и то же максимальное значение, равное 2(x1 + x2) = 3 · 8 = 24. Это означает, что задача имеет бесконечно много отимальных решений (их задают координаты точек отрезка AB), среди которых базисных оптимальных решений два соответственно в угловых точках A(3, 5) è B(6, 2). Точки отрезка AB задаются уравнением x2 = 8 − x1, ãäå 3 ≤ x1 ≤ 6.

Èòàê, Fmax при бесконечном множестве оптимальных решений x1 = c, x2 = 8 − c, ãäå

3 ≤ c ≤ 6.

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

F = 3x1 + 3x2, x1 + x2 = 6.

В случае b):

Если линию уровня перемещять в направлении убывания линейной функции (т.е. в на-

−→

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

Итак, конечного оптимума линейной функции нет, т.е. Fmin = −∞.

Рассмотренный геометрический метод решения обладает рядом достоинств и недостат-

êîâ:

достоинства:

Он прост, нагляден, позволяет быстро и легко получить ответ.

недостатки:

возможны технические погрешности, многие величины, имеющие четкий экономиче- ский смысл (такие, как остатки ресурсов производства, избыток питательных веществ и т.п.), не выявляются при геометрическом решении. Но самое главное геометрический метод неприемлем для решения практических задач. Его можно применить только в том случае, когда число переменных в стандартной задаче равно двум. Поэтому необходимы аналитические методы, позволяющие решать задачи линейного программирования с любым числом переменных и выявить экономический смысл входящих в них величин. Эти методы будут рассмотрены далее.

96

Тема 4. Симплексный метод.

Введение. Критерий оптимальности. Алгоритм симплексного метода. Алгоритм полу- чения первоначального базисного решения.Особые случаи симплексного метода.

4.1. Введение.

Симплексный метод является универсальным методом, которым можно решить любую ЗЛП. Впервые симплексный метод был предложен американским ученым Дж.Данцигом в 1949г., однако еще в 1939 г. идеи метода были разработаны российским ученым - Л.В.Канторовичем. В настоящее время он используется для компьютерных расчетов, однако несложные примеры с применением симплексного метода можно решать и вручную.

Идея симплексного метода состоит в следующем: осуществляется переход от одного допустимого базисного решения к другому, при котором целевая функция постепенно приближается к своему оптимуму.

Метод состоит из следующих основных этапов:

1)Приведение задачи к каноническому виду.

2)Получение любого допустимого базисного решения.

3)Правило перехода от одного допустимого базисного решения к другому (лучшему).

4)Проверка критерия оптимальности для найденного решения.

4.2.Критерий оптимальности.

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

2)Критерий оптимальности решения при отыскании минимума линейной (целевой) функции: если в выражении линейной функции все коэффициенты при свободных переменных положительны, то решение оптимально, т.е. получено ее минимальное значение.

4.3.Алгоритм симплексного метода.

1)Систему функциональных ограничений приводим к каноническому виду путем введения добавочных неотрицательных переменных.

2)В полученной системе m уравнений с n неизвестными разбиваем переменные на две

группы: базисные и свободные.

Правило выбора базисных переменных. В качестве базисных переменных на первом шаге следует выбрать (если возможно) такие m переменных, каждая из которых вхо-

дит только в одно из m уравнений системы, при этом нет таких уравнений, в которые не

входит ни одна их этих переменных. Дополнительные переменные удовлетворяют этому правилу.

Решаем систему и получаем базисное решение. Если решение допустимо, то переходим

êпункту 4), если недопустимо, то предварительно выполняем пункт 3).

3)От полученного недопустимого базисного решения переходим к допустимому или устанавливаем, что система ограничений данной задачи противоречива.

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

5)Если критерий оптимальности не выполнен, то переходят к новому базисному решению: из свободных переменных, входящих в целевую функцию с положительным (для

97

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

6) Чтобы решить, какая из базисных переменных перейдет в свободные, составляют оценочное соотношение свободных членов уравнений к коэффициентам при переводимой переменной. Причем только для тех уравнений, в которых эти коэффициенты с разными знаками, для остальных отношение считают равным ∞. Из найденного оценочного

отношения выбирают наименьшее, и тем самым решают, какая из базисных переменных перейдет в свободные. Соответствующее уравнение выделяют.

7)Выражают новые базисные переменные и целевую функцию через свободные, начи- ная с выделенного уравнения.

8) Повторяют пункты 5 7 до тех пор, пока не будет достигнут критерий оптимальности. После этого выписывают компоненты оптимального решения и находят оптимум

целевой функции.

Пример. Решить симплексным методом задачу

				F = 2x1 + 3x2 → max
при ограничениях
		x1 + 3x2			≤	18;		x 0.
		2x1 + x2				16; , x 0,
			≤	5;	≤		1 ≥	2 ≥
	x2
		3x1 ≤ 21.

Решение. C помощью дополнительных неотрицательных переменных перейдем к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком +, т.к. все неравенства имеют вид ≤. Получим систему ограничений в виде:

	x1 + 3x2	+ x3	= 18;
	2x1 + x2	+ x4	= 16;

x2 + x5 = 5;3x1 + x6 = 21.

ØÀÃ 1. Так как дополнительные переменные удовлетворяют правилу выбора базисных переменных, то

x3, x4, x5, x6 базисные; x1, x2 свободные.

Выразим базисные переменные через свободные:

			−	−
	x3	= 18	−	x1	3x2		;
x4 = 16				2x1−		x2;

x5 = 5 − x2;x6 = 21 − 3x1.

Положив свободные переменные равными нулю, т.е. x1 = 0, x2 = 0, получим базисное решение X1 = (0, 0, 18, 16, 5, 21), которое является допустимым. Проверим его на оптимальность:

F (X1) = 0

Очевидно, что функцию F можно увеличить за счет увеличения любой из свободных переменных. Согласно 5) выбираем переменную x2.

98

Замечание. Такое правило выбора не всегда дает наименее трудоемкое решение, иногда имеет смысл провести предварительные специальные оценки.

Далее, согласно 6) составляем оценочное отношение:

x2 = min{18/3, 16/1, 5/1, ∞} = 5.

Ïðè x2 = 5 переменная x5 обращается в нуль и переходит в свободные.

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

это третье уравнение, выделяем его:

	x3	= 18		−	x1		3x2		;
x4 = 16					2x1−			x2 ;
			−			−			;
x5 = 5				−x2,
		= 21 −			3x1,
x6									.

ØÀÃ 2.

x2, x3, x4, x6 базисные, x1, x3 свободные.

Выразим новые базисные переменные через новые свободные, начиная с разрешающего уравнения

x2 = 5

x5

3(5

x5)

èëè

x2 = 5

x5

x3 = 18−

x1

x3 = 3

− x1 + 3x5

−

−

−

−

2x1 + x5

x4 = 16 −

2x1−

(5

− x5)

x4 = 11−

= 21 −

3x1

= 21 −

3x1

x5

x5

Второе базисное решение X2 = (0; 5; 3; 11; 0; 21) является допустимым. Выразим целевую функцию через свободные переменные

F = 2x1 + 3x2 = 2x1 + 3(5 − x5) = 15 + 2x1 − 3x5.

Значение целевой функции F2 = F (X2) = 15, которое не является оптимальным, так как есть возможность дальнейшего увеличения за счет переменной x1, входящей в выражение для F с положительным коэффициентом.

Составляем оценочное отношение

x1 = min{∞; 3/1; 11/2; ∞} = 3,

следовательно второе уравнение является разрешенным, переменная x3 переходит в неоснов

íûå.

ØÀÃ 3.

x1, x2, x4, x6 базисные, x3, x5 свободные.

Выражаем новые базисные переменные через новые свободные, начиная с разрешающего уравнения, после преобразований получим:

			x1 = 3 − x3 + 3x5					;
				= 5 − x5		−
		x2						;
Базисное решение		x4 = 5 + 2x1					5x5, ;
					допустимо. Выражаем целевую функцию через
		x6 = 12 + 3x3					− 9x5	, .
	X	0; 5; 0; 12)
	3	= (3; 5;

свободные переменные

F = 2x1 + 3x2 = 2(3 − x3 + 3x5) + 3(5 − x5) = 21 − 2x3 + 3x5, F3 = F (X3) = 21,

99

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

Составляем оценочное отношение

x5 = min{∞; 5; 1; 12/9} = 1,

следовательно третье уравнение разрешенное, x4 переходит в свободные.

ØÀÃ 4.

x1, x2, x5, x6 базисные, x3, x4 свободные. После преобразований, получим систему

	x1 = 6 + 1/5x3 − 3/5x4				;
		= 4 − 2/5x3	−
x2			+ 1/5x4		;
x5 = 1 + 2/5x3				1/5x4, ;
		= 3 − 3/5x3	+ 9/5x4, .
x6

Базисное решение X4 = (6; 4; 0; 0; 1; 3) допустимо, проверяем на оптимальность

F = 24 − 4/5x3 − 3/5x4, F4 = F (X4) = 24 оптимально,

так как не содержит положительных коэффициентов при свободных переменных.

В рассмотренном примере оптимальное решение получено путем перехода от первона- чального допустимого базисного решения к следующему, "лучшему и так до достижения критерия оптимальности. Однако не всегда на первом шаге получается допустимое базисное решение.

4.4.Алгоритм получения первоначального базисного решения.

1)Если каждая дополнительная переменная входит в уравнение с тем же знаком, что

èсвободный член, стоящий в правой части уравнения, то дополнительные переменные можно брать в качестве основных на I шаге. При этом получится допустимое базисное решение.

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

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

4.5.Особые случаи симплексного метода

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

2)Если на каком либо шаге решения задачи симплексным методом все оценочные

отношения имеют вид ∞, то задача не имеет конечного оптимума (Fmax = ∞, если задача на отыскание максимума, и Fmin = −∞, если задача на отыскание минимума). Геометри-

чески этот случай соответствует открытому множеству решений системы неравенств. 3) Если невозможно получить ни одного допустимого базисного решения, то задача не

имеет решения.

100