Разделы презентаций


Математическое программирование (математическая теория принятия оптимальных

Содержание

Примеры задач математического программирования Задача планирования производства (оптимальное использование ресурсов)2. Задача распределения работ.3. Задача оптимального распределения финансовых ресурсов.

Слайды и текст этой презентации

Слайд 1Математическое программирование (математическая теория принятия оптимальных решений)


Проф. Сагитов Р.В.

Математическое программирование (математическая теория принятия оптимальных решений)

Слайд 2Примеры задач математического программирования
Задача планирования производства
(оптимальное использование

ресурсов)
2. Задача распределения работ.
3. Задача оптимального распределения финансовых ресурсов.

Примеры задач математического программирования Задача планирования производства (оптимальное использование ресурсов)2. Задача распределения работ.3. Задача оптимального распределения финансовых

Слайд 3Общая задача линейного программирования
Линейная форма

Система условий
(система ограничений)







Условия ограничений

по знаку

Общая задача линейного программированияЛинейная форма Система условий(система ограничений)Условия ограничений  по знаку

Слайд 4Каноническая задача линейного программирования

Каноническая задача линейного программирования

Слайд 5Основные определения
Допустимое решение (план) – вектор
Х = (х1,

х2,…,хn) -удовлетворяющий системе ограничений ЗЛП.
Решение ЗЛП (оптимальный план) – вектор

Х* = (х1*, х2*,…,хn*) , доставляющий максимальное значение линейной форме
т.е. Z( Х* ) = max Z(X)
Основные определенияДопустимое решение (план) – вектор  Х = (х1, х2,…,хn) -удовлетворяющий системе ограничений ЗЛП.Решение ЗЛП (оптимальный

Слайд 6Теорема 1: Всякая задача линейного программирования может быть приведена к

каноническому виду.
1.1. Задача минимизации Z(x) →max равносильна задаче

- Z(x) →min
1.2. Неравенство равносильно уравнению и неравенству
1.3 Переменная, на которую не наложено условие неотрицательности, можно представить в виде хj= х1j – х2j ;
Теорема 1: Всякая задача линейного программирования может быть приведена к каноническому виду.1.1. Задача минимизации Z(x) →max равносильна

Слайд 7Различные формы записи ЗЛП
Общая 2. Каноническая .3.Симмет

ричная
Z(x) →extr Z(Х) →max Z(Х)→max
AX≤B AX=B AX≤B
AX≥B X≥0 X≥0
AX=B
Различные формы записи ЗЛПОбщая  2. Каноническая .3.Симмет

Слайд 8Геометрические свойства З.Л.П
Рассмотрим симметричную форму задания задачи линейного программирования в

матричном виде

Z(х) →max
АХ ≤ В
X ≥0
Пусть переменных n=2 .

G

Геометрические свойства З.Л.ПРассмотрим симметричную форму задания задачи линейного программирования в матричном виде

Слайд 9Геометрический способ решения задачи линейного программирования
n=2

x2 l1

l2 Z* l3
G X*(x1*,x2* )
Z1=0
Z2 l4

l5


x1
Геометрический способ решения задачи линейного программированияn=2     x2     l1

Слайд 10Геометрический способ решения
n=2 x2


G



x1
Z(X) → ∞
Геометрический способ решения n=2    x2

Слайд 11Геометрический способ решения
n = 2 x2

G = Θ


x1
ЗЛП неразрешима из-за противоречивости условий системы ограничений
Геометрический способ решения n = 2   x2

Слайд 12Геометрический способ решения З.Л.П( в пространстве)
n=3

X3

X* оптимальный план
G Z*= Z(Х*)=maxZ(X)


Z1
X2
X1

Геометрический способ решения З.Л.П( в пространстве)n=3  X3

Слайд 13Выпуклые множества
Геометрическое представление

Х2

Х3
Х"
Х1 Х'
Х5 Х4
Х"
Х' Х"

Х'


Х' Х"

Алгебраическое представление
Определение Множество отрезок имеет вид
Х(Θ) = ΘХ' +(1-Θ)Х"
Θ Є [0;1]
Определение: Множество называется выпуклым, если вместе с двумя произволь- ными точками этого множества ему принадлежит и отрезок, соединяющий их.
Определение:Выпуклой комбинацией называется выражение вида
Хо = k1Х1 +k2 Х2 +…+kr Хr ki ≥0 i=1,2,…,r Σki = 1.


Выпуклые множестваГеометрическое представление       Х2

Слайд 14Свойства З.Л.П
1.Теорема 1. Множество планов З.Л.П – выпуклое множество.
2. Лемма.

Всякая точка выпуклого множества может быть представлена в виде выпуклой

комбинации угловых точек множества.
3. Теорема 2. Решение З.Л.П. достигается в угловой точке множества планов З.Л.П.
Свойства З.Л.П1.Теорема 1. Множество планов З.Л.П – выпуклое множество.2. Лемма. Всякая точка выпуклого множества может быть представлена

Слайд 15Опорные планы З.Л.П.
Определение: все угловые точки множества планов З.Л.П называются

опор-ными планами З.Л.П.
Опорным планом называе тся такой план ЗЛП, для

которого не найдется двух различных планов таких, что опорный план будет внутренней точ- кой отрезка соединяю-щего их

Геометрическое представление




Х2
Х1
Х3

xo

Опорные планы З.Л.П.Определение: все угловые точки множества планов З.Л.П называются опор-ными планами З.Л.П.Опорным планом называе тся такой

Слайд 16Критерий опорности плана З.Л.П
Теорема 3 ( критерий опорности плана ЗЛП)
Для

того чтобы план ЗЛП был опорным, необходимо и достаточно, чтобы

векторы условий, отвечающие положительным компонентам плана были линейно независимыми.

Критерий опорности плана З.Л.ПТеорема 3 ( критерий опорности плана ЗЛП)Для того чтобы план ЗЛП был опорным, необходимо

Слайд 17Пример
G

Пример G

Слайд 18Алгебраическая характеристика опорного плана
Z(x)= 3х1+х2-2х3→max

2x1 - x2 + x3 =

1
x1+2x2 – x3 = 3
xj ≥ 0

j=1,2,3

Z(x)= 3х1+х2-2х3→max

x2 - (3/5)x3 = 1
x1 +(1/5)x3 = 1
xj ≥ 0 j=1,2,3

Xo = (1,1,0) Бхо (А1,А2)
Z(Xo) = 4.

Алгебраическая характеристика опорного планаZ(x)= 3х1+х2-2х3→max2x1 - x2 + x3 = 1 x1+2x2 – x3 = 3

Слайд 19Базис опорного плана
Хо= (х1о;х2о;…хno) – опорный план.
Если хј > 0,

то Ај = Аѕі , если хј = 0,

то Ај ≠ Аѕі
Определение: Векторы, отвечающие положительным компонентам плана образуют базис опорного плана
Х1=(1,0,0,1) – базис Бх1 = {А1=Аѕ1;А4 =Аѕ2 } таким образом Бх1 ={Аѕ1 Аѕ2}.
Х2=(0,5,0,0) – вектор А2 = Аѕ1 войдет в базис, но его требуется дополнить еще каким либо вектором Бх2 = {А2 = Аѕ1 ; А? = Аѕ2}
Базис опорного планаХо= (х1о;х2о;…хno) – опорный план.Если хј > 0,  то Ај = Аѕі , если

Слайд 20Переход от одного опорного плана к другому
ХО = (х1о;х2о;..xsⓡ..;хno)
Б(хо)= (Аѕ₁

Аѕ₂…Аѕⓡ..Аѕm)
хiо≥0 Аѕi лин. незав.
i = 1,2,…m

Х1 =

( х11;х21;..Θ..,хn1)
Б(х1)= (Аѕ₁ Аѕ₂…Аk..Аѕm)
Хi1 ≥ 0 Аѕi лин. незав.
i = 1,2,…m


Геометрическое представление
А1
А2

А2
Ао
А3 А3

Переход от одного опорного плана к другомуХО = (х1о;х2о;..xsⓡ..;хno)Б(хо)= (Аѕ₁ Аѕ₂…Аѕⓡ..Аѕm)хiо≥0  Аѕi  лин. незав. i

Слайд 21Преобразование опорного плана
Пусть дана каноническая ЗЛП


Z(Х) = Σсj

хj → max

A1x1 +A2x2 +…+ Amxm +…+ Anxn = B
G хj ≥ 0 j = 1,2,…,n

А1 ,А2 ,…,Аm ,…,Аn – векторы условий
В – вектор ограничений

Преобразование опорного планаПусть дана каноническая ЗЛП

Слайд 22Преобразование опорного плана
Пусть дан опорный план Хо =(х1ох2о... х®о..хmо 0…0)
Базис

плана Б(Хо)={Аs1;Аs2;…;Аsr;…;Аsm }

{ X(Θ) = (Xo - Θαk) ; Θ } Є G

αk =(α1k; α2k;… αrk;…αmk )
Аs1 α1k +Аs2 α2k+…+Аsrαrk+…Аsmαmk = Ak


Аs1 х1о +Аs2 х2о+…+Аsrхsr+…+Аsmхmo +Am+1 0+…+An0 =В

Аs1 α1k +Аs2 α2k+…+Аsrαrk+…+Аsmαmk – Ak = 0


Преобразование опорного планаПусть дан опорный план Хо =(х1ох2о... х®о..хmо 0…0)Базис плана Б(Хо)={Аs1;Аs2;…;Аsr;…;Аsm }

Слайд 23Преобразование опорного плана

As1x1o+As2x2o+…+Asrxro …+A smxmo +

ΣAj0 = B

(As1α1k+As2α2k+…+Asrαrk …+A smαmk -

Ak = 0)Θ

Аs1(x1o-Θα1k)+ …+ Asr(xro-Θαrk)+…+AkΘ = B
(xio- Θαik) ≥ 0 i=1,2,…,m и Θ≥0

Θ≤ выберем Θо = min =
αik>0

(1)

(2)

Преобразование опорного плана    As1x1o+As2x2o+…+Asrxro …+A smxmo + ΣAj0 = B    (As1α1k+As2α2k+…+Asrαrk

Слайд 24Что при этом произойдет с Z(X)?
Подставим новый план

{ X(Θo) = (Xo - Θoαk) ; Θo

} Є G в Z(X) !

Z(X(Θ)) = Σcj(xj(Θo )) =





Z(X(Θo))= Z(Xo) – ΘΔk , где Δk =

Что при этом произойдет с Z(X)? Подставим новый план    { X(Θo) = (Xo -

Слайд 25Признак оптимальности плана
Теорема Если для плана Хо выполняется условие Δj

≥ 0 при j = 1,2,…,n ,то план Хо= Х*

т.е. оптимальный план.
Следствие Если существует Δк < 0 и при этом все αik≤ 0 , то ЗЛП не имеет решения из-за неограниченности линейной формы на множестве планов.
(Z(X) → ∞)
Признак оптимальности планаТеорема Если для плана Хо выполняется условие Δj ≥ 0 при j = 1,2,…,n ,то

Слайд 26Основоположники
Л.В.Канторович (1912-1986) академик РАН, Нобелевский лауреат- Российский математик

Джорж Данциг(1914-2005) американский

математик

ОсновоположникиЛ.В.Канторович (1912-1986) академик РАН, Нобелевский лауреат- Российский математикДжорж Данциг(1914-2005) американский математик

Слайд 27Блок-схема алгоритма симплекс-метода
1.
Определение первоначального опорного плана


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

Исследование плана на оптимальность

Вычисление оценки

Δj =

1

2

Блок-схема алгоритма симплекс-метода1.Определение     первоначального опорного плана

Слайд 28
Δj
Δj ≥ 0 j=1,2,...n X

= X*

αij
Δj < 0
Δk


Δk<0 αik>0

Выбор вектора вводимого в базис

3

ΔjΔj ≥ 0 j=1,2,...n   X = X*  αijΔj < 0Δk

Слайд 29Выбор вектора выводимого из базиса
4
Пересчет таблицы
По формулам

Жордана-Гаусса
5
Контроль вычислений
В блок 2
6

Выбор вектора выводимого из базиса 4Пересчет   таблицыПо формулам Жордана-Гаусса5Контроль вычислений  В блок 26

Слайд 30Таблица МПУП (симплексная таблица)
С1 С2

C3

Ск Сn
А1 А2 A3 Ак Аn

Б(Х)

Csi

Ao

Θ

As1
As2

Asr

Asm

Δk

cs1 x1o α11 1 0 α1k α1n
cs2 x2o α21 0 1 α2k α2n

csr xro αro 0 0 αrk αrn

csm xmo αmo 0 0 αmk<0 αmn
Δ1>0 0 0 Δk<0 Δn>0






х10 α1к х20 α2к

Xro
αrk

Таблица МПУП (симплексная таблица)  С1    С2      C3

Слайд 31Определение первоначального опорного плана
Если ЗЛП задана в симметричном виде

Z(х) →max
АХ ≤ В
X ≥0
Если все компоненты вектора В положи-телны, тогда в каждое уравнение вводится дополнительная переменная и первоначальный план очевиден.

Определение первоначального опорного планаЕсли ЗЛП задана в симметричном виде

Слайд 32Определение первоначального опорного плана
Если ЗЛП задана в каноническом виде

Z(х) →max
АХ = В
X ≥0
Тогда рассматривают вспомогательную задачу с искусственным базисом, который получается путем введения в каждое уравнение искусственной переменной.
Определение первоначального опорного планаЕсли ЗЛП задана в каноническом виде

Слайд 33Теорема о решении вспомогательной задачи
Если в оптимальном плане вспомогательной задачи

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

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

Слайд 34ПРИМЕР
Исходная

Вспомогательная
Z(X) = 3x1+x2

+2x3 →max Z(X)= -x4 – x7→max
x1 + x2 + x3 = 3 x1 + x2 + x3 + x4 = 3
Gиз x1 + x2 ≤ 1 x1 + x2 + x5 =1
x1 – x2 + x3 ≥ 1 Gвз x1 – x2 + x3 – x6 + x7 = 1
xj ≥ 0 j=1,2,3 xj ≥ 0 j=1,2,3,…,7

Xo = (0,0,0,3,1,0,1)

ПРИМЕР  Исходная

Слайд 35Двойственность в линейном программировании
Исходная задача






Хj ≥ 0

j = 1,2,…,n1




Двойственная задача


yi ≥ 0 i

= 1,2,…,m1


yi не ограничены по знаку
i = m1 +1,m1 +2,…,m








Двойственность в линейном программированииИсходная задача  Хj ≥ 0   j = 1,2,…,n1Двойственная задачаyi ≥ 0

Слайд 36Свойства пары взаимно двойственных задач
1.Z(x) ≤ Ž(y) для любых X

Є Gи.з. и У Є Gд.з.


2.Если для Xо Є Gи.з.

и Уо Є Gд.з Z(xо) = Ž(yо), то Хо = Х*, а Уо = У*.

3.Если Ž(y) → -∞, то Gи.з = О
Замечание: В обратную сторону свойство 3 не всегда выполняется
Свойства пары взаимно двойственных задач1.Z(x) ≤ Ž(y) для любых X Є Gи.з. и У Є Gд.з.2.Если для

Слайд 37Теоремы двойственности
Первая теорема двойственности.
Если одна из пары двойственных задач

разрешима, то разрешима и двойственная к ней, при этом Z(Х*)

= Ž(У*) .
Если одна из пары двойственных задач не имеет решения, то неразрешима и двойственная к ней.
Теоремы двойственностиПервая теорема двойственности. Если одна из пары двойственных задач разрешима, то разрешима и двойственная к ней,

Слайд 38Теоремы двойственности
Вторая теорема двойственности: для того чтобы планы задач ХЄGиз

и УЄGдз были оптимальными планами соответствующих задач, необходимо и достаточно,

чтобы выполнялись следующие равенства:

х*j ( ;

y*i( .

Теоремы двойственностиВторая теорема двойственности: для того чтобы планы задач ХЄGиз и УЄGдз были оптимальными планами соответствующих задач,

Слайд 39Условия дополнительной нежёсткости
Если строчное условие i исходной задачи выполняется как

неравенство Σаijx*j< bi , то переменная у*i = 0.

Если строчное

условие i исходной задачи выполняется как равенство Σаijx*j= bi , то переменная у*i > 0.
Условия дополнительной нежёсткостиЕсли строчное условие i исходной задачи выполняется как неравенство Σаijx*j< bi , то переменная у*i

Слайд 40Условия дополнительной нежёсткости
Если столбцовое условие j исходной задачи выполняется как

неравенство хj>0, то условие j двойственной выполняется как равенство Σаij

у*i= сj
Если столбцовое условие j исходной задачи выполняется как равенство хj=0, то условие j двойственной выполняется как неравенство Σаij у*I > сj


Условия дополнительной нежёсткостиЕсли столбцовое условие j исходной задачи выполняется как неравенство хj>0, то условие j двойственной выполняется

Слайд 41Теоремы двойственности
Рассмотрим пару двойственных задач



yi ≥ 0 i = 1,2,…,m


Хj ≥ 0 j = 1,2,…,n


Введем функцию М(В) = max{Z(X)}
XЄG BЄB

из

Теоремы двойственностиРассмотрим пару двойственных задач

Слайд 42Теоремы двойственности
Теорема об оптимальных оценках
(Третья теорема двойственности)
Если невырожденная задача линейного

программирования разрешима,
∂М(В)

/ ∂bi = yi*
Замечание: ΔВ велико, то теорема не имеет применения – область устойчивости оценок А-1ΔВ ≥ 0
Теоремы двойственностиТеорема об оптимальных оценках(Третья теорема двойственности)Если невырожденная задача линейного программирования разрешима,

Слайд 43Транспортная задача (матричная форма)
аi
bj

b1

b2 … bn
Транспортная задача (матричная форма)аi   bj         b1

Слайд 44Транспортная задача (сетевая форма)
Дана транспортная сеть
19
21
16
32
15
34
3
31
12
11
5
9
7
10
6
8
13
Поставщики
Потребители

Транспортная задача (сетевая форма)Дана транспортная сеть1921163215343311211597106813ПоставщикиПотребители

Слайд 45Математическая модель Т-задачи (матричная форма)
Z(X) =







xij ≥ 0 i=1,2,…,m
j=1,2,…,n
Математическая модель Т-задачи (матричная форма)Z(X) =

Слайд 46Свойства Т - задачи
Теорема: Для того чтобы Т-задача была разрешима

необходимо о достаточно, чтобы выполнялось условие баланса

Σ аі = Σ bj

Теорема: Ранг системы условий (ограничений ) Т – задачи равен m+n-1

i

j

Свойства Т - задачиТеорема: Для того чтобы Т-задача была разрешима необходимо о достаточно, чтобы выполнялось условие баланса

Слайд 47Методы построения первоначального опорного плана Т-задачи
Метод северо-западного угла.
Метод минимального элемента.
Метод

Фогеля.

Методы построения первоначального опорного плана Т-задачиМетод северо-западного угла.Метод минимального элемента.Метод Фогеля.

Слайд 48Метод северо-западного угла
аi
bj

Метод северо-западного углааibj

Слайд 49Метод минимального элемента
аi
bj

Метод минимального элементааibj

Слайд 50Метод минимального элемента
min (aij) = a13 = 2 =>

min(15;20) = x13 = 15
min (aij) = a13 = 2

Метод минимального элементаmin (aij) = a13 = 2  => min(15;20) = x13 = 15min (aij) =

Слайд 51Цепочки и циклы
Если в позиции (ij) имеется перевозка хij >

0, то позиция называется отмеченной.
Последовательность отмеченных позиций, в которой из

каждой строки и каждого столбца последовательно включены две и только две отмеченные позиции называется цепочкой
Цепочка, в которой первая позиция совпадает с последней называется циклом
Цепочки и циклыЕсли в позиции (ij) имеется перевозка хij > 0, то позиция называется отмеченной.Последовательность отмеченных позиций,

Слайд 52Цепочки и циклы
аi
bj

Цепочки и циклыаibj

Слайд 53Теорема

Теорема

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика