Графический способ решения задачи линейного программирования
Рассмотрим графический метод решения на следующем примере.
Задача. Для производства двух препаратов A и B химическое производство использует три вида сырья:
Виды сырья
|
Норма расхода сырья(кг/стандарт)
|
Общее количество сырья(кг)
|
А
|
В
|
I
II
III
|
12
4
3
|
4
4
12
|
300
120
252
|
Прибыль от реализации 1 стандарта(усл.ед/станд)
|
30
|
40
|
|
Необходимо составить план выпуска, при котором прибыль от реализации выпущенной продукции будет максимальна.
Обозначим х1-количество стандартов препарата А, х2-количество стандартов препарата В.
Целевая функция (общая прибыль)оптимизируется на максимум Q=30x1+40x2 max.
По каждому виду сырья составляются ограничения в форме неравенств, а на переменные накладывается условие неотрицательности:
Алгоритм графического решения ЗЛП:
строят прямые линии по условиям-ограничениям;
находят полуплоскости, определяемые каждым ограничением;
находят многоугольник решений (пересечение полуплоскостей);
строят систему параллельных линий Q=const, проходящих через многоугольник;
находят точку, в которой значение целевой функции Q максимально;
определяют оптимальный план (х1*;х2*) и значение целевой функцииQ для оптимального плана.
Решим задачу №1 графически согласно приведенному алгоритму:
- неравенства заменим на равенства
(1)
(2)
(3)
- строим соответствующие прямые;
- определяем полуплоскости по отношению к началу координат О(0;0);
- заштриховываем область пересечения полученных полуплоскостей;
- строим вектор , который указывает направление перемещения прямой
- перемещая прямую в направлении вектора , видим, что макс. значение целевая функция принимает в точке “B”
- определяем координаты точки В, решив систему:
х* = (12;18) – оптимальный план.
- максимальная прибыль: Qmax = 30 · 12 + 40 · 18 = 1080 усл.ед.).
Прямая Q=constможет пересекать допустимую область в точке, по лучу, по отрезку. Допустимая область не всегда является ограниченной областью.
Задание 1. Решить задачу с двумя переменными графическим методом в соответствии со своими индивидуальными данными (m – число гласных букв в фамилии студента, n – число гласных букв в полном имени студента, k – число гласных букв в отчестве студента).
Достарыңызбен бөлісу: |