Часть 4. Задача линейного программирования

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

Задача №1. Для производства двух препаратов A и B химическое производство использует три вида сырья:

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

Обозначим х₁-количество стандартов препарата А, х₂-количество стандартов препаратаВ.

Целевая функция (общая прибыль) оптимизируется на максимум Q=30x₁+40x₂ max.

По каждому виду сырья составляются ограничения в форме неравенств, а на переменные накладывается условие неотрицательности:

Алгоритм графического решения ЗЛП:

1) строят прямые линии по условиям-ограничениям;

2) находят полуплоскости, определяемые каждым ограничением;

3) находят многоугольник решений (пересечение полуплоскостей);

4) строят систему параллельных линий Q=const, проходящих через многоугольник;

5) находят точку, в которой значение целевой функции Q максимально;

6) определяют оптимальный план (х₁^*;х₂^*) и значение целевой функцииQ для оптимального плана.

Решим задачу №1 графически согласно приведенному алгоритму:

- неравенства заменим на равенства

- строим соответствующие прямые; - определяем полуплоскости по отношению к началу координат О(0;0); - заштриховываем область пересечения полученных полуплоскостей; - строим вектор , который указывает направление перемещения прямой - перемещая прямую в направлении вектора , видим, что макс. значение целевая функция принимает в точке “B”

- определяем координаты точки В, решив систему:

х^* = (12;18) – оптимальный план.

- максимальная прибыль: Q_max = 30 · 12 + 40 · 18 = 1080 усл. ед.).

Прямая Q=constможет пересекать допустимую область в точке, по лучу, по отрезку. Допустимая область не всегда является ограниченной областью.

Индивидуальное задание №4

Решить задачи с двумя переменными графическим методом (табл. 1) в соответствии со своим номером в списке группы.

Таблица 1. Варианты задания 1

Вариант	Задача	Вариант	Задача
1		6
2		7
3		8
4		9
5		10
11		17
12		18
13		19
14		20
15		21
16		22
23		27
24		28
25		29
26		30