Контрольная работа по "Линейное программирование"

ТИПОВОЙ РАСЧЕТ № 1

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

Задание 1

Предприятие выпускает два вида продукции А1 и А2, используя при этом три вида сырья В1, В2 и В3. Известны запасы сырья равные b1, b2 и b3 соответственно. Расход сырья вида Вi на производство единицы продукции Aj равен ai,j. Доход от реализации единицы продукции Aj составляет cj условных единиц. Требуется составить такой план производства продукции, при котором доход будет максимальным.

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

Математическая модель

1. Переменные:

x1 – оптимальное количество продукции A1;

x2 - оптимальное количество продукции A2;

1. Критерий оптимальности: доход →max;
2. Целевая функция:

[pic 1]

1. Ограничения:

[pic 2]

[pic 3]

[pic 4]

[pic 5]

Графическое решение

Строим прямые, соответствующие нашим ограничениям. В первой координатной четверти выделяем многоугольник, в котором выполняются все ограничения. Он имеет 5 вершин. Экстремум находится или в одной из вершин или на одной из сторон многоугольника. Строим вектор нормали к линиям равного уровня целевой функции. Перемещая линию равного уровня вдоль вектора нормали, находим, что крайней точкой многоугольника является точка 3.  

[pic 6]

Она находится на пересечении линий, соответствующих 2-ому и 3-ему ограничениям. Её координаты находим, решив систему уравнений:

[pic 7]

Решение: [pic 8][pic 9]

Значение целевой функции: [pic 10][pic 11]

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

1. Переменные:

y1 – оптимальная цена единицы сырья B1;

y2 – оптимальная цена единицы сырья B2;

y3 – оптимальная цена единицы сырья B3;

1. Критерий оптимальности: общая стоимость сырья →min;
2. Целевая функция:

[pic 12]

1. Ограничения:

[pic 13]

[pic 14]

[pic 15]

Подставим оптимальные значения переменных x в систему ограничений прямой задачи:

[pic 16]

[pic 17]

[pic 18]

Поскольку первая строка является строгим неравенством,  то .[pic 19]