Многомерные задачи оптимизации (стр. 5 из 6)
Основываясь на введенных понятиях, рассмотрим геометрический метод решения задачи линейного программирования. Пусть заданы линейная целевая функция
двух независимых переменных, а также некоторая совместная система линейных неравенств, описывающих область решений 
. Требуется среди допустимых решений 
найти такое, при котором линейная целевая функция 
принимает наименьшее значение.Положим функцию
равной некоторому постоянному значению 
. Это значение достигается в точках прямой, удовлетворяющих уравнению 
(4.5)При параллельном переносе этой прямой в положительном направлении вектора нормали
линейная функция будет возрастать, а при переносе прямой в противоположном направлении — убывать.Действительно, пусть при параллельном переносе точка
, принадлежащая прямой (4.5), переходит в точку 
, принадлежащую новой прямой, т. е. параллельный перенос производится в направлении вектора 
. Тогда уравнение новой прямой будет иметь вид 
Поскольку
Если вектор
сонаправлен с вектором 
, то 
и 
, а если направлен противоположно, то 
.Предположим, что прямая, записанная в виде (4.5), при параллельном переносе в положительном направлении вектора первый раз встретится с областью допустимых решений
в некоторой ее вершине, при этом значение целевой функции равно 
, и прямая становится опорной. Тогда значение будет минимальным, поскольку дальнейшее движение прямой в том же направлении приведет к увеличению значения .Если в задаче оптимизации нас интересует максимальное значение целевой функции, то параллельный перенос прямой (4.5) осуществляется в направлении, противоположном
, пока она не станет опорной. Тогда вершина многоугольника, через которую проходит опорная прямая, соответствовать максимуму функции . При дальнейшем переносе прямой целевая функция будет убывать.Таким образом, оптимизация линейной целевой функции на многоугольнике допустимых решений происходит в точках пересечения этого многоугольника с опорными прямыми, соответствующими данной целевой функции. При этом пересечение может быть в одной точке (в вершине многоугольника) либо в бесконечном множестве точек (на ребре многоугольника). В последнем случае имеется бесконечное множество оптимальных решений.
В распоряжении бригады имеются следующие ресурсы: 300 кг металла, 100 м2 стекла, 160 чел.-ч. (человеко-часов) рабочего времени. Бригаде поручено изготовить два наименования изделий: А и Б. Цена одного изделия А -1 тыс. р., для его изготовления необходимо 4 кг металла, 2 м2 стекла и 2 чел.-ч. рабочего времени. Цена одного изделия Б 1,2 тыс. для его изготовления необходимо 5 кг металла, 1 м2 стекла и 3 чел.-ч. рабочего времени. Требуется так спланировать объем выпуска продукции, чтобы ее стоимость была максимальной.
Сначала сформулируем задачу математически. Обозначим через
и 
количество изделий А и Б, которое необходимо запланировать (т.е. это искомые величины). Имеющиеся ресурсы сырья и рабочего времени зададим в виде ограничений-неравенств: 
(4.6)Полная стоимость запланированной к производству продукции выражается формулой
(4.7)Таким образом, мы имеем задачу линейного программирования, которая состоит в определении оптимальных значений проектных параметров
являющихся целыми неотрицательными числами, удовлетворяющих линейным неравенствам (4.6) и дающих максимальное значение линейной целевой функции (4.7).Вид сформулированной задачи не является каноническим, поскольку условия (4.6) имеют вид неравенств, а не уравнений. Как уже отмечалось выше, такая задача может быть сведена к канонической путем введения дополнительных переменных
по количеству ограничений- неравенств (4.6). При этом выбирают эти переменные такими, чтобы при их прибавлении к левым частям соотношений (4.6) неравенства превращались в равенства. Тогда ограничения примут вид 
(4.8)При этом очевидно, что
. Заметим, что введение дополнительных неизвестных не повлияло на вид целевой функции (4.7), которая зависит только от параметров . Фактически будут указывать остатки ресурсов, не использованные в производстве. Здесь мы имеем задачу максимизации, т. е. нахождения максимума целевой функции. Если функцию (4.7) взять со знаком минус и принять целевую функцию в виде 
(4.9)то получим задачу минимизации для этой целевой функции.
Примем переменные
в качестве базисных и выразим их через свободные переменные из уравнений (4.8). Получим 
(4.10)В качестве опорного решения возьмем такое, которое соответствует пулевым значениям свободных параметров:
Этому решению соответствует нулевое значение целевой функции (4.9):
(4.11)Исследуя полученное решение, отмечаем, что оно не является оптимальным, поскольку значение целевой функции (4.9) может быть уменьшено по сравнению с (4.11) путем увеличения свободных параметров.
Положим
и будем увеличивать переменную до тех пор, пока базисные переменные остаются положительными. Из (4.10) следует, что можно увеличить до значения 
, поскольку при большем его значении переменная 
станет отрицательной (отношение 100/(-2) является наименьшим по модулю среди отношений 300/(-4),100/(-2),160/(-2)).Таким образом, полагая
, , получаем новое опорное решение (значения переменных найдем по формулам (4.10)): 
(4.12)Значение целевой функции (4.9) при этом будет равно
(4.13)