5.1. Задача оптимальной загрузки транспортного устройства
На
производстве имеется транспортная
система, обслуживающая
единиц ТО (рис. 23). Транспортная система
характеризуется грузоподъемностью Р
и полезным объемом V
. На каждую
-ю
единицу ТО транспортная система должна
поставить детали
-го
типа, характеризующиеся массой
,
и объемом
.
Полезность перевозки детали
-го
типа
по заданному маршруту пропорциональна
производительности ТО, для которого
она предназначена,
,
т.е. чем больше производительность ТО,
тем большее количество деталей необходимо
к нему доставить.
Задача
состоит в том, чтобы определять количество
деталей
-го
типа,
,
которое необходимо загрузить в
транспортное устройство, чтобы полезность
перевозки деталей была бы максимальной.
При этом загрузка всего ТО также будет
максимальной. Подобные задачи относятся
к задачам математического программирования.
В качестве
целевой функции, очевидно,
следует выбрать суммарную полезность
перевозки деталей
.
Ограничения на независимые переменные устанавливается по грузоподъемности и полезному объему транспортного устройства. Ограничение по грузоподъемности заключается в том, что суммарная масса деталей, перевозимых транспортным устройством, не должна превышать его грузоподъемности
.
Ограничение по полезному объему аналогично
.
В данном случае и целевая функция и ограничения является линейными, поэтому задача математического программирования относится к задачам линейного программирования.
5.2. Геометрическая интерпретация задачи линейного программирования
Задача линейного программирования имеет простую геометрическую интерпретацию. В евклидовом -мерном пространстве система ограничений определяет некоторый выпуклый многогранник (рис.24). Для выяснения геометрической сущности целевой функции приравняем ее нулю
.
Полученное
уравнение определяет в
-мерном
пространстве гиперплоскость, проходящую
через начало координат перпендикулярно
вектору
при
(рис.24а).
Для
нахождения максимума необходимо
гиперплоскость
отодвинуть
параллельно самой себе в направлении
вектора
как можно дальше от начала координат,
но так, чтобы с областью допустимых
решений оставалась хотя бы одна общая
точка R
. Аналогично, минимум будет находиться
в точке S
. На этом основан графический метод
решения задачи с двумя неизвестными
Если
гиперплоскость параллельна ребру или
грани области
,
то решений будет бесчисленное множество
- все точки ребра или грани (рис.24,б).
Если множество
не ограничено сверху, то гиперплоскость
можно передвигать сколь угодно далеко
(рис.25,а). Функционал в данном случае не
ограничен и задачу на
решить невозможно, хотя на
задача решается. В случае, если не
введены ограничения снизу, в том числе
и
,
то подобная ситуация может сложиться
при решении задачи на минимум (рис.25,б).
При условии
значения
функционала снизу всегда ограничены
нулем.
Понятно, что графически задача решается только на плоскости, размерность которой равна двум. Для более сложных случаев разработан специальный метод нахождения экстремумов – симплекс-метод. В основе его лежит то свойство задачи,что система ограничений определяет в -мерном евклидовом пространстве выпуклый многогранник, в одной из вершин которого достигается экстремум целевой функции.
Это обстоятельство дает возможность не испытывать на оптимальность все бесчисленное множество точек многогранника, а ограничиваться только перебором его вершин. Отсюда выявляется способ решения задачи - определить любую вершину многогранника, а затем от вершины к вершине добираться до нужной точки, т.е. до экстремума.
Для примера рассмотрим решение следующей задачи линейного программирования. Целевая функция задается в виде
,
а ограничения
,
,
;
.
Геометрическая
интерпретация этой задачи приведена
на рис.26. Вектор градиента Р
целевой функции имеет направляющие
проекции [1,1]. Точка R
определяет экстремум целевой функции,
который достигается при
и
.
