korobov

211

На третьей итерации проверяем опорный план табл. 5.12 на оптимальность, для этого вычисляем потенциалы и записываем их в соответствующий столбец и строку.

Характеристики свободных клеток, вычисленные по формуле (5.47), равны

Характеристики всех свободных клеток оказались не отрицательными, следовательно, опорный план табл. 5.12 является оптимальным решением задачи. Целевая функция (5.28) достигла минимального значения.

Поскольку в оптимальном решении нет ни одной характеристики равной нулю, план табл. 5.12 является единственным оптимальным решением задачи.

В экономическом условии задачи требуется определить каждому исполнителю Аi объем производства продукции того или иного вида. Оптимальный же план (табл. 5.12) получен в часах работы исполнителей. По этим данным, а также по производительности (цифры в правом верхнем углу каждой клетки) нетрудно вычислить объемы производства продукции. В табл. 5.13 в числителе показано задание исполнителям по количеству продукции, в знаменателе - время работы (по основному оборудованию)

Табл. 5.13

Выполнение задания по выпуску всей продукции полностью обеспечивается ресурсами времени. Кроме того, у исполнителей А2 и А3 имеются резервы времени— соответственно 117,3 и 50 ч. По величине резерва времени судят о напряженности плана. Оптимальное распределение задания между исполнителями позволяет выполнить его с минимальными суммарными расходами.

Таким образом, решение задачи закончено. Как дальше использовать выявленные резервы времени—вопрос другой, и экономисты всегда найдут на него ответ.

На решении этого примера рассмотрен интересный и нужный для оптимизации планирования и управления производством алгоритм—ламбда-задачи. Не все особенности алгоритма нашли здесь отражение, так как на одном примере это невозможно сделать. Читатель в своей практике может встретиться с моментами, несколько усложняющими процесс решения. На возникшие вопросы он найдет ответ в других книгах, в которых алгоритм изложен полнее на многих примерах, например в книге И. Я. Бирмана.

Изучив алгоритм последовательного решения этого примера распределительной нетранспортной задачи (5.28-5.31), читатель может самостоятельно разработать алгоритм (для: определения исходного опорного плана, проверки плана на оптимальность, перехода к "лучшему" плану) для другой постановки задачи (5.32-5.34), которая была изложена выше. Естественно, что алгоритм решения претерпит соответствующие изменения, поскольку изменилась экономико-математическая модель задачи.

214

Глава 6. ЭЛЕМЕНТЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задачи отыскания наибольшего или наименьшего значения целевой функции на множестве допустимых планов носят название экстремальных задач. Экстремальные

задачи, в которых либо целевая функция, либо ограничения, либо то и другое нелинейны, называются задачами нелинейного программирования. Интерес даже к простейшим нелинейным задачам оптимизации вполне закономерен, ибо линейное моделирование реальных процессов осуществляется во многом числе случаев ценой весьма серьезных допущений, искажающих действительную картину явления. Например, в линейных моделях минимизации затрат предполагается, что производственные затраты пропорциональны количеству произведенной продукции. Этим делается допущение, что производственные затраты на единицу продукции (удельные затраты) не зависят от ее количества. В действительности это не так. Для большинства видов производства затраты на выпуск единицы продукции обычно уменьшаются с ростом объема производства.

Если в линейной модели минимизации производственных затрат по группе предприятий, или изделий и т. п., целевая функция имеет вид

где cj — постоянные затраты на выпуск единицы продукции; xj — количества производимой продукции,

то в действительности эта функция такого вида

размещения и концентрации производства, в которой производственные затраты зависят от объема выпуска продукции нелинейно и др.

Постановка подробной задачи (уравнение целевой функции) приведена в 5.4. Целевая функция должна представлять собой сумму приведенных затрат на

производство и транспортировку лесоматериалов, т. е. должна иметь вид:

Ограничительные условия этой задачи математически могут быть записаны следующим образом: xij ≥ 0, условие неотрицательности переменных;

215

n

xi = ∑xij ≤ ai — объем поставки продукции из пункта i всем п потребителям равен

j=1

объему производствa продукции в этом пункте, который не должен превосходить допустимой мощности;

m

∑xij = bj - каждому потребителю доставляется требуемое количество продукта.

i=1

Ниже будет показано, каким образом эту задачу можно свести к обычной транспортной задаче открытого типа, но с переменными стоимостями поставки лесоматериалов.

Если линейное программирование можно считать относительно законченным разделом математического программирования, то это ни в коей мере нельзя отнести к нелинейному программированию, которое бурно развивается и, вероятно, никогда не будет считаться законченным. В настоящее время имеется достаточно обширная переводная и отечественная литература по нелинейному программированию, которую невозможно хотя бы кратко охватить в учебном процессе. Поэтому мы постараемся лишь в весьма краткой и в то же время в доходчивой форме осветить идею и основные положения теории нелинейного программирования, применительно только к задачам оптимизации некоторых специальных классов нелинейных целевых функций при линейных ограничениях. Такого рода задачи чаще всего возникают в практических приложениях. Заметим, что задачи нелинейного программирования решаются труднее, чем задачи линейного программирования. Иногда удается свести решение некоторых задач нелинейного программирования к решению последовательного ряда линейных задач, сопровождающихся в общем случае, решением нелинейных систем уравнений. В практике иногда возникают задачи оптимизации линейных целевых функций при отсутствии ограничений или с ограничениями в виде уравнений. Методы решения таких задач известны очень давно (около 200 лет тому назад) и поэтому называются классическими методами оптимизации. На примере этих методов мы также вкратце остановимся. При очень малом количестве неизвестных в задаче (равном двум) и при условии гладкости1 функций, входящих в условие задачи, она может быть решена элементарно при помощи геометрических построений и решения в общем нелинейной системы уравнений с тремя неизвестными. С этого простого случая мы и начнем изложение элементов теории нелинейного программирования.

6.1. Геометрический способ решения задач нелинейного программирования

Задачу нелинейного программирования с двумя неизвестными x1 и x2 в общем виде можно сформулировать следующим образом. Найти наибольшее (или наименьшее) значение

Заданные функции f(x1, x2), gi(x1, x2 ), ..., gm(x1, x2) будем считать гладкими. Требование неотрицательности переменных x1≥0, x2≥0, если это необходимо, также

будем выражать в виде ограничений типа (6.6), т. е. представлять следующим образом:

216

неравенства должна быть неположительной. Всякое ограничение другого вида легко преобразуется к виду (6.6). Например, дано ограничение

x1 + x22 ≥ 3.

1 Гладкость функции означает непрерывность ее частных производных первого порядка.

Умножая это ограничение на — 1, получим

− x1 − x22 ≤ −3.

Наконец перенесение числа 3 в левую часть неравенства с обратным знаком дает неравенство вида (6.6)

3 − x1 − x22 ≤ 0.

Так же как в линейном программировании, набор значений неизвестных x1, х2 называется допустимым решением, если он удовлетворяет условиям задачи (6.6).

Множество всех допустимых решений называется допустимой областью. Каждое допустимое решение (x1, х2), геометрически изображается точкой X=(x1, х2) в прямоугольной системе координат x1Ох2. Допустимая область геометрически изобразится некоторой ограниченной или неограниченной частью координатной плоскости. Геометрическое изображение допустимой области называется ее построением. Для геометрического решения задачи необходимо прежде всего построить графически допустимую область. Но для этого надо знать, что представляет собой допустимая область каждого ограничения в отдельности, которую мы будем называть частной допустимой областью. Очевидно, допустимая область задачи (6.5), (6.6) будет представлять собой общую часть всех частных допустимых областей. Частная допустимая область, соответствующая одному ограничению gi(x1, х2)≤0 строится следующим образом. Полагая gi(x1, х2)=0 мы получаем одно неопределенное уравнение с двумя неизвестными x1, х2 . Бесчисленное множество решений этого уравнения представляет геометрическое место точек некоторой кривой L в плоскости x1Ох2. (рис. 6.1).

Обычно эта кривая разделяет плоскость на две части, в одной из которых функция g1(x1, х2) положительна (gi(x1, х2)>0), а в другой — отрицательна (gi(x1, х2)<0). На самой кривой L функция равна нулю. Таким образом, частная допустимая область представляет собой часть плоскости (ограниченной кривой L), на которой gi(x1, х2)≤0. Если

217

кривая L не замкнута, то частная, допустимая область не ограничена, если же замкнута и gi(x1, х2)<0, внутри контура, то ограничена (рис.6.2). Но как узнать по какую сторону от кривой L лежит частная допустимая область, определяемая неравенством gi(x1, х2)≤0?

Это определяется очень просто, если построить в произвольной точке контура вектор gi(x1, х2), который называется градиентом функции gi(x1, х2). Градиентом функции называется вектор, у которого координаты являются частными производными функции. Градиент функции обозначается символом , npocтавляемым перед функцией (знак называется «набла»). Иногда градиент функции обозначается через grad gi(x1, х2). Обозначение короче и поэтому наиболее употребительно. Таким образом градиент функции gi(x1, х2)—переменный двумерный вектор:

Градиент функции в заданной точке всегда направлен по нормали к линии уровня, проходящей через эту точку в сторону возрастания функции.

Нулевая линия уровня gi(x1, х2)=0 отделяет область положительных значений

Z=a2

0

Z=a1 x1

Рис.6.3

функции от области отрицательных ее значений. Поэтому частная допустимая область лежит по ту сторону от кривой L, где векторы gi(x1, х2) не располагаются.

Перейдем теперь к геометрическому изображению целевой функции Z=f(x1, х2). Если придать Z определенное фиксированное числовое значение Z = a, то мы получим одно уравнение f(x1, х2)=a с двумя неизвестными х1, х2, которому будут удовлетворять координаты точек некоторой кривой. При перемещении по этой кривой x1 и х2 будут непрерывно изменяться, но значение функции (6.5) будет оставаться постоянным, равным числу Z = a. Поэтому такая кривая называется линией уровня функции (6.5), соответствующая величине Z = a. Каждому числовому значению параметра а соответствует своя линия уровня. Таким образом, целевая функция Z =f(x1, х2) изображается на плоскости x1Ox2 семейством линий уровня (рис. 6.3).

Градиент

218

целевой функции в любой точке (x1, х2), где функция определена, направлен в сторону возрастающего уровня функции по нормали к линии уровня, проходящей через эту точку. Таким образом, построив произвольную линию уровня целевой функции и построив вектор f в какой-либо точке этой линии, мы будем знать направление возрастания функции.

Линия уровня, имеющая хотя бы одну общую точку с допустимой областью, называется допустимой линией уровня. Точка ( x1(0) , x2(0) ) допустимой области будет представлять оптимальное решение задачи, если она будет лежать на допустимой линии

x2

g3(x1,x2)=0

g1(x1,x2)=0

max Z=a’

Рис.6.4

уровня, отвечающей наибольшему значению maxZ = a' при отыскании наибольшего значения целевой функции и наименьшему minZ = a" при задаче минимизации.

х2

Рис.6.5

При геометрическом способе решения задачи приблизительное положение этой экстремальной точки легко определяется, а точное значение ее координат x1(0) и x2(0) определяется расчетом. Здесь возможны три случая, при единственности решения.

219

1. Точка ( x1(0) , x2(0) ) является внутренней точкой допустимой области. В этом случае линии уровня в окрестности этой точки замкнуты и стягиваются в точку ( x1(0) , x2(0) ), в которой f( x1(0) , x2(0) )=0. Для вычисления координат этой точки надо вычислить первые частные производные функции и приравнять их нулю. Оптимальное решение ( x1(0) , x2(0) ) найдется как решение полученной системы:

2.Точка М ( x1(0) , x2(0) ) — граничная угловая точка допустимой области (рис.6.4).

Вэтом случае точные значения ее координат найдутся как координаты точки пересечения двух смежных граничных кривых.

Например, для определения координат оптимальной М( x1(0) и x2(0) ) (рис. 6.4) надо решить систему уравнений:

g2 (x1, x2 )= 0; g3 (x1 , x2 )= 0.

3.Точка М ( x1(0) , x2(0) ) —граничная не угловая точка допустимой области (рис. 6.5).

В оптимальной точке М касательная к граничной линии g(x1, х2)=0 и к допустимой линии уровня maxZ=f(x1, х2)= a общая и поэтому будет общей и нормаль. Следовательно, векторыg(M) и f(M) имеют одинаковое направление, так как они должны лежать на нормали. Два вектора, лежащие на одной прямой, должны иметь пропорциональные координаты. Из

этого следует, что координаты x1(0) , x2(0) оптимальной точки должны удовлетворять системе трех уравнений

с тремя неизвестными — x1, х2 и λ (коэффициент пропорциональности). Третье уравнение выражает требование принадлежности точки М к соответствующей граничной линии. Итак,

для определения координат оптимальной точки М ( x1(0) , x2(0) ) надо составить систему уравнений (6.10) и затем ее решить. При этом определять число λ не обязательно, так как нас интересуют только значения координат x1(0) , x2(0) .

Пример. Рассмотрим нелинейную задачу об использовании ресурсов при изготовлении двух видов продукции P1 и Р2, в том случае когда использование некоторых видов ресурсов не пропорционально количеству продукции. К таким видам ресурсов могут относиться, например, затраты машинного времени, рабочего времени и т. д. Мы не будем здесь конкретизировать виды продукции и ресурсов, а поставим задачу в относительно общем виде.

Предположим, что для изготовления продукции P1 и Р2 требуется использование трех видов ресурсов R1, R2, R3. Располагаемое количество peсурсов и нормы их расхода на изготовление единицы каждого вида продукции известны и задаются табл. 6.1.

Табл. 6.1