1.1.4. Определение задачи линейного программирования. (злп)

ЗЛП состоит в максимизации (минимизации) линейной функции при линейных ограничениях.

Пример 1.1:

найти (1.3)

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

(1.4)

ЗЛП, записанная в виде (1.3) и (1.2), называется общей задачей ЛП, заданной в произвольной форме записи.

Любую ЗЛП можно записать в виде:

найти при условиях , но при этом вводится дополнительное условие:

(1.5)

(1.3) и (1.5) - стандартная форма записи ЗЛП

Любую ЗЛП можно представить в виде:

найти (1.6)

при

(1.7)

(1.6) и (1.7) - представляют собой каноническую форму записи ЗЛП.

ЗЛП в произвольной постановке всегда может быть приведена к стандартной и канонической формам с помощью следующих преобразований ( - знак преобразования):

1. ; (1.8)

2. ; (1.9)

3. если , то; (1.10)

4. ; (1.11)

^~ - означает, что эту переменную дополнительно вводят.

5. (1.12)

Преобразования 3-5 приводят к увеличению размера задачи.

Пример 1.2:

В стандартной форме:

В канонической форме:

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

Пример 1.3:

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

Таблица 1.1

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

Решение:

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

B

m

f(x)

ax f(x) = 12

C

Рис. 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. Если в заданном направлении крайняя граница - вершина, то задача имеет единственное решение, если крайняя граница - ребро, то задача имеет множество решений.