- Дайте алгоритм графического
метода решения задач линейного программирования.
Существуют два наиболее распространенных
способа решения задач линейного программирования
(ЗЛП): графический метод и симплекс-метод.
Графический метод существенно нагляднее
и обычно проще для понимания и решения
(хотя занимает много времени, так как
требует тщательного построения чертежа).
Также этот метод позволяет практически
одновременно найти решение на минимум
и максимум, тогда как симплекс-методом
придется делать "два подхода".
Основные шаги по решению
ЗПЛ графическим методом следующие: построить
область допустимых решений задачи (выпуклый
многоугольник), который определяется
как пересечение полуплоскостей, соответствующих
неравенствам задачи, построить линию
уровня целевой функции, и, наконец, двигать
линию уровня в нужном направлении, пока
не достигнем крайней точки области - оптимальной
точки (или множества). При этом можно найти
единственное оптимальное решение (точку),
множество (отрезок) или ни одного (область
пустая или не ограниченная в нужном направлении).
- Дайте постановку
задачи об использовании ресурсов и постройте
соответствующую модель.
1. Задача об оптимальном
использовании ресурсов при производственном
планировании.
Общий смысл задач этого класса
сводится к следующему.
Предприятие выпускает n различных
изделий. Для их производства требуется
m различных видов ресурсов (сырья, материалов,
рабочего времени и т.п.). Ресурсы ограничены,
их запасы в планируемый период составляют,
соответственно, b1, b2,..., bm условных единиц.
Известны также технологические
коэффициенты aij, которые
показывают, сколько единиц i-го ресурса
требуется для производства единицы изделия
j-го вида (
).
Прибыль, получаемая предприятием
при реализации изделия j-го вида, равна
cj.
В планируемом периоде значения
величин aij, bi и cj остаются постоянными.
Требуется составить такой
план выпуска продукции, при реализации
которого прибыль преприятия была бы наибольшей.
Далее приведем простой пример
задачи такого класса.
Компания специализируется
на выпуске хоккейных клюшек и наборов
шахмат. Каждая клюшка приносит компании
прибыль в размере $2, а каждый шахматный
набор - в размере $4. На изготовление одной
клюшки требуется четыре часа работы на
участке A и два часа работы на участке
B. Шахматный набор изготавливается с затратами
шести часов на участке A, шести часов на
участке B и одного часа на участке C. Доступная
производственная мощность участка A составляет
120 н-часов в день, участка В - 72 н-часа и
участка С - 10 н-часов.
Сколько клюшек и шахматных
наборов должна выпускать компания ежедневно,
чтобы получать максимальную прибыль?
Условия задач указанного класса
часто представляют в табличной форме
(см. таблицу 2.1).
Таблица 2.1 - Исходные данные
задачи об использовании производственных
ресурсов
производственные
участки |
затраты времени
на единицу продукции, н-час |
доступный фонд
времени, н-час |
клюшки |
наборы шахмат |
А |
4 |
6 |
120 |
В |
2 |
6 |
72 |
С |
- |
1 |
10 |
прибыль на единицу
продукции, $ |
2 |
4 |
|
По данному условию сформулируем
задачу линейного программирования.
Обозначим: x1 - количество
выпускаемых ежедневно хоккейных клюшек,
x2 количество
выпускаемых ежедневно шахматных наборов.
Формулировка ЗЛП:
= 2x1 + 4x2 → max; |
|
|
4x1 + 6x2≤ 120,
2x1 + 6x2 ≤ 72,
x2 ≤ 10; |
|
|
x1 ≥ 0, x2 ≥ 0. |
|
Подчеркнем, что каждое неравенство
в системе функциональных ограничений
соответствует в данном случае тому или
иному производственному участку, а именно:
первое - участку А, второе - участку В,
третье - участку С.
- Опишите метод последовательного
улучшения плана задач линейного программирования.
В отдельных случаях, когда
число неизвестных в ограничениях и целевой
функции не более трёх, задачу линейного
программирования удаётся решить с помощью графического метода.
Этот метод позволяет наглядно описать
область допустимых решений, критерий
оптимальности и процесс получения оптимального
решения путём последовательного приближения
по допустимым вариантам.
Не уменьшая общности, рассмотрим
двумерный случай, когда задача линейного
программирования зависит от двух переменных
−
и
Как известно, в этом случае система
линейных ограничений задачи задаёт на
плоскости многоугольное множество, и
поскольку целевая функция
является линейной, она не имеет экстремума
внутри многоугольника. Экстремум
достигается на границе области допустимых
решений, т. е. в одной из вершин многоугольника.
Алгоритм графического метода
решения задачи линейного программирования
рассмотрим на следующем примере.
Пример. Найти решение системы неравенств
-
максимизирующее (минимизирующее)
функцию
. На неизвестные
накладываются условия неотрицательности.
Решение. Рассмотрим данную задачу как
задачу линейного программирования.
1. Построим по системе
ограничений и условиям неотрицательности
область допустимых решений задачи (рис.
6.1). В результате построения получился
пятиугольник ABCDE, расположенный
в первом квадранте, т.е. удовлетворяющий
условиям неотрицательности, наложенным
на неизвестные
.
2. По уравнению целевой
функции
определяем координаты вектора нормали
(координаты вектора нормали равны
соответствующим коэффициентам при неизвестных
в целевой функции или пропорциональны
им). На той же координатной плоскости,
где изображён многоугольник допустимых
решений, строим вектор нормали
и линию уровня
перпендикулярную этому вектору и
проходящую через начало координат О (линия
уровня заштрихована).
3. Передвигая линию уровня
параллельно самой себе в направлении
возрастания вектора
, в первой пересекаемой ею вершине
многоугольника допустимых решений получим
минимальное значение целевой функции,
а в последней пересекаемой вершине –
максимальное.
Таким образом, функция
достигает минимум в точке D, а максимум
– в точке А.
Найдём координаты точек D и А из решения
систем линейных уравнений:
Определим соответствующие
экстремальные значения целевой функции:
start="5"
Рис. 6.1. Графический метод решения
задачи линейного программирования