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

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

	С1	…	Сn
B1	a11	…	a1n
…	…	…	…
Bm	am1	…	amn

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

Математическое моделирование данной проблемы приводит к задаче линейного программирования вида (4.4):

,

где - количество выпускаемой продукции соответствующих видов.

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

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

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

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

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

Таким образом, имеем систему ограничений

.

К ним еще следует добавить смысловые ограничения неотрицательности переменных: цены не могут быть отрицательными.

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

Таким образом, мы пришли к двойственной задаче:

.

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

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

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

Задача 1

Озеро можно заселить двумя видами рыб: А и В. Средняя масса рыбы вида А равна 2 кг, а вида В - 1 кг. В озере имеется два вида пищи: Р₁ и Р₂. Средние потребности одной рыбы вида А составляют 1 ед. корма Р₁ и 3 ед. корма Р₂ в день. Аналогичные потребности для рыбы вида В составляют 2 ед. и 1 ед. Ежедневный запас пищи поддерживается на уровне 500 ед. Р₁ и 900 ед. Р₂. Как следует заселить озеро рыбами, чтобы максимизировать общую массу рыб?