 |
Решение задач линейного программирования графическим методом
|
|
|
|
Решение задачи линейного программирования графическим методом производится по следующему алгоритму:
1. Интерпретируется система ограничений. Строится область допустимых решений.
2. Строится произвольная линия уровня.
Замечание: При решении ЗЛП графическим методом удобнее всего строить линию уровня при Z=0.
3. Выбирается направление перемещения линии уровня.
Замечание1: Направление перемещения линии уровня выбирается с учетом направления наибольшего изменения функции. Это направление определяется с помощью градиента:
grad Z = 
=(
, 
)
Если решается задача на max, то выбирается направление вектора градиента (направление вектора ). В противном случае – направление антиградиента (вектора - 
).
Замечание 2: С помощью вектора 
можно построить линию уровня. Она строится перпендикулярно градиенту, через точку (0,0).
4. Перемещается линия уровня, до тех пор, пока не найдено решение ЗЛП.
Замечание 1: При решении ЗЛП возможны следующие случаи:
Рис. 8 Рис. 9.
Рис. 10 Рис. 11
На рис. 8 показан случай, когда минимум и максимум целевой функции найдены и находятся соответственно в точках max и min. Во втором случае (рис. 9) минимум целевой функции существует. Однако область допустимых решений не ограничена сверху, следовательно, максимума у целевой функции нет. В третьем случае (рис. 10) нет ни минимума, ни максимума функции. На рис.11 ЗЛП имеет бесконечно много решений.
Пример1: Решить ЗЛП графическим методом. Найти:
при
Решение.
Найдем градиент: 
(2;-3).
Построим область допустимых значений. Для этого построим прямые, соответственные ограничениям:
| 1: | A | B | 2: | A | B | 3: | A | B | ||
| -6 | 
|
| |||||||
| 
|
|
|
|
|
| y | |||||||||||||||
| x | |||||||||||||||
| C | |||||||||||||||
Решение находится, исходя из решения системы:
Тогда: 
= 
; 
= 
и max Z= –
Ответ: Z= – в 
.
Пример 2. Решить ЗЛП графическим методом. Найти:
при
Решение.
Задачи, представленные в канонической форме можно решать графическим методом только в том случае, если разность между порядком и рангом системы ограничений равна 2. В данном случае: 5-3=2.
Представим задачу таким образом, чтобы можно было решать графическим методом. Для этого в системе ограничений выразим переменные 
, 
и 
через и .
|
|
|
Так как все переменные неотрицательны, то можно составить систему неравенств:
Подставим в целевую функцию вместо , и соответственные значения:
Таким образом, ЗЛП имеет вид:
при
Найдем градиент: (1;1).
Построим область допустимых значений. Для этого построим прямые, соответственные ограничениям:
| 1: | A | B | 2: | A | B | 3: | A | B | ||
|
|
|
| -5 | |||||||
|
|
|
|
| y | |||||||||||||||
| x | |||||||||||||||
Область допустимых решений не ограничена сверху. Значит, решений нет.
Ответ: Решений нет.
|
|
|
A) устный или письменный запрет, наложенный на какое-либо решение управомоченным на то органом или лицом
E) тело, размерами которого можно пренебречь в условиях данной задачи
I Приклади розв’язання задач
I ЭТАП. Постановка задачи
I. ОСНОВНІ ЗАДАЧІ І НАПРЯМКИ САМОСТІЙНОЇ НДР СТУДЕНТІВ
I. Цели и задачи учебной дисциплины
I. Цель задачи дисциплины «История государства и права зарубежных стран»
II Анализ задачного материала
II Раздаточный материал из сборника задач по технологии горячей и холодной прокатки стали и сплавов. Протасов А.А. Изд-во «Металлургия» М.1972, 320 с.
II. Задачи работы с классом
