Тема 4: Двойственность в линейном программировании

Тема 2

Пример 1. Схема задачи использования сырья.

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

Для изготовления двух видов продукции и требуется четыре вида ресурсов (сырья): , , , . Запасы сырья - соответственно , , , единицы.

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

Решение. Для удобства сначала все данные запишем в виде таблицы:

Виды сырья	Запасы сырья	Виды продукции





Доход от реализации одной единицы продукции

Тогда на основании таблицы запишутся неравенства (ограничения):

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

Из остальных строк таблицы составим ещё 3 неравенства системы.

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

Схема задачи о питании.

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

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

Решение. Строим таблицу:

Питательные вещества	Норма	Продукты

Ж
Б
У
В
Стоимость питательных веществ

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

Запишем задачу в виде математических соотношений. В задаче неизвестно количество каждого вида продукта. Поэтому обозначим количество продукта буквой , количество продукта - буквой , количество продукта - буквой .