«Методы оптимальных решений» (стр. 5 )

Задание 2. Решение задач линейного программирования графическим методом

Рассмотрим алгоритм графического метода для ЗЛП, содержащих не более двух переменных и имеющих вид (2.1) , , (1.2) , . (2.3) Алгоритм графического метода рассмотрим на примере применительно к задаче: 1 шаг. Строим область допустимых решений - область Р, т. е. геометрическое место точек, в котором одновременно удовлетворяются все ограничения ЗЛП. Каждое из неравенств (1-5) системы ограничений нашей задачи геометрически определяет полуплоскость соответственно с граничными прямыми Условия неотрицательности переменных 6) ограничивают область допустимых решений первым квадратом. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных. Построим первую прямую . Для этого запишем уравнение в виде: . При такой форме записи в знаменатели показаны отрезки, которые отсекает прямая на осях координат, поэтому прямая будет проходить через две точки (0;15) и (15;0). Если от уравнения перейти к неравенству: , то его можно представить графически в виде полуплоскости. Часть плоскости, которая удовлетворяет неравенству, будет лежать по левую сторону от этой прямой, как показано стрелкой. Эта полуплоскость является областью допустимых решений (см. рис. 2.1). Рис. 2.1 Алгоритм построения остальных прямых-ограничений аналогичен и результат построения показан на рис. 2.2. Рис. 2.2 Если система неравенств совместна, то область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Полученное таким образом область допустимых решений Р - планов ЗЛП есть многоугольник ABCDE - замкнутое, ограниченное, выпуклое множество с пятью крайними или угловыми точками: A, B, C, D, E. 2 шаг. Строим вектор градиент целевой функции . В условиях примера . Напомним, что этот вектор указывает направление возрастания целевой функции. 3 шаг. Строим прямую - линию уровня (т. е. линию, где функция принимает постоянное значение, ), перпендикулярную вектору-градиенту . Результаты построений, соответствующие 2 и 3 шагу приведены на рис. 2.3. Рис. 2.3 4 шаг. Линию уровня целевой функции передвигаем вдоль градиента (в случае её максимизации) или вдоль антиградиента (в случае её минимизации) до тех пор, пока она в какой-нибудь из крайних (или угловых) точек не покинет область Р. Координаты этой точки (функция в ней будет иметь максимальное или минимальное значение) являются оптимальным планом или решением задачи (см. рис. 2.4). Крайняя точка С - точка минимума , лежит на пересечении прямых (3) и (5). Она имеет координаты (2;10), что означает . Подставляя эти значения в целевую функцию, найдем . Рис. 2.4 Отметим, что если допустимая область решений Р представляет собой неограниченную область и прямая (линия уровня целевой функции) при движении в направлении вектора (или противоположном ему) не покидает Р, то в этом случае не ограничена сверху (или снизу), т. е. или . Решить задачу линейного программирования в соответствии с номером в журнале группы.

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

Пример. Симплекс-методом решить ЗЛП:

(3.1)

при наличии ограничений:

(3.1)

, . (3.2)

Приводим систему линейных неравенств (3.1) к каноническому виду, вводя в каждое неравенство дополнительную переменную , . Получим систему линейных уравнений:

(3.3)

Целевая функция принимает вид

(3.4)

Расширенная матрица

системы линейных уравнений (3.3) является исходной К-матрицей ЗЛП, которая определяет исходный опорный план:

, .

Кроме того, .

Результаты последовательных итераций симплекс-алгоритма удобно оформить в виде симплекс-таблицы (см. табл. 3.1).

Таблица 3.1

S	i				3	2	0	0	0	0
	1	2	3	4	5	6
0	1 2 3 4	3 4 5 6	0 0 0 0	6 8 1 2	1 2 -1 0	2 1 1 1	1 0 0 0	0 1 0 0	0 0 1 0	0 0 0 1	6 4 - -
		-3	-2	0	0	0	0	k=1 l=2
1	1 2 3 4	3 1 5 6	0 3 0 0	2 4 5 2	0 1 0 0	3/2 1/2 3/2 1	1 0 0 0	-1/2 1/2 1/2 0	0 0 1 0	0 0 0 1	4/3 8 10/3 2
		0	-1/2	0	3/2	0	0	k=2 l=1
2	1 2 3 4	2 1 5 6	2 3 0 0	4/3 10/3 3 2/3	0 1 0 0	1 0 0 0	2/3 -1/3 -1 -2/3	-1/3 2/3 1 1/3	0 0 1 0	0 0 0 1
		0	0	1/3	4/3	0	0

На второй итерации S = 2, все , следовательно, опорный план