Линейное программирование

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Задание № 1.

Вариант № 2

Для указанной содержательной постановке задачи

1. Составить ее математическую модель в виде задачи ЛП;
2. Решить полученную задачу ЛП графически;
3. Решить эту задачу ЛП симплекс-методом;
4. Составить двойственную задачу ЛП и найти оптимальное решение этой задачи, используя теоремы двойственности.

Условия:

Вариант 2. Фирма изготовляет два вида красок для внутренних (В) и наружных (Н) работ. Для их производства используют исходные продукты: пигмент н олифу. Расходы исходных продуктов и максимальные суточные запасы указаны в таблице. Изучение рынка сбыта показало, что суточный спрос на краску для наружных работ никогда не превышает 4 г в сутки. Цена продажи 1 г краски для наружных работ - 3 у.е.. для внутренних - 2 у.е. Какое количество краски каждого вида должна производить фирма, чтобы доход от реализации был максимальным?

Решение: 

1. Составить ее математическую модель в виде задачи ЛП;

Решение: Составим математическую модель задачи. Обозначим через x1 количество краски для внутренних работ, а через x2 – количество краски для наружных работ. Тогда вектор [pic 1] характеризует количество краски, производимой в сутки. Этот план должен удовлетворять следующим ограничениям, связанным запасами ресурсов:

[pic 2]

Суммарный доход от реализации всех видов краски, произведенной в соответствии с планом [pic 3], выражается линейной функцией

[pic 4]

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

[pic 5]

I. Строим область D, заданную следующими ограничениями:

[pic 6]

Заштриховав  область D, берем любую точку. В данном случае, начало координат.

[pic 7]

II. Строим градиент

[pic 8]

III. Строим линию уровня, перпендикулярную градиенту. Линия уровня – это

[pic 9].

Примем С=0 для того, чтобы остались одни переменные.

[pic 10]

Прямая f(x) = const пересекает область в точке Е. Так как точка Е получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:

[pic 11]

Решив систему уравнений, получим: x1 = 4/3, x2 =8/3

Откуда найдем максимальное значение целевой функции:

[pic 12]

3. Решить эту задачу ЛП симплекс-методом.

Решим симплекс-методом задачу линейного программирования. Выполним переход к канонической форме введением дополнительных переменных (неотрицательных):

[pic 13]

Разрешим систему относительно введенных относительных переменных. Т.к. расход сырья

[pic 14]

Составим симплекс-таблицу, полагая [pic 15]-базисными переменными, а [pic 16]-свободными переменными.

[pic 17]

Окончательный вариант симплекс-таблицы:

Таблица отвечает оптимальному опорному плану т.к. в строке целевой функции нет отрицательных чисел. Оптимальный план можно записать так:

[pic 18]

4. Составить двойственную задачу ЛП и найти оптимальное решение этой задачи, используя теоремы двойственности.