Графоаналитический метод для решения задачи линейного программирования (ЗЛП)

Пример 1.3:

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

Таблица 1.1

Типы ресурсов	Нормы затрат ресурсов	Запасы ресурсов
а	б
Прибыль от 1 изделия

Решение:

Найти max f(x) = 6x₁ + 2x₂

B

f(x)

max f(x) = 12

Рис. 1.1

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

Пример 1.4:

Найти max f(x) = x₁ + x₂

f(x)

Рис. 1.2

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

Пример 1.5:

Найти max f(x) = 2x₁ + 3x₂

		f(x)

Рис. 1.3

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

Пример 1.6:

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

Стандартная форма записи ЗЛП

Каноническая форма записи ЗЛП

			х2
						(1)
				(3)
	f (x)						(4)
					(2)
							х1
							с=40
						сmax
				с=0

Рис. 1.4

Рассмотрим линии уровня:

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

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

(1) и (2)

.

(3) и (4)

.

Ответ:

Вывод:

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

2. Оптимальное решение в заданном направлении всегда достигается на крайней границе допустимой области.

3. Если в заданном направлении крайняя граница - вершина, то задача имеет единственное решение, если крайняя граница - ребро, то задача имеет множество решений.

Двойственная задача в ЛП.

Каждой задаче ЛП можно поставить в соответствие другую задачу ЛП, называемую двойственной.

Рассмотрим две задачи:

1: найти (1.13)

при этом

(1.14)

2: найти (1.15)

при этом

(1.16)

Задача (2) называется двойственной задаче (1), при этом задача (1) называется прямой задачей ЛП.

Пример1.7:

Найти max f(x) = 4x₁ + 5x₂ + 9x₃

min φ(y) =16y₁ + 25y₂

Пример 1.8:

Найти max f(x) = x₁ - 4x₂ - 3x₃

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

min φ(y)= -7y₁ + 6y'₂ - 6y''₂ + 4y₃

Конечная форма двойственной задачи:

y₂ = y'₂ - y''₂

min φ(y) = -7y₁ + 6y₂ + 4y₃

Пример 1.9:

найти max f(x) = -6x₁ - 10x₂

найти max f(x) = -6x₁ - 10

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

найти min φ(y) = -10y₁ + 4y₂

Правила и особенности перехода к двойственной задаче.

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

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

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

4. Направление знаков неравенств коэффициентов прямой задачи противоположно направлению знаков неравенств двойственной задачи.

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

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

7. Требование максимизации в прямой задаче заменяется минимизацией в двойственной задаче.

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

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