Математическое программирование

• Название: Математическое программирование
• Анкор: Matematicheskoe_programmirovanie.doc
• Дата: 11.09.2018
• Размер: 227.5 Kb.
• Имя файла: Matematicheskoe_programmirovanie.doc
• Тип: Документы; #24433
• страница: 1 из 2

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Развитие относится к 30-ым годам. Математик – Толстой . Бурное развитие после войны. Всюду, где возникает необходимость выбора среди множества вариантов, решения какой либо проблемы (получения максимальной прибыли, минимальный расходы и.т.д) , выбор наилучшего в каком-то смысле – там и возникают задачи математического программирования.

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

Найти max или min функции Z=f() , где φ()b_i , где (i=1,k); φ()=b_i , где (i=1,k) (i=k+1, L);

- управляемый параметр. - неуправляемый параметр. (не учитывается)

Чтобы решить задачу имея математическую модель нужно знать математические метод (Гауса, Крамера, матричный и.т.д) Зная метод => нужно знать алгоритм.

КЛАССИФИКАЦИЯ МЕТОДОВ.

В зависимости от того какими являются функции f и φ_i , задачи делятся на два класса : 1) Если функции f и φ_i линейны относительно параметров Х и У , то имеем задачу линейного программирования. (Л.П.)

2) Если хотя бы одна из функций f и φ_i нелинейная относительно параметров и , то имеем нелинейную задачу. (Н.П.)

Для Л.П. существует универсальный способ. Симплекс – метод Основ. разработку дал Дансон.

Х3


Х2


Х1

В Н.П. самым изученным является выпуклое программирование – это когда находится минимум выпуклой функции на выпуклом множестве или максимум вогнутой функции на выпуклом множестве. Существуют так же :1) Д.П. – динамическое программирование , вся задача разбивается на n-этапов. 2) Стохастическое программирование – случайные параметры. 3) Э.П. – эвристическое программирование , где оптимальное решение найти сложно из-за большого количества вариантов. 4) Ц.П. – целочисленное программирование.

Транспортная задача.

Имеется два пункта однородного продукта. Мощность 1^го 400т.; 2^го – 500т., имеется 3 пункта потребления этого продукта. Известны затраты на перевозку 1т. продукции . Из 1^го пункта к 1^му – 2млн. р. ; 2^му – 3 млн. р; 3^му – 4 млн. р. Из 2^го - 1^му – 5 млн. р.;2^му- 4 млн. р.; 3^му- 2 млн. р. Спланировать перевод таким образом, чтобы суммарные затраты были минимальными.

1) нужно 300 т. 2) нужно 400 3) нужно 200 т.

Математическая модель.

Х_ij – кол-во тонн продукции перевезенной из пункта i к пункту j- му потребителю. Найти план перевозок. (матрицу Х) Х= х₁₁ х₁₂ х₁₃ Предложение = спросу.

Х₂₁ х₂₂ х₂₃ 900 900
Если спрос и предложение совпадают , то имеем закрытую модель, иначе открытая модель. В закрытом моделирование все выражения равенства.

bj ai	b1 300	b2 400	b3 200
400	2 x11	3 x12	4 x13
500	5 x21	4 x22	2 x23

b –потребность . =
х₁₁+x₁₂+x₁₃=400

x₂₁+x₂₂+x₂₃=500

2 x₁₁+x₂₁=300

x₁₂+x₂₂=400

x₁₃+x₂₃=200

3. 
   x_ij>=0 (i=) (j=)
   

Функция цели 1 Z=2x₁₁+3x12+4x13+5x21+4x22+2x23 -> min

3. 
   математическое моделирование задачи.
   

Различают другие типы задач :

1) задачи о диете или о рациональном питании.

2) задачи производственного планирования

3) на составление математического моделирования

4) задачи о раскрое

5) задачи о назначениях.
Метод Гауса.

М.Г. вычисляется с помощью таблиц Гауса.

2х1-х2+х3=3

х1+3х2-2х3=1 разрешающий элемнт.

х2+2х3=8 разрешающая строка разреш.столбец.

Х1	Х2	Х3	Св.чл		проверка
2	-1	1	3	5	5
1	3	-2	1	3	3
0	1	2	8	11	11
0	-7	5	1	-1	-1
1	3	-2	1	3	3
0	1	2	8	11	11
0	0	19	57	76	76
1	0	-8	-23	-30	-30
0	1	2	8	11	11
0	0	1	3	4	4
1	0	0	1	2	2
0	1	0	2	3	3

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

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

Стандартная форма модели З.Л.П. . Система задачи формируется : Найти вектор х, удовлетворяющий системе ограничений и условию не отрицательности.



а11х1+а12х2+…+а1nxn<=b1

a21x1+a22x2+…+a2nxn<=b2

….

am1x1+am2x2+…+amnxn<=bn

xj>=0 j=1,4; Z=c1x1+c2x2+..+cnxn->max

A-матрица (m*n) Z=cx->max Ax<=b x>=0 ; C=(C1 C2 …Cn) b(b1 b2..bm)

Каноническая тоже самое только в системе ограничений = и Ax=b.

Общая форма. Найти вектор Х, удовлетворяющий системе ограничений
a11x1+a12x2+...+a1nxn=b1

am1x1+amnxn=bm

Xj>=0 (j=1,l) l max
Для того что бы решать задачи Л.П. симплекс методом необходимо иметь каноническую форму модели, поэтому необходимо знать , как перейти от одной формы модели к другой .

Переход от стандартной формы к канонической форме.

1. 
   ai1x1+ai2x2+…+ainxn<=bi (2)
   

ai1x1+ai2x2+..+ainxn+ainxi+n=b xn+i>=0 , i=1,m – балансовые переменные. (1)

Можно доказать, что все решения системы 1 равны решениям неравенства 2 и в этом сысле они эквивалентны. Функцию цели эти переменные(xn+i) могут быть введены с коэффициентами =0 => z=c1x1+..+cnxn+oXn+1+..+oxn+m->max

Переход от канонической к стандартной.

Осуществляется двумя способами.

1. а=b (a>=b a<=b) -> a1x1+a2x2=b a1x1+a2x2>=b

a1x1+a2x2<=b

2. Z=c1x1+…+cnxn->max

a11x1+…+a1nxn=b1

a21x1+…+a2nxn=b2

am1x1+…+amnxn=bm (m

1. 
   Приводим к единичному базису методом гауса. Приравняем все свободные переменные к 0, т.е. xm+1=xm+2=0 то получим первоначальное базисное решение.
   
2. 
   Выражаем все базисные переменные через свободные.
   

Х1=b1-a1,m+1xm+1-..-a1,nxn>=0

Xm=bm-am,m+1-…-amnxn>=0

3. 
   В функция цели вместо базисных переменных подставить их через переменные.
   

Z=c1(b1-..-a1nxn)+c2(b2-..-a2nxn)+cm(bm-..-amnxn)+cm+1xm+1+…+cnxn->max/

Переход от задачи max к min и наоборот.

Во всех формах моделях все сводится к max, но иногда необходимо найти min/



Z=f(x)

min




z1max

z1=f(x)
Чтобы перейти от задачи min к max достаточно поменять знак и ввести новое значение функции.

Графический метод решения Л.П.

Понятие: допустимого , оптимального , опорного решений, понятие области допустимых решений.

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

Вектор Х называется оптимальным решением если он является допустимым , а функция цели в этом решении достигает своего оптимального значения. (max or min)

Опорным решением называется не отрицательное базисное решение системы ограничений.




x1+x3 –x4=1

x2+2x3+4x4=-2

x1 и х2 –базисные неизвестные. Х3,х4 - неизвестные .

Приравняем свободные к 0. , тогда базисные неизвестные получают значения равные х1=1 х2=-2 и получаем базисное решение. Оно является не опорным , т.к. х=-2. Данное решение допустимое , базисное, не опорное.

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

Геометрическая интерпретация линейного неравенства.

n=2a1x1+a2x2<=b (n-кол-во переменных , m число неравенств )

Из математики знаем что геометрическим образом уравнение а1х1+а2х2=b – прямая на плоскости х1 х2 Прямая разбивает плоскость на две полуплоскости . а1х1+а2х2<=b и >= , т.е. одно из плоскостей является решением. Чтобы определить какая четверть является решением данного неравенства нужно взять любую точку M и подставить в данное неравенство. И если не равенство удовлетворяется, то точка эта принадлежит той полуплоскости в которая является решением . И наоборот.

Геометрическая интерпретация системы линейны неравенств.

n=2 . a1x1+a1x2<=b1 ГИСЛН – является пересечение всех полуплоскостей соответству

a2x1+a2x2<=b2 ющих каждому неравенству системы , таким образом нашли ОДР.

am1x1+am2x2<=bm

Возможные случаи ОДР.

1. 
   ОДР является точка.
   
2. 
   ОДР выпуклый многоугольник.
   
3. 
   ОДР выпуклая многоугольная область.
   
4. 
   ОДР – пустая область
   

Графический метод .

ГМ состоит из двух этапов.

1. 
   ОДР.
   
2. 
   Среди всех решений необходимо найти такое решение при котором Z достигает своего либо max или min.
   

Grad показывает наискорейшее возрастание функции. (С – коэффициент) (линии уровня)

Возможные случаи

1. 
   задача имеет единственное решение.
   
2. 
   Задача имеет – бесконечно много решений.
   
3. 
   Задача не имеет решений а) нет ОДР б) в случаи когда zmax - ф-ия не ограниченной сверху линией уровня и наоборот.
   

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

ОПОРНЫЙ ПЛАН.

Свойства допустимых планов.

1. 
   Выпуклая линейная комбинация точек . х1 х2 …хk сумма вида α1х1+ α2х2+ ...+ αkxk , где αi =1 (αi>=0 αi – коэффициент линейной комбинации).
   
2. 
   Выпуклым множеством называется такое множество т. Д на плоскости , когда вместе с любыми двумя точками Х1є Д ; Х2 є Д принадлежащим множеству Д. Ему принадлежит и их выпуклая Л.К. х=tx1+(1-t)x2 є Д 0<=t<=1
   
3. 
   Крайняя точка – т.Х выпуклого множества называется крайней если она не может быть представлена в виде выпуклой Л.К. любых двух точек этого множества (n=2)
   

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

Свойства допустимых планов.

Теорема №1

Множество допустимых планов З.Л.П. выпукла если оно не пусто.

Дано: Д- не является пустым множеством – ОДР

Доказать Ж Д- выпуклое множество.

Док-во :

Х1 єД; Х2 єД,то оно удовлетворяет системе ограничений в З.Л.П. Z=cx->max Ax=b X>=0

Ax1=b 0<=t<=1

Ax2=b (1-t) => tAx1+(1-t)Ax2=bt+b(1-t) = A[tx1+(1-t)x2]=b

t>=0

x1; x2>=0 => x>=0

1-t>=0

Ax=b X- решение задачи.

Х = tx1+(1-t)x2 0<=t<=1, согласно опр. Имеем выпуклое множество – Д, т.к. с любыми двумя точками ему принадлежит и их выпуклая Л.К.

Теорема № 2

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

Дано: Zmax->X₀ Док-ть X_0- вершина.

Zmax=C X₀

Док-во: Дан многогранник. А,В,С,Д,Е – вершины. (Док-во проведем от противного)

X₀ – не вершина , тогда согласно опр. Крайней точки , X₀ – не крайняя точка , и может быть представлена в виде выпуклой Л.К. точек хi є ОДР

C X₀>Cxi (т.к. С X₀ ->max)

X₀ = αiXi αi=1 αi>=0

Найдем значение функции Z=C X₀=CαiXi=αiCXi<αiCX₀=CX₀αi=CX₀

В каждом слагаемом сменим Xi на Х₀

СХ₀0 – противоречие.

Теорема №3

Об альтернативном оптимуме.

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

Дано : Док-ть: х= αiXi

Xi , i:=1,k αi=1 αi>=0 CX=d

Zmax=C{i=d

Док-во

Найдем Z=СХ=CαiXi=αiCXi=αid=dαi=d

Теорема № 4

Вектор Х является опорным решением тогда и только тогда , если он является вершиной многогранника.

Если переменных n>3 то говорят гиперплоскость, положение точек в т – мерном пространстве.

ИДЕЯ СИМПЛЕКС МЕТОДА.

Симплекс метод является универсальным.

Симплекс метод – аналитический метод.

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

Б)Преобразовать что бы bi >=0 i=1,m

С)Привести систему к единичному базисному виду с неотрицательной правой частью.

Поэтому за разрешающий элемент выбирается строго положительный элемент.

Д)Приравниваем свободные к 0 , получаем первоначальное базисное неотрицательное

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

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

Алгебра симплекс метода.

Х1	Х2	Х3	Х4	Х5	св.чл
1	0	1	6	2	8
0	1	1	0	3	9
0	0	7	-1	-3	-0
1	-2/3	1/3	6	0	2
0	1/3	1/3	0	1	3
0	1	8	-1	0	9
1/6	-2/18	1/18	1	1/3
			0	1	-9
1/6	8/9	8 1/8	0	0	1/3

Особенность выделенная клетка.

1. 
   Чтобы решать симплекс методом необходимо Z->min (перейти к min)
   
2. 
   В строке Z записываются коэффициенты ф-ии цели, а свободный член записывается в выделенную клетку св.чл. с противоположным знаком.
   
3. 
   Сделаем свободные члены неотрицательными.
   
4. 
   Приводим систему ограничений к единичному базису методом Гауса, выбирая за разрешающий элемент положительный элемент.
   
5. 
   Функция цели должна быть выражена только через свободные неизвестные , чтобы определить оптимален ли полученный опорный план. Для определения опорного плана свободные элементы =0 r=(7;-1;-3} Среди них выбираем самый отрицательный и делаем разрешающий столбец. Для выбора разрешающей строки находится min-ое из отношений свободных членов системы ограничений к положительным коэффициентам разрешающего столбца
   
6. 
   Для выбора разрешающей строки находится min-ое из отношений свободных членов системы ограничений к положительным коэффициентам разрешающего столбца.
   

Альтернативный оптимум.

Предположим найдено оптимальное решение. r>=0. Признаком альтернативного оптимума в этом случаи является равенство 0, хотя бы одной из компонент вектора r. Покажем что если компонента rj =0 , для найденого оптимального плана (Х^*₁) то можно найти еще одно оптимальное решение Х^*₂ , значение в котором будет таким же как и значение в Х^*₁. Z(Х^*₂)= Z (Х^*₁₎=Zmin

За разрешающий столбец берем rj =0 Zmin=Z(X^*₁)=-Q (свободный член в Z) Q¹=aij*Q-bi*rj/aij = Q-(bi*rj/aij)=Q bi>0 aij>=0

Сделав шаг метода Гауса , получим новое решение , а значение функции в т Х^*₂ будет точно таким же как и в Х^*₂ – т.е. задача Альтернативного оптимума.

Монотонность и конечность алгоритма симплекс метода.

Покажем , что применяя алгоритм симплекс метода к З.Л.П. мы получим , что значение функции монотонно убывает. Предположим, что на кокаком то шаге симплекс метода выбран разрешающий столбец rj<0 , а за разрешающую строку выбрана i строка. Покажем что значение функции не возрастает , если мы применим один шаг симплекс метода. Qнов=aij*Q-bi*rj/aij= Q-bi-rj/aij<=0 (bi>=0 rj<0 aij>=0) Qнов>=Q -Qнов<=-Q

Так как многогранник имеет конечное число вершин , то алгоритм симплекс метода будет конечен.

Проблема выражденности.

Если получено в опорном плане число положительных координат меньше чем m , то решение является выражденным , и если полученный план не является оптимальным , т.е. возникает необходимость к новому опорному плану и при этом за разрешающую строку выбирается строка в которой bi=0 Тогда моежт быть проблема зацикливания, т.е. возврат к прежней вершине , для того чтобы избежать этого нужно «расклеить» точки для чего служит ипсилон метод. На ипсилон величину сдвигают прямые , таким образом чтобы раздвигаются вершины. Находят оптимальное решение новой задачи и учитывая ипсилон переходя к страой задаче.
Если в конце преобразований получена таблица , то столбец соответсвующем столбце нет ни одного положительного элемента то Zmin->- бесконечности ( нет решения)

Если в результате преобразований сстрока превратилась ( 0 0 0 0 = 7), то задача не имеет решения по причине не совместимости систем . Нет ОДР.

Если оптимальное решение и соответствующий ему вектор (r) имеет 0 координату то задача на альтернативный оптимум. Что бы найти второе решение берем за разрешающий столбец 0.

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

Z=CX->min В данной задаче нет естественного базиса. Введем в каждое ограничение

Ax=b искусственную переменную «у»>=0 Z преобразуем в T. М – полож. большое чис

X>=0 -Z задача.
Ах+у=b

Х>=0 у>=0

T=CX+M*y->min (М –задача)
Теорема . Если М задача имеет оптимальное решение , то Z – задача : а) тоже имеет решение , если все искусственные переменные = 0. Б) Z- задача не имеет решения если хотя бы одна из искусственных переменных не равна 0, систем ограничений будет не совместна. Если М задача не имеет решения ,т.е. Tmin ->-бесконечности , то и Z- задача тоже не имеет решения.


ТЕОРИЯ ДВОЙСТВЕННОСТИ .

Каждой задаче Л.П. можно поставить в соответствие двойственную задачу , решения которой дает немедленное решение прямой задачи.

Стандартная форма.

Z=CX->max

Ax<=b

x>=0 1)

Двойственной задачей к данной З.Л.П. называется задача вида

w=yb->min

YA>=C

Y>=0 2)

Задача 1) и 2) называется пара двойственных задач.

Если по этим правилам построить двойственную задачу к 2) то получим 1) . И в этом смысле задачи называются взаимозаменяемыми или сопряженными.

(y- строка)

(y1,y2..ym) a11

a21

am1

Экономический смысл : Экономически двойственную и прямую задачу можно интерпретировать прямая на max прибыль. , при выпуске х1 х2 х3 , а двойственную min -> расходов на ресурсы.

1. 
   b – сырье ; у1 у2 – оценка ресурсов.
   

Правило построения двойственных задач к общей З.Л.П.

1. 
   Количество переменных в двойственной задаче равно количеству ограничений в прямой задаче.
   
2. 
   Количество ограничений двойственной задачи равно числу переменных в прямой задачи.
   
3. 
   Вектор свободных элементов прямой задачи b является вектором коэффициентов двойственной задачи.
   
4. 
   Вектор коэффициентов функции цели C=(C1…Cn) прямой задачи служит вектором свободных членов системы ограничений двойственной задачи.
   
5. 
   Если прямой Z->max то в Д.З. W->min/
   
6. 
   Каждому ограничению – неравенству ai1x1+a12x2+..+ainxm , i=1,m Соответствует неотрицательная переменная yi>=0 ; i=1,m Д.З.
   
7. 
   Каждой неотрицательной переменной (xj>=0) j=1,n прямой задачи соответствует ограничения неравенства Д.З. a1jy1+a2jy2+…+amjym>=Cj (j=1,n)
   
8. 
   Матрица системы ограничений Д.З. служит транспонированная матрица прямой задачи.
   
9. 
   Каждом ограничению равенству прямой задачи ai1x1+ai2x2+…+ainxn=bi (i=1,m) соответствует свободная переменная yi><0
   
10. 
    Каждой свободной переменной xj><0 (j=1,n) соответствует ограничение равенства a1j+a2j+…+amjym=Cj
    

ТЕОРЕМА ДВОЙСТВЕННОСТИ.

1. Если прямая и двойственная задача имеют допустимые решения Х и У , то они имеют оптимальное решение Х^* и У^* и причем значение функции в этих точках совпадают. Zmax=Wmin CX^*=Y^*b

Лемма №1

Для любых двух допустимых решений Х и У пары Д.З. справедливо СХ<=Уb

Док-во:

Z=CX->max W=yb->min

Ax<=b YA>=C

x>=0 y>=0

Допустим что X¹ – любое допустимое решение П.З. , а Y¹ – для Д.З.

Тогда Х¹ удовлетворяет системе ограничений , т.е. АХ¹<=b ¦ y¹>=0 Y¹A>=C¦x¹>=0

Первое ограничение умножим на y¹

Y¹Ax¹<=y¹b

Y¹Ax¹>=Cx¹

Cx¹<=T<=y¹b => Cx¹<=y¹b

Лемма № 2

Если для допустимых решений X^* и У ^* , выполняется условие равенства СХ^* =У^*b , то Х^* и У^* являются оптимальными решениями пары двойственных задач.

Док-во : Дана пара Д.З. Х^* и У^* допустимые решения. СХ^*=У^*b , док-ть Х^* и У^* оптим. решение

Предположим что Х- ОДР (любое) , тогда по первой лемме СХ<=У^*b , но У^*b=Cx^* => Cx=Cx^* отсюда следует , что Х^* т. максимума => у^* т. минимума.

На основании графического анализа Д.З. исследовать разрешимость данной задачи в случаи разрешимости – найти экстремальные значение целевой функции.

2.