Лекция 8. ЛИНЕЙНОЕ И НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

С О Д Е Р Ж А Н И Е

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

II. Решение задач линейного и нелинейного программирования  на основе вычислительных методов.
Пример 2. Требуется структурировать область ограничений и расчитать в ней минимум/максимум ЦФ.

Упражнение. Используя теоретико-множественные операции в системе “CG-Вектор”, смоделируйте область ограничений, представленную системой уравнений равенств и неравенств.

III.  Нелинейные задачи.
Пример 3. Задача "О почтовой посылке": найти  ее максимальный объем при ограничении на обхват и длину.

IV. Задачи нелинейного программирования в многогокритериальных задачах.
Пример 4. Задача Тартальи. Из чисел: 0 < x,y < 90 найти: Fmax=xy(y-x).


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

Задача линейного программирования формируется следующим образом: найти значения переменных x1, x2, ..., xn, которые обращают в минимум (максимум) функцию
F=c1*x1+....cn*xn+c0 -> max         (1)
и удовлетворяют условиям
     a11*x1+...a1n*xn = b1
     a21*x1+...a2n*xn = b2
     .....................................
     an1*xn+  ann*xn = bn                  (2)

Областью решений системы ограничений (2) является выпуклое многогранное множество - гипергранник ограничений. Этот гипергранник ограничен гиперплоскостями, уравнения которых получают из неравенств системы ограничений.

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

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

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

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

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

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)

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

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

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

Известно, что уравнение вида: x/a+y/b+z/c+t/d+ и т.д=1, называются:

x/a+y/b =1 - уравнением прямой в отрезках,
x/a+y/b+z/c=1 - уравнением плоскости в отрезках,
x/a+y/b+z/c+t/d=1 - уравнением гиперплоскости в отрезках.

Эти образы отсекают по осям x,y,z,t отрезки равные, соответственно a,b,c,d.
 
Рис. 1. Уравнения в отрезках и их геометрические образы

Некоторые переменные и, соответственно, отсекаемые отрезки в уравнениях могут отсутствовать. В этом случае образы будут занимать частные положения. Например, уравнение вида x=20 в 2-мерном пространстве x,y будет представлять прямую линию, параллельную оси y и отстоящую от нее на 20 единиц. В трехмерном пространстве x,y,z уравнение вида x=20 будет представлять плоскость, перпендикулярную оси х (а также параллельную осям y и z) и отстоящую от начала координат на 20 единиц. Уравнение вида x/10+y/30+1 в трехмерном пространстве будет плоскостью, параллельной оси z и перпендикулярной координатной плоскости x,y.

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

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

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

Решение может оказаться и на ребре и даже грани, если плоскость ЦФ будет им параллельна.

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

Требуется найти максимум линейной формы
F=6x1 + 5x3 + 200 -> max  (3)
при ограничениях:
4x1 + 7x2 + 8x2 < 280
10x1 + 6x2+ 6x3+ 5x4 < 300
x1, x2, x3, x4 > 0                     (4)

Решение графическим методом этой задачи заключается в следующем:
1) строится гипергранник решений данной системы ограничений;
2) вне гипергранника решений проводится гиперплоскость линейной формы задачи;
3) определяется вершина оптимального решения как вершина гипергранника, наименее или наиболее удаленная от проведенной гиперплоскости;
4) по чертежу определяются координаты вершины оптимального решения, значения которых и являются искомыми значениями неизвестных;
5) значения координат подставляются в уравнение линейной формы и определяется искомое максимальное значение.

Для построения гипергранника решений уравнения системы (4) почленно делятся на свободный член. В результате
получаем уравнения в отрезках рассматриваемых гиперплоскостей на координатных осях Ох1, Ox2, Ox3, Ox4
x1/70 + x2/ + x3/35+x4/28 = 1  (5)
x1/30 + x2/50 + x3/50+x4/60 = 1  (6)
 

На рис. справа в косоугольной изометрической и ортогональных проекциях построены следы гиперплоскостей P и Q.
В результате пересечений координатных гиперплоскостей и гиперплоскостей P и Q образовался выпуклый гипергранник решений. Контуры этого гипергранника на чертежах даны утолщенными линиями. Вершинами гипергранника являются точки О, Qх, K, H, Px2, Px4, Px3, V.

На рис. построена также линейная форма (4), соответствующая значению F=500. Стрелками показано направление ее перемещения, при котором возрастает линейная форма.

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

Координаты вершины V, снятые с чертежей, имеют значения  х1=13.5; х2=0; х3=28.5; х4=0. Подставив значения этих координат в уравнение (4.4) линейной формы, получим ее максимальное значение Fmax=423.5.

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

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

Одновременно с преобразованием гиперплоскости необходимо соответственно преобразовать и все вершины гипергранника решений.


Пример 1. На Магаданском направлении необходимо перевезти следующие виды груза: А - транспортная техника; Б - контейнеры, В - генгруз в количествах, верхние пределы которых указаны в таблице. Каждое из выделенных для этих перевозок трех судов может принять одновременно определенное количество каждого груза, указанное в таблице.
Требуется составить такой план работы судов (определить количество рейсов каждого судна), который обеспечивает перевозку грузов с наименьшими эксплуатационными расходами.
Для построения геометрической модели планируем для 1-го судна - x рейсов, для 2-го судна - y рейсов, а для 3-го судна - z рейсов. Тогда суммарные расходы судов будут равны:

F=20x+15y+10z -> min  (7)

при следующих ограничениях

12x + 6y+10z=60
5x+10y+8z = 40
3x+5y+10z=30   (8)

Ограничения определяют то количество груза каждого вида, которое могут перевезти все суда за искомое количество рейсов: x,y и z.

 
Виды 
грузов
Количество грузов, 
которое необходимо 
перевезти, тыс. т 
 
Количество грузов, перевозимое судном 
за один рейс, тыс. т
 
А 60
Б 40
В 30
 
на 1-м судне на 2-м судне на 3-м судне
12 6 10
5 10 8
3 3 10
 
Эксплуатационные расходы за рейс, тыс. т. 
 
20 15 10
 
Графическое решение задачи по предложенной выше методике показано на рис. 2.
 

Рассмотрим решение данной задачи в расчетно-графической среде системы "Вектор". Наиболее сложным этапом решения является задание области ограничений. Модуль Vec_Opt системы "Вектор" предоставляет возможность формирования трехмерной фигуры с помощью операций задания первой грани (косая плоскость по 4-м точкам), задания второй грани (косая плоскость по 4-м точкам) и операции "Визуализация трехмерного объекта на трехмерной сетке 00 x 00 x 00". При этом формируется трехмерный массив точек трехмерного образа. Если задать сетку 2x2x2, то изображаются только линии ребер тела.

Над областью ограничений необходимо построить целевую функцию Q(x,y,z), которая представляет собой трехмерную линейную фигуру (гиперплоскость) в 4-мерном пространстве. Модуль Vec_Opt позволяет работать с фигурами 4-мерного пространства. Выполняются все традиционные операции отображения, преобразования и расчета подобно тому, как это производилось для трехмерного пространства, с отличием лишь в том, что увеличивается число ортогональных проекций, добавляются ортогональные трехмерные проекции и т. д.

На рис. показаны различные проекции целевой функции. При этом проекции целевой функции на координатные подпространства xyz полностью совпадают с проекциями области ограничений. На проекциях сразу определяются минимумы и максимумы той или иной вершины. В состоянии "Расчет" эти значения автоматически заносятся в регистры p191 и p192 для дальнейшей работы с ними.

Следует заметить, что для нахождения экстремума трехмерной целевой функции не обязательно отображать ее в 4-мерном пространстве. Известно (и из чертежа на проекции xt понятно), что оптимальное решение сводится к поиску ближайшей или наиболее удаленной от плоскости сечения целевой функции вершины многогранника. Поэтому, если целевой функции придать какое-либо значение (t=сonst или, тоже самое, Q=const ), то это сечение является двумерной плоскостью в пространстве xyz.

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

В модуле Vec_Opt описанные преобразования можно выполнить по-другому: направление оси z изображения необходимо задать по вектору следа (или прямой уровня - горизонтали) плоскости. В этом случае данная плоскость проецируется на экран дисплея в прямую (вид на плоскость с ее "торца" ), по этому же направлению изобразится и фигура ограничений.

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


II. Решение задач линейного и нелинейного программирования  на основе вычислительных методов.

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

Пример 2. Пусть требуется структурировать область, ограниченную следующей системой неравенств:
x/100 + y/170 -1 < 0,  (1)
x/140 + y/120- 1  < 0,  (2)
x > 0,    (3)
y > 0.    (4)

Уравнения (1,2) можно представить как уравнения прямых в отрезках (см.рис.):

x/100 + y/170 = 1,
x/140 + y/120 = 1.

Уравнения (3, 4) представляют  оси координат.

Решая уравнения (1,2), можно найти точку р4  и свести область ограничений к 4-х угольнику. Однако, поступим следующим образом. Используя операции сканирования при изменяющемся уi и сравнений, можно осуществить перебор точек в определяемой области ограничений. Такой перебор в системе “Вектор” можно выполнить с помощью двух рекурсивных циклов.
 
 
 
 
Рис. 7
Однако известно, что искомое решение задач линейного программирования чаще лежит на внешней границе области выпуклого множества. Перебор точек на границе (рис. 7,б) можно осуществить уже с помощью одного цикла, т.е. задачу свести к одномерной.

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

Если ЦФ приравнять какому-либо числу, например, f(x,y)= x+y=200, то ее также можно записать уравнением прямой в отрезках x/200 + y/200 =1 и изобразить в координатной системе x,y отрезком прямой (рис.8).

Известно, что наибольшее (или наименьшее) значение функция f будет иметь  при тех значениях x и y области ограничений, когда точка (ребро) этой области будет находиться ближе (или дальше) от отрезка прямой ЦФ.

Условие зависимости расстояния s1 от отрезка прямой ЦФ до контура области ограничений можно отобразить графиком (рис. 3) (кстати, на рис. не совсем правильный, т.к. расстояние не выдерживают перпендикулярность от точек контура к ЦФ, равной с). Максимум на этом графике и даст искомую точку, в которой ЦФ будет максимальной.
Кроме того, вычисляя еще и значения ЦФ, можно отобразить ее графически также непосредственно над областью (контуром) ограничений.

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

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

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

Упражнение. Используя теоретико-множественные операции в системе “CG-Вектор”, смоделируйте область ограничений, представленную следующей системой уравнений-неравенств:

x > 0,    (5)
y > 0,    (6)
x/100+y/50+z/150-1 < 0,  (7)
x/150+y/100+z/100-1 <0.  (8)

Схема решения:
1) задаем параллелепипед, у которого стороны равны максимальным значениям области ограничений;
2) задаем два полупространства, у которых вектора нормалей определяются из соотношений: {1/a,  1/b, 1/c } или [bc, ac, ab] плоскостей (7) и (8);
3) пересечения параллелепипеда и полупространств в одной конъюнкции и определят искомую фигуру.


III.  Нелинейные задачи

Такие задачи имеют в своей основе нелинейные функции.

Пример 3. Задача "О почтовой посылке": найти  ее максимальный объем при ограничении на обхват и длину.

Постановка (формализация задачи)
Формулируем цель:
s=xyz->max
и ограничения:
x+2y+2z < 72,
0< x,y,z.

Задача является смешанной. ЦФ s  -нелинейная, а область ограничений - линейная. Область ограничений - многогранник, ограниченный координатными плоскостями x,y,z и плоскостью x/72+y/36+z/36=1.

Т.к. значения x,y,z должны быть больше нуля и точка, определяющая максимум ЦФ, должна лежать на поверхности многогранника, то заключаем, что положения точки, обеспечивающей максимум ЦФ, возможны на грани р1-р3 многогранника ограничений (рис.8).

Рис.8
Алгоритм решения задачи.
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.
3) В момент достижения максимального значения s выполняем принудительный выход из МК. Искомые значения x,y,z будут лежать в p.
4) Для контроля вычислений строим графики ЦФ в координатных плоскостях sx, sy, sz (рис. 9, а,б.с или (рис. 9, д) непосредственно над плоскостью р1-р3 в трехмерной координатной системе (аксонометрии) sxy.
 
 
Рис. Отображение ЦФ: s=x*y*z -> max на комплексном и ортогональном чертежах а) полностью, б) до достижения максимума.


IV. Задачи нелинейного программирования в многокритериальных задачах. ЦФ и ограничения нелинейные

Пусть задана ЦФ:
F (X) = {f1(X) = (x1 - 4)* (x1 - 4) + (x2 - 3)* (x2 - 3)* (x2 - 3),
               f2(X) =  x1*x1  + 9(x2 - 3)* (x2 - 3)* (x2 - 3),
               f3(X) = (x1 - 0.5)* (x1 - 0.5) + (x2 + 1)*(x2 + 1)*(x2 + 1) } -> min   (1)

при  следующих ограничениях:

   - 4*x1*x1- 9*x2*x2 + 36 > 0,                                      (2)
   - (x1- 1)*(x1- 1) - (x2+3)*(x2+3) + 20.25 = 0.            (3)

Требуется исследовать область ограничений, частные ЦФ и глобальную ЦФ. Найти минимум ГЦФ

Решение

Определяем область ограничений согласно системе уравнений-ограничений   (2,3)

Линия (2) определена в диапазоне
- 3 < x < 3
и ее уравнение как функция y(x) будет иметь вид:
y(x) = sqrt(4-0.44*x2)
Линия (3) определена в диапазоне

- 4.45  < x  < 4.45

и ее уравнение как функция y(x) будет определяться

y(x) = sqrt(20.25 - (x-1)*(x-1)) - 3

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


Пример 4. Задача Тартальи. Из чисел: 0 < x,y < 90 найти: Fmax=xy(y-x).
Задача нелинейная частично. Область ограничений можно представить уравнением:
x/90+y/90=1. Таким образом, перебирая точки на этом отрезке можно найти максимум или минимум заданного произведения. Решение данной задачи см. в практике 8.