Дробно - линейное программирование.

Таблица

Таблица

Таблица

Таблица

Таблица

Таблица

Таблица

Таблица

Таблица

Таблица 3.5

Начальная симплекс – таблица

Таблица 3.4

Базис	Переменные	Свободный член
. . . . . .	. . . . . .	. . . . . .
	……

Рассмотрим переход от симплекс – таблицы, соответствующей угловой точке , к симплекс – таблице для угловой .

Пусть номера q и k определены так, как это сделано выше. Элемент , а также строка и столбец таблицы 3.4, на пересечении которых он стоит, называются разрешающими или опорными.

Из формул (18) и (19) следует, что преобразование начальной симплекс – таблицы с опорным элементом (см. табл. 3.4) приводит к новой симплекс – таблице (табл. 3.5), для определения элементов которой необходимо выполнить операции, указанные в нижеприведенном алгоритме.

Симплекс – таблица для угловой точки

Базис	Переменные	Свободный член
. . . . . .	. . . . . .	. . . . . .
	……

Алгоритм решения задач симплекс – методом

Для определенности считаем, что решается задача на отыскание максимума.

1. Задачу линейного программирования привести к каноническому виду.

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

Предполагаем, что все добавочные переменные имеют тот же знак, что и свободные члены; в противном случае используем так называемый М – метод, который будет рассмотрен ниже.

2. Определить базисные и свободные переменные.

3. Исходную расширенную систему заносим в первую симплекс – таблицу. Последняя

строка таблицы, в которой приведено уравнение для линейной функции цели, называется оценочной. В ней указываются коэффициенты функции цели . В левом столбце таблицы записываем основные переменные (базис), в последующих – коэффициенты при свободных переменных. В предпоследнем столбце – свободные члены расширенной системы . Последний столбец подготовлен для оценочных отношений, необходимых для определения базисной переменной на основании соотношения (14).

4. Определить возможность решения задачи по значениям согласно теоремам 1…3.

5. Выбрать разрешающий (опорный) элемент . Если критерий оптимальности не

выполнен (не выполнены условия теоремы 1 или 2), то наибольший по модулю отрицательный коэффициент в последней строке определяет разрешающий (опорный) столбец .

Составляем оценочные отношения каждой строки по следующим правилам:

1) , если все и имеют разные знаки;

2) , если все и ;

3) , если ;

4) 0, если и ;

5) , если и имеют одинаковые знаки.

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

6. Переход к следующей таблице по правилам:

a) В левом столбце записываем новый базис: вместо основной переменной - переменную , т.е. поменяем местами переменные и ;

b) На место опорного элемента поставить 1;

c) На остальных местах опорной строки в новой таблице оставить элементы исходной таблицы;

d) На остальные места в опорном столбце поставить соответствующие элементы исходной таблицы, умноженные на –1;

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

, , .

Для упрощения вычислений по этим формулам их можно сформулировать в виде «правила прямоугольника» (рис. ): элементы на диагоналях прямоугольника с вершинами

(или , , , , или , , , ) перемножаются (произведение, не содержащее опорного элемента берется со знаком минус) и полученные произведения складываются;

Рис. Правило прямоугольника для определения чисел: а - , б - , в - .

f) Все полученные элементы новой таблицы разделить на опорный элемент .

7. По назначению элемента определить, найдено ли оптимальное значение целевой функции. В случае отрицательного ответа продолжить решение (возврат к пункту 6).

Рассмотрен алгоритм преобразования симплекс – таблиц для невырожденных

допустимых базисных решений, т.е. выполнялась ситуация, описанная теоремой 3. Если исходная задача линейного программирования является вырожденной, то в ходе ее решения симплекс – методом могут появиться и вырожденные базисные решения. При этом возможны холостые шаги симплекс – метода, т.е. итерации, на которых не изменяется. Возможно так же и зацикливание, т.е. бесконечная последовательность холостых шагов. Для его предотвращения разработаны специальные алгоритмы – антициклины [Васильев Ф. П. Численные методы решения экстремальных задач. – М.: Наука, 1980].

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

Пример. Решить задачу, приведенную в примере , симплекс методом.

Решение.

q Итерация 1.

В качестве начальной симплекс – таблицы возьмем таблицу, найденную в примере и соответствующую допустимому базисному решению :

Начальная симплекс - таблица

Базис	Переменные	Свободный член	Оценочное отношение
x1	x2
x3 x4 x5				¥
f(x)	-3	-3

В последней строке таблицы есть два отрицательных элемента, , и столбец, соответствующий каждому из них можно считать опорным. Выберем, например, первый столбец (этот столбец отмечен стрелкой). Согласно теореме 3 существует допустимое базисное решение. Опорную строку найдем по правилу (14). В соответствии с пунктом 5 находим оценочные отношения: , т.е. это вторая строка. Опорный элемент обведен рамкой.

Будем формировать новую таблицу в соответствии с описанным алгоритмом

П.6а,б п.6в,г

	x4	x2
x3
x1
x5

Свободные места последней таблицы заполним по «правилу прямоугольника». Например, число, стоящие в строке при x₃ и столбце при x₂ этой таблицы, равно 2*2-1*1=3. Для и т.д. В результате этих вычислений, а также пункта 6е (т.е. деления на опорный элемент) получим искомую симплекс – таблицу:

П.6д п.6е

Отметим, что в результате перехода к новому допустимому решению значение целевой функции уменьшилось с 0 до –12 (см. нижний элемент последнего столбца таблицы).

q Итерация 2.

В качестве опорного (см. табл. ) можно взять только второй столбец (). С учетом (14) находим опорную строку:

Симплекс – таблица для угловой точки

Базис	Переменные	Свободный член	Оценочное отношение
x4	x2
x3 x1 x5	-1/2 1/2	3/2 1/2
f(x)	3/2	-3/2

, т.е. это первая строка. Опорный элемент обведен рамкой.

Преобразуем таблицу согласно алгоритму, получаем

	x4	x3
x2	-1/2
x1		-1/2
x5		-1
		-3/2

	x4	x3
x2	-1/2
x1		-1/2	9/2
x5	1/2	-1	3/2
	3/2	-3/2	45/2

Таким образом, на данной итерации значение уменьшилось с –12 до –15.

q Итерация 3.

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

Графическое решение задачи представлено на рис. , откуда видно, что

	I

Рис. Графическое решение задачи

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

Столбцы с номерами 2, 4, 5 и 6 матрицы А системы ограничений – равенств данной задачи образуют базисный минор. С помощью эквивалентных преобразований приводим эту систему к виду (4), где базисными являются переменные :

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

Исключив с помощью (20) базисные переменные в выражении для целевой функции, получим:

С помощью равенств (20) и (21) составляем симплекс – таблицу , соответствующую угловой точке :

Начальная симплекс - таблица

Базис	Переменные	Свободный член	Оценочное отношение
x1	x3
x2 x4 x5 x6	-1	-1
f(x)	-7	-14	-880

Среди коэффициентов , из (7) есть отрицательные – это элементы –7 и –14 последней строки таблицы . Следовательно, угловая точка не является решением задачи.

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

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

Разрешающую строку находим в соответствии с (14): так как , то разрешающей является строка, соответствующая базисной переменной . Итак, опорный элемент найден. , в таблице он обведен рамкой.

Заполнив новую таблицу по правилам, описанным выше, получим:

Симплекс – таблица для угловой точки

Базис	Переменные	Свободный член	Оценочное отношение
x1	x6
x2 x4 x5 x3	-1
f(x)	-7		-460

Отметим, что значение в новой угловой точке уменьшилось по сравнению с исходным: 460 вместо 880.

В нижней строке последней таблицы есть отрицательный элемент –7, стоящий в столбце при свободной переменной . Кроме того, в этом столбце имеются положительные элементы, поэтому в дальнейшем возможно уменьшение с помощью очередного шага симплекс – метода.

На данном шаге выбор опорного столбца однозначен и определяется отрицательным элементом –7 последней строки. Опорная строка находится из условия (14): так как , то это строка при базисной переменной . Опорный элемент в таблице обведен рамкой.

Как и на предыдущем шаге, находим очередную симплекс – таблицу по общим правилам:

Симплекс – таблица для угловой точки

В этой таблице оба коэффициента , в последней строке положительны. Поэтому угловая точка , соответствующая свободным переменным и , является точкой минимума целевой функции . Минимальное значение со знаком минус записано в правом нижнем углу таблицы , поэтому .

Графическое решение задачи представлено на рис. , откуда видно, что и .

Пример . Решить симплекс – методом задачу:

при ограничениях

Решение. С помощью дополнительных неотрицательных переменных перейдем к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком «+», так как все неравенства имеют вид «».

Получим систему ограничений в виде:

Итерация 1.

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

Исключив с помощью () базисные переменные в выражении для целевой функции, получим

с помощью равенств (1) и (2) составляем симплекс – таблицу, соответствующую угловой точке :

Начальная симплекс – таблица

Базис	Переменные	Свободный член	Оценочное отношение
x1	x2
x3 x4 x5 x6
f(x)	-2	-3

В соответствии с п.4 алгоритма проверяем критерий оптимальности. В последней строке имеются отрицательные коэффициенты. Выберем из них наибольший по модулю (-3); второй столбец разрешающий, переменная x₂ перейдет в основные (этот столбец отмечен стрелкой). В соответствии с п.5 находим оценочные отношения и . Третья строка является разрешающей (отмечена горизонтальной стрелкой). На пересечении разрешающих строки и столбца стоит опорный элемент (обведен рамкой).

Итерация 2. Строим таблицу по правилам п.6 алгоритма. В новом базисе основные переменные: .

Симплекс – таблица для угловой точки

Базис	Переменные	Свободный член	Оценочное отношение
x1	x5
x3 x4 x2 x6		-3 -1		11/2
f(x)	-2

Критерий оптимальности вновь не найден. Теперь первый столбец разрешающий; - переход в основные, ; первая строка разрешающая, - опорный элемент.

Итерация 3. Новая симплексная таблица примет вид табл.

Симплекс – таблица для угловой точки

Базис	Переменные	Свободный член	Оценочное отношение
x3	x5
x1 x4 x2 x6	-2 -3	-3		12/9
f(x)		-3

И на этот раз критерий оптимальности не выполнен; второй столбец и вторая строка – разрешающие, - опорный элемент.

Итерация 4. Переходим к таблице .

Симплекс – таблица для угловой точки

Критерий оптимальности выполнен, значит , оптимальное базисное решение .

Графическое решение задачи представлено на рис. , откуда видно, что и .

Рис. Графическое решение задачи .

Метод искусственного базиса (М – метод).

Решение задачи линейного программирования симплекс - методом начинается с поиска какой – либо угловой точки допустимого множества этой задачи и построения начальной симплекс – таблицы. Для этого можно использовать метод искусственного базиса, который состоит в следующем.

Пусть в ограничениях (2) задачи линейного программирования в каноническом виде (1) … (3) все свободные члены . Если это не так, то умножим соответствующие уравнения из (2) на (-1). Введем дополнительные переменные , и рассмотрим вспомогательную задачу линейного программирования.

(1) (30)

, , (2) , (31)

(3) , (32)

Одной из угловых точек допустимого множества этой задачи, очевидно, является точка . Поэтому для решения задачи (30) – (32) можно использовать симплекс – метод со следующей начальной симплекс - таблицей:

Начальная симплекс – таблица.

Базис	Переменные	Свободный член
. . . . . .	. . . . . .	. . . . . .
	……	-

где , -.

Отметим, что решение задачи (30) – (32) всегда существует, так как её допустимое множество не пусто (), а целевая функция (30) ограничена снизу на (.

Пусть минимум функции на множестве , равный , достигается в точке

. (32’)

1.>0. Тогда допустимое множество исходной задачи линейного программирования (1) – (3) пусто, т. е. Эта задача не имеет решений.

□ Предположим, что это не так, т. е. Æ и существует точка (). Тогда из (2), (3), (30)…(32) следует, что точка и , что противоречит предположению . ■

2. Пусть теперь . Покажем как в этом случае найти допустимое базисное решение исходной задачи (1)…(3) и построить соответствующую ему симплекс – таблицу.

□ Так как , то из (30) и (32’) следует, что .

Для невырожденной задачи (30)…(32) это означает, что в завершающей симплекс – таблице, полученной при её решении симплекс – методом, все дополнительные переменные переведены в свободные. Если опустить столбцы этой таблицы, соответствующие переменным , то получим таблицу, в которой записано базисное решение системы (2). В этом решении какие – то переменных являются базисными, а остальные – свободными. А так как таблица получена в результате шагов симплекс – метода, все элементы её столбца свободных членов неотрицательны и базисное решение является, к тому же, допустимым, т. е. угловой точкой множества .

Если вспомогательная задача (30)…(32) является вырожденной, то в угловой точке (32’) некоторые из переменных могут оказаться базисными. В этом случае такие переменные следует перевести в свободные, выбирая в качестве разрешающих произвольные элементы симплекс – таблицы, отличные от нуля. Если же все элементы в строке базисной переменной = 0, то эту строку можно вычеркнуть из таблицы. ■

Таким образом, описанная процедура поиска метода искусственного базиса позволяет либо убедиться в неразрешимости исходной задачи (1)…(3), либо найти угловую точку допустимого множества этой задачи и соответствующую симплекс – таблицу. Для дальнейшего решения задачи (1)…(3) симплекс – методом необходимо предварительно заменить в этой таблице последнюю строку на строку коэффициентов целевой функции из (1).

Замечание. В процессе поиска решения вспомогательной задачи можно сразу опускать в симплекс – таблице вспомогательные переменные , переведенные в число свободных (вычеркивая соответствующие столбцы симплекс – таблицы).

Пример 7. Методом искусственного базиса найти какую – либо угловую точку допустимого множества задачи линейного программирования, рассмотренной в примере 5, и записать соответствующую этой угловой точке симплекс – таблицу.

◄ Введем дополнительные переменные и запишем условие вспомогательной задачи линейного программирования (1) – (3) для рассматриваемого случая:

Считая дополнительные переменные базисными , запишем симплекс – таблицу этой задачи, соответствующую угловой точке = (0; 0; 0; 0; 0; 0; 20; 50; 30; 60):

Начальная симплекс – таблица.

Базис	Переменные	Свободный член
	1 0 0 100 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1
	-1 –1 –1 –2 –2 –2	-160

Любой столбец этой симплекс – таблицы может быть выбран в качестве разрешающего, так как элементы её последней строи отрицательны. Выберем , например, столбец, соответствующий свободной переменной . Тогда разрешающим будет элемент этого столбца, стоящий в первой строке, так как

Производя преобразования симплекс – метода, получим такую последовательность симплекс – таблиц (рамками обведены разрешающие элементы):

	x1	x2	x3	x7	x5	x6
x4
x8
x9
x10	-1			-1
		-1	-1		-2	-2	-120

	x1	x2	x3	x10	x6
x4
x8				-1	-1
x9
x5	-1
	-1	-1	-1			-40

	x1	x8	x3	x6
x4
x2				-1
x9
x5	-1
			-1	-1	-30

	x1	x3	x9
x4
x2
x6
x5	-1	-1	-1

В нижней строке последней симплекс – таблицы нет отрицательных элементов, а в правом нижнем углу стоит нуль. Следовательно, минимум вспомогательной целевой функции достигнут и

(0; 40; 0; 20; 10; 30) (35)

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

Заменив нижнюю строку последней симплекс – таблицы на строку коэффициентов целевой функции исходной задачи, получим симплекс – таблицу этой задачи, соответствующую угловой точке из (35):

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

Использование из (35) в качестве начальной угловой точки симплекс – метода в рассматриваемой задаче иллюстрирует решение примера.

М – метод (продолжение).

Рассмотрим разновидность метода искусственного базиса, суть которого заключается в следующем.

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

1. Если в оптимальном решении Т – задачи все искусственные переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи (т. е. если т. е. минимум М – функции равен 0).
2. Если имеется оптимальное решение Т – задачи, в котором хотя бы одна из искусственных переменных отлична от нуля, то система ограничений исходной задачи несовместна.
3. Если то исходная задача также неразрешима, причем либо либо условия задачи противоречивы.

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

Пример. Решить задачу М- методом, используя симплексные таблицы

при ограничениях

( I )

( II )

( III )

Решение. Вводим дополнительные неотрицательные переменные с соответствующими знаками:

(0; 0; -1; 3; 3) – недопустимое базисное решение с одной отрицательной компонентой, поэтому в первое уравнение введем искусственную переменную с тем же знаком, что и свободный член:

или

.

Составляем первую симплексную таблицу (табл. 5.5).

Начальная симплекс - таблица

Базис	Переменные	Свободный член	Оценочное отношение
x1	x2	x3
y1 x4 x5	-1 -1		-1		¥
f(x)	-1	-2			max
-Mф	M	-M	M	M	max

Последняя строка – это (-М ) - функция, т. е. (-Заполняем её, умножая строку на коэффициент (-М). Проверяя выполнение критерия оптимальности при отыскании максимума (-М) – функции, определяем, что в последней строке имеется отрицательный элемент во втором столбце; значит, он является разрешающим, переменная переходит в основные. Минимальное оценочное отношение в первой строке, она разрешающая. Переменная переходит в неосновные, обращается в 0 на следующем базисном решении и далее исключается из рассмотрения.

В соответствии с общим алгоритмом получаем табл. 5.6.

Симплекс – таблица первого шага.

Базис	Переменные	Свободный член	Оценочное отношение
x1	x3
x2 x4 x5	-1	-1		¥ ¥
f(x)	-3	-2		max
-Mф				max

Последняя строка показывает, что критерий оптимальности выполнен; значит , далее эту строку можно не рассматривать. Получено допустимое базисное решение (0; 1; 0; 2; 3), начиная с которого решаем исходную задачу в соответствии с обычным алгоритмом.

Итерация 1.

Симплекс-таблица угловой точки

Базис	Переменные	Свободный член	Оценочное отношение
x5	x3
x2 x4 x1		-1		¥ ¥
f(x)		-2

В качестве разрешающего столбца выберем первый (этот столбец в таблице помечен стрелкой). Разрешающую строку найдем по оценочному соотношению. Это будет третья строка. Опорный элемент =1 обведен рамкой.

Будем формировать новую таблицу в соответствии с алгоритмом.

Итерация 2.

В качестве разрешающего столбца можно взять только второй столбец. По оценочному соотношению находим разрешающую строку и опорный элемент =1 (обведен рамкой).

Преобразуем таблицу согласно алгоритму (см табл.)

Симплекс-таблица угловой точки

Итерация 3.

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

.

Графическое решение задачи представлено на рисунке , откуда видно что .

Рис. Графическое решение задачи

Рассмотрим задачу дробно – линейного программирования.

(4)

(5)

(6)

. (7)

Будем считать, что на допустимом множестве X задачи (4)-(7) знаменатель целевой функции из (4) не обращается в нуль и, соответственно, сохраняет знак. Если этот знаменатель отрицателен, то умножим числитель и знаменатель дроби из (4) на -1 и будем в дальнейшем считать, что >0 для всех xÎX.

Обозначим (очевидно, y₀ >0 при xÎX) и введем новые переменные

В новых переменных задача (4)-(7) принимает следующий вид:

(8)

т.е. превращается в задачу линейного программирования. Отметим, что требование , включенное в условие задачи (8), не ограничивает возможного изменения переменной , так как > 0 при xÎX.

Найдем решение задачи линейного программирования (8) и, используя равенства:

(9)

получим решение исходной задачи дробно - линейного программирования (4)-(7).

Если то допустимое множество X задачи (4)-(7) не ограниченно и минимум целевой функции на нем не достигается.

Рассмотрим задачу, состоящую в определении максимального значения функции двух переменных, позволяющих решить ее графическим методом

(10)

при условиях (5)…(7).

Чтобы найти решение задачи (10) сначала находим многоугольник решений, определяемый ограничениями (5)…(7). Предполагая, что этот многоугольник не пуст, полагаем значение функции равным некоторому числу h

(11)

Из (11) найдем

или

где ; уравнение разрешающей прямой, проходящей через начало координат. С изменением h разрешающая прямая вращается относительно начала координат. Направление вращения разрешающей прямой определяется по знаку производной . Отрицательный знак производной соответствует вращению разрешающей прямой почасовой стрелке, а положительный – против часовой стрелки.

Вращая построенную прямую (11) вокруг начала координат, либо определяем вершину (вершины), в которой функция (10) принимает максимальное значение, либо устанавливаем неограниченность функции на множестве планов задачи.

Итак, процесс нахождения решения задачи (10) при условиях (5)…(7) включает следующие этапы:

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

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

3). Находят многоугольник решений задачи.

4). Строят прямую (11), уравнение которой получается, если положить значение целевой функции(4)равным некоторому постоянному числу.

5). Определяют точку максимума или устанавливают неразрешимость задачи.

6). Находят значение целевой функции в точке максимума.

Заканчивая рассмотрение нахождения решения задачи дробно – линейного программирования графическим способом, отметим, что если многогранник решений содержит больше чем одну точку, то возможны следующие случаи:

1). Многогранник решений ограничен, максимум и минимум достигается в его угловых точках (рис. 2.15).

2). Многогранник решений не ограничен, однако существуют угловые точки, в которых целевая функция задачи принимает максимальное и минимальное значения (рис. 2.16).

3). Многогранник решений не ограничен, и один из экстремумов достигается. Например, минимум достигается в одной из вершин многогранника решений и функция F имеет так называемый асимптотический максимум (рис. 2.17).

4). Многогранник решений не ограничен, как максимум, так и минимум являются

асимптотическими (рис. 2.18).

Рис 2.15

Рис 2.16

Рис 2.17

Рис. 2.18

Пример.1 (12)

(13)

(14)

Таким образом, математическая постановка задачи состоит в определении неотрицательного решения системы линейных неравенств (13), при котором достигается минимум функции (12). Чтобы найти решение задачи, прежде всего построим многоугольник решений. Как видно из рис.2.14, им является треугольник BCD. Значит, функция (12) принимает минимальное значение в одной из точек: B,C или D. Чтобы определить, в какой именно, положим значение функции F равным некоторому числу, например 11 / 4. Тогда

или

(15)

Уравнение (15) определяет прямую, проходящую через начало координат. Координаты точек, принадлежащих этой прямой и многоугольнику решений, являются планами задачи, при которых значение функции (12) равно 11/4.

Возьмем теперь h = 5/2, т.е. положим

или

(16)

Рис.2.14

Уравнение (16), так же как и (15), определяет прямую, проходящую через начало координат. Ее можно рассматривать как прямую, полученную в результате вращения по часовой стрелке вокруг начала координат прямой (15). При этом координаты точек, принадлежащих прямой (16) и многоугольнику решений, являются планами задачи, при которых значение функции (12), равное 5/2, меньше, чем в точках прямой (15). Следовательно, если положить значение функции (12) равным некоторому числу h₀:

(17)

а прямую (17), проходящую через начало координат, вращать в направлении движения часовой стрелки вокруг начала координат, то получим прямые

где h < h₀ .

Найдем последнюю общую точку вращаемой прямой с многоугольником решений. Это точка D (3,1) (рис.2.14), в которой достигается минимум функции (12).

При нахождении угловой точки многоугольника решений, в которой целевая функция задачи принимает наименьшее значение, мы полагали значение функции равным некоторым двум постоянным числам и установили направление вращения прямой, определяющее уменьшение значения функции. Это можно было сделать и по-другому. А именно: полагая значение функции F равным некоторому числу h, т.е.

(18)

и получив некоторую прямую, проходящую через начало координат и имеющую угловой коэффициент, зависящий от h, можно, используя производную, установить направление вращения прямой (18) при возрастании h. Получим

Практически же дело обстоит гораздо проще. Найдя точки В (1,3)

И D (3,1) (рис.2.14), в которых функция (12) может принимать минимальное значение, вычислим ее значение в этих точках: F(В)=11/4 F(D)=9/4. Так как F(В) < F(D), то можно утверждать что в точке, D целевая функция принимает минимальное значение. Одновременно с этим заметим, что в точке В функция принимает максимальное значение.

Нелинейное программирование

Задача нелинейного программирования формулируется следующим образом:

определить минимальное значение функции

f (x) → min (1)

при условии, что её переменные удовлетворяют соотношениям

g_i (x) = b_{i ,} i = 1, 2,…, L (2)

g_i (x) £ b_i i = L+1,…, m (3)

где f(x), g(x), i = 1,…, m - некоторые известные функции

(необязательно линейные) n переменных, а b_i - заданные числа.

Условие неотрицательности переменных x_j ³ 0, j =1,…, n, входящее в постановки многих задач нелинейного программирования, можно записать в виде неравенств (3), положив g_j (x) = -x_j , b_j =0.

В евклидовом пространстве Eⁿ система ограничений (2) … (3) определяет область допустимых решений задачи. В отличие от задачи линейного программирования она не всегда является выпуклой.

Если определена область допустимых решений, то нахождение решения задачи (1) … (3) сводится к определению такой точки этой области, через которую проходит гиперплоскость наинизшего уровня: f (x) = α , где α - произвольное число.

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

1. Находят область допустимых решений задачи,

определяемую соотношениями (2) … (3).

2. Строят гиперплоскость f (x) = α..

3. Определяют гиперплоскость наинизшего уровня или устанавливают неразрешимость задачи из-за неограниченности функции (1) снизу на множестве допустимых решений.

4. Находят точку области допустимых решений, через которую проходят гиперплоскость наинизшего уровня, и определяют в ней значение функции (1).

Пример:Найти максимальное значение функции

F = x₂ - x₁² +6x₁ (3)

при условиях 2x₁ + 3x₂ £ 24

x + 2x₂ £ 15 (4)

3x₁ + 2x₂ £ 24

x₂ £ 4 (5)

x₁x₂ ³ 0

x₂ = 4 .

Решая эту систему, получим x₁^* = 3; x₂^* = 4. И так, F_max = 13 при

x^* (3,4).

Процесс нахождения решения задачи нелинейного программирования (1) … (3) с использованием её геометрической интерпретации включает следующие этапы:

Для нахождения гиперплоскости наинизшего уровня можно руководствоваться следующими соотношениями: точка x^* = (x_{1 min} , x_{2 min}) принадлежит прямой x₂ = 0 и параболе F_min = x₂ - x₁² +6x₁ , а потому обоим этим уравнениям, т. е. м.д. определена как решение системы

x₂ = 0

x₂ - x₁² +6x₁ = F_min (1)

Однако, т.к. нам не известно F* - оптимальное значение целевой функции F (x₁, x₂), то в этой системе оказывается три переменных и всего два уравнения, поэтому систему необходимо дополнить ещё одним уравнением, связывающим переменные x₁, x₂, F_min.

Нужное уравнение можно получить, если учесть, что угловой коэффициент касательной к параболе, по которой целевая функция достигает своего min значения, равен 1: касательной в этой точке является прямая x₂=0. Как мы знаем, целевой коэффициент касательной к кривой x_{2 =} f (x₁) в точке x₁ равен ∂x₂ / ∂x₁. Поэтому в нашем случае имеем

∂x₂ / ∂x₁=0 (2)

Вычислим теперь производную целевой функции F_min. Для этого продифференцируем левую и правую часть этого соотношения по x₁. Получим

0 = 0 - 2x₁ +6 (3)

первое слагаемое дифференцируем, как сложную функцию от x₂.

∂ [x₂] / ∂ x₂ = ∂ [x₂] / ∂ x₂ ∂ x₂ / ∂ x₂ = 0

Откуда из (3) следует 0 = 2x₁ +6. Если учесть (2), то окончательно получим

2x₁ - 6 = 0 x₁ = 3. Дополняя этим последним соотношением систему (1), окончательно получим x₂ = 0 x₂ - x₁² + 6x₁ = F_min x₁ = 3.

Откуда -9 + 18 = F* F* = 9.

Для нахождения максимального значения функции поступаем аналогичным образом. Получаем систему

x₂ = 4

x₂ - x₁² +6x₁ = F_max

x₁ = 3

Решая её, получим F_max =13.