Практика 8. Линейное и нелинейное программирование

Содержание
Теоретические положения.
Упражнение 1. Задать область ограничений геометрически и осуществить в ней перебор точек.
Упражнение 2.  Задать область ограничений и осуществить перебор точек на`ее границе. Найти максисмум ЦФ, построить ее график.
Контрольные вопросы.
Нелинейное программирование
Упражнение 3. Задача "О почтовой посылке". Найти  максимальный объем посыдки при ограничении на обхват и длину. 
Контрольные вопросы.
Упражнение 4. Задача Тартальи: Из чисел: 0 < x,y < 90 найти: Fmax=xy(y-x).
Контрольные вопросы.



Теоретические положения.

Задачи линейного и нелинейного программирования формируются следующим образом: найти значения переменных, которые бы обращали целевую функцию (ЦФ) в минимум или максимум.

ЦФ - это комбинация суммы, произведений переменных величин и заданных чисел (констант), например:

F=10*x+20*y+3*z+80*t  и т.д. - max.     (1)

Переменные величины x,y,z,t и т.п. имеют, как правило, ограничения простые, типа больше нуля:
x,y,z,t 0,                                  (2)
и сложные, состоящие из равенств и неравенств типа:
10*x +30*y+5*z =  30,           (3)
50*x +10*y+9*z  ?  60,          (4)
10*x +30*y+5*z  ?  10.          (5)

Если комбинации переменных в ЦФ и в ограничениях не содержат их перемножения, возведения в степень и т.п., то такие задачи называются линейными, в противном случае - нелинейными.
ЦФ, области ограничений имеют геометрические интерпретации: в линейных задачах - это
прямые, плоскости, гиперплоскости, в нелинейных кривые, поверхности, гиперповерхности.

Графический способ решения задачи заключается в том, что, если ЦФ дать какое-то (произвольное) значение и привести ее к уравнению в отрезках, то это будет плоскость в том же пространстве, в котором находится многогранник ограничений, и, если найти к этой плоскости ближайшую или самую удаленную вершину многогранника ограничений, то координаты этих вершин, при подстановке их в уравнения ЦФ дадут ее максимум или минимум.

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



 

  
Упражнение 1 Задать область ограничений геометрически и осуществить в ней перебор точек. ЦФ и область ограничений заданы. 
 
 

Целевая функция задана следующим уравнением:
F(x,y) = x+y -> max.   (1)

При ограничениях, заданных системой неравенств:
x/100 + y/170 > 1,  (2)
x/140 + y/120 > 1,  (3)
x > 0,    (4)
y > 0.    (5)

Уравнения (1,2) можно представить как уравнения прямых в отрезках (рис.1):
x/100 + y/170 = 1,
x/140 + y/120 = 1.

Уравнения (9, 10) представляют  оси координат.
Перебор точек  в заданной области можно выполнить с помощью МК: linpr0, linpr1, linpr2.

linpr0.mac
otrezok : p101=0.,0. p102=0.,180. $ ось Ox
otrezok: p101=0.,0. p102=160.,0. $ ось Oy
otrezok : p101=100.,0.  p102=0.,170. $ ограничение x/100.+y/170.=1.
otrezok : p101=140.,0. p102=0.,120. $ ограничение x/140.+y/120.=1.
linpr1: x=0.   y=2.5

linpr1.mac - перебор линий в области ограничений
y  120. ? exit
x90=(1.-(y/170.))*100.
x91=(1.-(y/120.))*140.
linpr2: x=0.
linpr1 : y=y+5.0

linpr2.mac - перебор точек на линиях в области ограничений
x91 x90 ? goto met
x > x91 ? exit
goto met2
$ met
x > x90 ? exit
$ met2
okr : p100=p s100=2.5
linpr2: x=x+5.0

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


Упражнение 2 Задать область ограничений и на ее границе осуществить перебор точек. Найти максисмум ЦФ и построить ее график.  
 
 ЦФ и область ограничений заданы.

Целевая функция задана следующим уравнением:
F(x,y) = x+y -> max.   (1)

При ограничениях, заданных системой неравенств:
x/100 + y/170 > 1,      (2)
x/140 + y/120 > 1,      (3)
x > 0,                           (4)
y > 0.                           (5)

Уравнения (1,2) можно представить как уравнения прямых в отрезках (рис.1):
x/100 + y/170 = 1,
x/140 + y/120 = 1.
Уравнения (4, 5) представляют  оси координат.
Перебор точек  в заданной области можно выполнить с помощью МК:

linmd0.mac - задания исходных данных
otrezok : p101=0.,0. p102=0.,250.  $ ось Ox
otrezok: p101=0.,0. p102=250.,0. $ ось Oy
otrezok: p101=140.,0.  p102=0.,170. $ x/140.+y/170.=1.
otrezok: p101=190.,0. p102=0.,120. $ x/190.+y/120.=1.
otrezok: p101=200.,0. p102=0.,200. $ ЦФ x+y=200.
: p103=140.,140.      $  начальная точка для ЦФ: f=x+y
linmd: x=0. y=0. s=0.  s98=0.

linmd.mac - непосредственно перебора точек на границе области ограничений, а также вычисления максимума ЦФ
s > 1.01 ? exit
y=s*120.0   $ перебор y в диапазоне 0.-120
x90=(1.-(y/170.))*140. $ расчет абсцисс на области ограничений
x91=(1.-(y/120.))*190. $ то же самое, но на другом ребре
x91 > x90 ? goto met
x=x91
goto met2
$ met
x=x90
$ met2
$ строим точки на границе выпуклого множества
okr: p100=x,y s100=2.5 $ точки на границе выпуклого многогранника
s9=x+y
s9 > s98 ? s98=s9
otrezok: p101=p103 p102=x,s9 $ график ЦФ: f=x+y
p103=p102
linmd : s=s+0.05



Контрольные вопросы
1. В каком диапазоне происходит вычисление ЦФ?
2. Что является аргументом ЦФ?
3. В каком регистре будет максимум ЦФ?
4. Чему равна ЦФ при x=85.5, y=66.0? Кстати, точки максимума ЦФ.
5. В какой точке ЦФ будет иметь минимум?



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

Упражнение 3. Задача "О почтовой посылке": найти  максимальный объем посыдки при ограничении на обхват и длину.
Постановка (формализация задачи)
Формулируем цель:
s=x*y*z->max
и ограничения:
x+2y+2z < 72,
0< x,y,z.
Задача является смешанной. ЦФ  - нелинейная, а область ограничений - линейная. Область ограничений - многогранник, ограниченный координатными плоскостями x,y,z и плоскостью x/72+y/36+z/36=1.
Положения точки, обеспечивающей максимум ЦФ, будет на грани р1-р3 многогранника ограничений.
Алгоритм решения задачи.
1) В плоскости р1-р3 выполняем перебор точек р (возможные сочетания переменных x,y,z) по формулам:
 
p=(1.-s11)*p91+s11*p92,  0 < s11 < 1,
где, р91, р92, в свою очередь, определяются:

 p91=(1.-s12)*p1+s12*p3,  0 < s12 < 1,
 p92=(1.-s12)*p2 +s12*p3,  0 < s12 < 1.

2) Вычисляем ЦФ s (s=x*y*z) при каждом сочетании x,y,z.

3) Сравниваем s с эталоном (регистром) s99. Как только s при расчете будет больше s99, помещаем его в s99. В результате перебора (например, с помощью 2-го цикла) и сравнения s c s99 (s > s99 ?  s99=s) получаем s99 максимальное из возможных s.

4) В момент достижения максимального значения s выполняем принудительный выход из МК. Искомые значения x,y,z будут лежать в p.

5) Для контроля вычислений строим графики ЦФ в плоскостях sx непосредственно над плоскостью р1-р3.

Решение задачи выполняем с помощью МК dok0 - задания исходных данных и МК dok, dok1 - действий, сформулированных в алгоритме решения задачи.

dok0.mac
: p1=72.,0.,0. p2=0.,36.,0.  p3=0.,0.,36.  p4=p3
otrezok : p101=p1 p102=p3
otrezok : p101=p2 p102=p4
dok: s=0. s12=0.  p105=x1, 0. s98=0.
$ Определили: s98max=3429.22

dok.mac
s 1.001 ? exit  $ МК перебора линий в области ограниченй
p91=(1.-s)*p1+s*p3
p92=(1.-s)*p2 +s*p4
otrezok: p101=p91 p102=p92
dok1 : s1=0. p105=p91 $ к МК перебора точек на линиях
$ n50<3429 ? exit
dok : s=s+0.1

dok1.mac - расчет объема посылки в цикле
s1 > 1.001 ? exit
p=(1.-s1)*p91+s1*p92  $  перебор точек на границе области ограничений
s11=x*y*z   $ вычисление объема посылки при разных x,y,z
otrezok:  p101=p105  p102=x, s11/30.+z   $ график ЦФ
p105=p102   $  конец в начлало
s11 > s98 ?  s98=s11  $ максимум посылки в s98
n50=s98 $  максимум переводим в целое число, знаки после запятой не учитыва-ем
$ n50 < 3429 ? exit $ выход при втором запуске для определения x,y,z
$  кстати, размеры посылки: x=25.2   y=12.6   z=10.8
dok1 : s1=s1+0.1
 
 
График ЦФ в задаче о посылке.



Контрольные вопросы
1. Что является абсциссой ЦФ? Что ординатой?
2. В каком диапазоне происходит изменение абсциссы ЦФ? Ординаты ЦФ?
3. В каком параметре отыскивается максимум ЦФ?
4. В какой переменной формируется ЦФ?
5. Что нужно сделать в МК, чтобы определить размеры посылки при ее максимальном объеме?

Упражнение 4. Задача Тартальи: Из чисел 0<x,y<90 найти Fmax=xy(y-x).

tart0.mac  - имя МК
: p1=90.,0. p2=0.,90.  $ так можно представить ограничения точками
otrezok : p101=p1 p102=p2 $  и соответственно отрезком
tart1: s=0.   s11=0.  p99= x1, 0. s98=0.

$ В итоге Fmax(в s99)=69984 при x=72, y=18
$ Проверка
s10=72.*18.(18.-72.)
tart1.mac
s11 1.00 ? exit
p=(1.-s11)*p1+s11*p2            $ перебор точек на ограничении
s=x*y*(x-y)                     $ вычисление мах/min
otrezok: p101=p99 p102=x,y+s/700. $ график ЦФ
p99=p102
s < s99 ? s99=s
s s98 ?  s98=s                $ сравнение и выбор
n50=s98
$ n50  < 69984 ? exit          $ при 2-м запуске МК
tart1: s11=s11+0.05 p105=p102   $ рекурсия
 
 
График ЦФ в задаче Тартальи.



Контрольные вопросы
1. Что является абсциссой ЦФ? Что ординатой?
2. В каком диапазоне происходит изменение абсциссы ЦФ? Ординаты ЦФ?
3. В каком параметре отыскивается максимум ЦФ?
4. В какой переменной формируется ЦФ?
5. Что нужно сделать в МК, чтобы определить цифры, чтобы их произведение на их разность было максимальном? Минимальным?