ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 29.12.2025
Просмотров: 36
Скачиваний: 0
Задача скачана с сайта www.MatBuro.ru
© МатБюро - Решение задач линейного программирования, ЭММ и т.п.
Тема: Графический метод решения задачи линейного программирования
ЗАДАНИЕ. Решить задачу графическим методом
x − 2 y → min, max
5x + 3y ³ 30,
x - y £ 3,
-3x + 5 y £ 15, x ³ 0, y ³ 0.
РЕШЕНИЕ. Построим область допустимых решений задачи, ограниченную неравенствами
5x + 3y ³ 30,
x - y £ 3,
- 3x + 5 y £15, x ³ 0, y ³ 0.
Строим прямые (по двум точкам каждую):
(I ) |
5x + 3y = 30 , точки (6, 0), |
(0, 10). |
(II ) |
x − y = 3, точки (3, 0), (6, |
3). |
(III ) |
−3x + 5 y = 15, точки (0, 3), (5, 6). |
|
Штриховкой выделяем нужные полуплоскости, соответствующие знакам неравенств.
1
Задача скачана с сайта www.MatBuro.ru
© МатБюро - Решение задач линейного программирования, ЭММ и т.п.
На пересечении всех полуплоскостей получаем ограниченную выпуклую область ABC (закрашена на чертеже).
Строим линию уровня целевой функции x − 2 y = 0 и вектор градиента n = (1, −2) . Двигаем линию уровня параллельно себе по направлению градиента (и против направления градиента) (см. рисунок), пока не войдем в область и не выйдем из области.
Видно, что выход из области (максимум целевой функции) произойдет в точке
пересечения прямых (I ) и ( II ) , она имеет координаты C |
39 |
; |
15 |
|
, так как: |
|||
|
|
|||||||
|
5(3 + y ) + 3y = 30, |
|
8 8 |
|
||||
5x + 3y = 30, |
8 y = 15, |
y = 15 / 8, |
|
|
||||
|
|
|
|
|
|
|||
x − y = 3, |
x = 3 + y, |
x = 3 + y, |
x = 39 / 8. |
|
|
|||
|
|
|
|
|
|
|
|
|
2
Задача скачана с сайта www.MatBuro.ru
© МатБюро - Решение задач линейного программирования, ЭММ и т.п.
Таким образом, максимум целевой функции Fmax |
|
39 15 |
|
|
39 |
|
15 |
|
9 |
|
|||
= F |
|
; |
|
|
= |
|
- 2 × |
|
|
= |
|
= 1,125. |
|
|
|
|
|
|
|
||||||||
|
|
8 8 |
|
|
8 |
|
8 |
|
8 |
|
|||
Видно, что вход в область (минимум целевой функции) произойдет в точке
B (15;12) . Таким образом, минимум целевой функции Fmin = F (15;12) =15 - 2 ×12 = -9.
3