Линейное программирование: формулировка задач и их графическое решение

Задача ЛП

Рассмотрим на примере задачи фирмы Reddy Mikks. Небольшая фабрик изготовляет два вида красок: для наружных (E) и внутренних (I) работ. Продукция поступает в оптовую продажу. Для производства красок используется два исходных продукта — A и B. Максимально возможные суточные запасы этих продуктов составляют 6 т и 8 т соответственно. Расходы A и B на производство 1 т соответствующих красок приведены в таблице.

Суточный спрос на краску I никогда не превышает спроса на краску E более чем на 1 т. Спрос на I не превышает 2 т. Оптовая цена за 1 т краски E — 3000 $, I — 2000 $. Какое количество краски каждого вида фабрика должна производить, чтобы доход от реализации продуктов был максимальным?

Так как нужно определить объём производства каждого вида краски, переменными в модели являются:

xE — суточный объём производства краски E (в тоннах);

xI — суточный объём производства краски I (в тоннах).

Обозначив доход (в тыс. $) через, можно дать математическую формулировку целевой функции: определить (допустимые) значения xE и xI, максимизирующие величину общего дохода.

Ограничения на расход исходных продуктов:

• (для A)
• (для B)

Ограничения на величину спроса на продукцию:

Потребуем выполнения условия неотрицательности переменных:

Получили математическую модель:

Определить суточные объёмы производства (в т.) краски I и E, при которых достигается.

(целевая функция) при ограничениях.

Графическое решение задачи ЛП

Построим область допустимых решений, в которой одновременно выполняются все ограничения. Искомое пространство решений — многоугольник ABCDEF. Пространство решений содержит бесконечное число точек, являющихся допустимыми решениями, но, несмотря на это, можно найти оптимальное решение, если выяснить, в каком направлении возрастает целевая функция модели z=3xE+2xI. На график наносят ряд параллельных линий, соответствующих уравнению целевой функции при нескольких произвольно выбранных и последовательно возрастающих значениях, что позволяет определить наклон целевой функции и направление её увеличения. На видно, что оптимальному решению соответствует точка C, являющаяся пересечением прямых.

Решив систему, получим.

Тогда получаемый доход тыс $.

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