Архів якісних рефератів

Знайти реферат за назвою:         Розширений пошук

Меню сайту

Головна сторінка » Математика

Відповіді на питання з предмету "Математичне програмування" (МАТПРО) (шпора)

1.Історія розвитку МП та сфери його застосування. Предмет МП. Класифікація задач МП.

2.Постановка економіко-математичних моделей транспортної задачі, задачі планування виробництва, задачі складання раціону, задачі про розкрій матеріалів.

3.n-Вимірний векторний, n-вимірний евклідовий простір, лінійна залежність і незалежність системи векторів, базис простору, опуклі множини точок. Опуклі множини в n-вимірному просторі,Геометрична інтерпретація розв'язань нерівностей,рівнянь та їх систем

4. Системи m лінійних рівнянь з n невідомими. Теорема Кронекера-Капеллі. Метод послідовних виключень Жордана-Гаусса. Базисні та опорні розв'язки.

5.Різні форми задач ЛП та їх еквівалентність. Зведення задачі ЛП до канонічної форми. Поняття плану, опорного плану, невиродженого опорного плану, оптимального плану задачі ЛП.

6.Властивості розв'язків задач ЛП. Графічний метод розв'язування задач ЛП з двома, трьома та п змінними.

7. Геометрична інтерпретація симплексного методу. Опорний розв'язок задачі ЛП. Табличний симплекс-метод.

8.Метод штучного базису в задачах ЛП. Задачі ЛП з мішаними обмеженнями.

9.Види математичних моделей взаємно двоїстих задач ЛП та їх властивості. Теореми теорії двоїстості. Знаходження розв'язку двоїстої задачі за таблицею прямої.

10.Економічний зміст оцінок ресурсів. Економічна інтерпретація двоїстих задач. Дефіцитні та недефіцитні ресурси. Аналіз стійкості двоїстих оцінок. Двоїстий симплекс-метод.

11.Постановка транспортної задачі, її математична модель та властивості. Відкрита модель транспортної задачі та її зведення до закритої. Методи пошуку початкових опорних планів. 18

12.Розв'язання транспортної задачі методом потенціалів.

13.Транспортна задача за критерієм часу та її розв'язання.

14.Класифікація розподільних задач. Задача щодо призначення та її розв'язок угорським методом та методом потенціалів.

15.Постановка задачі ЛЦП. Приклади задач ЛЦП.

16. Геометричний метод, метод Гоморі, метод гілок і меж розв'язання задач лінійного цілочислового програмування.


1.Історія розвитку МП та сфери його застосування. Предмет МП. Класифікація задач МП.

Основні розділи МП, постановка задачі МП. Застосування ЕОМ для розв'язку задач МП. Дисципліна Матпро була створена в 1947. Після відкриття Данцигом симплекс методу. Назва склалася тому, що розглядалися в математичній постановці еокном.,задачі і знаходилася оптимальна ек.,програма.МП використовується в слідуючих сферах:- дослідження операцій(транспортні задачі);- в чисельному аналізі(розв'язання систем задач наближення);- автоматиці;- техніці при керуванні великими технічними транспортними,інформаційними та іншими системами;- в мат., економіці(розв'язання макроекономічних моделей).Предметом МП є розроблення методів розв'язування оптимізаційних задач та дослідження отриманого розв'язку. Класифікація задач МП:- по характеру зв'язку між змінними:а)лінійні б) нелінійні; - по характеру змінення змінних а) неперервні б)цілочислові в)дискретні г) буляві; - по врахуванню фактору часу: а)статистичні б)динамічні;- по іеформації відносно змінних: а) детерміновані б) статистичні;- по числу критеріїв якості а)однокретеріальні б) багатокретеріальні.Розділи:лінійні; нелінійні; дискретні;цілочислові; бульове;динамічне;параметричне; дробоволінійне.Постановказадач:z=f(x1….xn)- extr-цільова функція(1) D: (x1…xn) {=; }bi i=1.,m(2); x=(x1…xn) є Q (3); (2) та(3) обмеження; x є D план або допустимий розв'язок X*-оптимальний план extr f(x)=f(X*). Застосування ЕОМ для розв'язку задач МП.????

2.Постановка економіко-математичних моделей транспортної задачі, задачі планування виробництва, задачі складання раціону, задачі про розкрій матеріалів.

Транспортна задача: Припустимо, що існує m-постачальників з запасом вантажу відповідно та n-споживачів, з потребами b1…bn. Загальні запаси = загальним потребам (∑ai=∑bj) ;C=(Cij)mn де Сij- означає вартість перевезення одиниці вантажу від I постачальника до j споживачя, треба так організувати перевезення вантажу, щоб задовільнити усіх постачальників та споживачів. Для розв'язку такої задачі вводяться змінні X=(Xij)mn де Xij- кількість вантажу яка перевозиться від "i” постачальника до j споживачя

z= CijXij ; ∑xij=ai, i=1,m; ∑xij=bj j=1,n ; xij≥0; i=1,m;j=1,n.

Задача планування виробництва:Припустимо існує m:S1…Sm- ресурсів з яких треба виготовити n:P1…Pn продукції , відомі запаси ресурсів b1…bn і задана матриця С=(С1...Сn), Cj- прибуток від реалізації одиниці; A=(aij) де aij- кількість ресурсу і яке іде на виготовлення одиниці „і” продукції, треба так організувати виготовлення з наявних ресурсів, щоб максимізувати прибуток. Введемо змінні Xj ;j=1,n; де xj означає кількість випущеної продукції. z= ∑cjxj→max; ∑aij xj≤bi, i=1,m; xj≥0, j=1,n.

Задача складання раціону: Припустимо для відгодівлі худоби використовують n: P1…Pn різних кормів в цих кормах знаходжуються поживні речовини в кількості m:S1…Sm,необхідно мінімізувати кількість кожної з них b1…bn . Задана матриця C=(C1…Cn), j=1,n; де Сj-вартість одиниці корму. A=(aij)mn де aij – кількість споживних речовин і-типу,які знаходяться від одиниці j-корму. Треа так організувати відгодівлю худоби.щоб мінімізувати загальні витрати і забезпечити худобу необхідною кількістю споживних речовин.Для постановки задачі вводяться змінні xj j=1,n-кількість корму відповідного j- типу:

z=∑Cjxj→min

∑aijxj≥bi , i=1,m

Aj≥xj≥Aj0, j=1,n.

Задача про розкрой матеріалів: Припустимо існує теоритично небмежена кількість деякого мірного матеріалу, з якого треба виготовити m типів заготовок, припустимо існує nспособів розкрою даного матеріалу. Задана матриця Сi=(C1…Cn) де Сi означає відходи з одиниці мірного матеріалу при використанні j способу розкрою.Задана матриця B=(b1…bm) bi,i=1,m- min необхідної кількості заготовок „і”типу,задана матриця А=(aij)mn aij-кількість заготовок „і”типу які отримуються з одиніці мірного матеріалу за j способом розкрою,треба так оргонізувати розкрой щоб, min загальні відходи,введемо змінні xj-кількість мірного матеріалу який розкроюється за j способом. Z=∑cjxj→min ; ∑xj≥0 j=1,m; ∑aijxj≥bi i=1,m.

3.n-Вимірний векторний, n-вимірний евклідовий простір, лінійна залежність і незалежність системи векторів, базис простору, опуклі множини точок. Опуклі множини в n-вимірному просторі,Геометрична інтерпретація розв'язань нерівностей,рівнянь та їх систем.

Розглядаємо n-вимірний векторний простір в якому розглядається n-вимірні вектори в якому виконуються тіж самі властивості з векторами як у двох,трьохвимірному просторі.N-вимірний векторний простір в якому вводиться операція скалярного добутку векторів наз.,n- вимітним евклідовим простором (Еn). x*y=∑xiyi ; /x-y/=корень(∑(xi-yi)2); /x/=корень(∑(xi)2). X1…Xn-наз лінійно залежними вектрами, якщо викон рівність α1x1+..+αnxn=0 при умові, що не всі αі≠0(1).Якщо рівність (1) виконується тільки тоді всі αі=0 ,і=1,n ;∑αі2=0 , то вектори лінійно залежні. Якщо деяка підсистема X1…Xk системи X1…Xn (k<n) залежна то і вся система векторів лінійно залежна. Якщо система векторів X1…Xn лінійно незалежна і будь-яка підсистема цих векторів теж лінійно незалежна. Довільна система лінійних векторів створює базис у відповідному просторі.Максимальна кількість лінійно залежних векторів n-вимірногопростору =n. Оскільки система n-лігійних незалжних векторів створюють базис в n-вимірноиу просторі то за цими векторами можна розкласти довільний інший вектор цього простору.Якщо визначник який складається з координат відповідних векторів≠0,то вектори створюючи базис.Якщо =0,то вони лінійно залежні і нестворюють базис.В опуклих множинах інують внутрішні,кутові, граничні точки. Геометричний зміст розв'язання нерівностей рівнянь та систем рівнянь: aixi+ai2x2≤bi x1=x; x2=y; ax+by+c=0.Для того щоб вирішити, яка частина півплощини від даної прямої відповідає нерівності треба підставити координати довільної точки замість X таY. Якщо координати точки задовільняють нерівності, то півплощина включає дану точку.Система це є перетин півплощин. (х;у)=α(х11)+β(х22) α+β=1.Якщо в нерівності маємо 3 змінні то ми будемо мати частини 3-вимірного простору aixi+ai2x2+ai3x3≤bi.

4. Системи m лінійних рівнянь з n невідомими. Теорема Кронекера-Капеллі. Метод послідовних виключень Жордана-Гаусса. Базисні та опорні розв'язки.

(писать без знака деления)

rA=rD – то система має розв'язок.; rA=rD=n - система має єдиний розв.,

rA≠rD – то система намає розв.,; rA=rD<n – безліч розв.,

Після отримання стрічкової матриці ми отримаємо, що система несумісна або має безліч роз.,.Будь-які R змінних для яких відповідний визначник який складається з елементів відповідних стопчиків являється базисними змінними,тоді коли цей визначник ≠0, всі інші змінні вільні, в базисному розв.,вільні зимінні =0.Кількість базисних розв., Сn2=

Допустимий базисисний розв., такий в якому всі компоненти невід'ємні.
5.Різні форми задач ЛП та їх еквівалентність. Зведення задачі ЛП до канонічної форми. Поняття плану, опорного плану, невиродженого опорного плану, оптимального плану задачі ЛП.

Різні форми задач ЛП та їх еквівалентність. Загальий вигляд задачі ЛП

Якщо m1=m, то задача ЛП має симетричну форму „<=”,m1=m. Якщо m2=0, то задача ЛП має канонічний вигляд, всі знаки обмежень „=”.

1)Стандартною є зад.на max,задачу на min можна звести до зад на max.

-z=-f(x), Max(-z). Min z = - max(-z), max z = -min(-z)

2)Якщо Якщо частина нерівностей мають вигляд >=;<= , то таку задачу ..лп можна звести до канонічної форми

Зводимо до стандартного вигляду :

a11x1+…a1nxn+xn+1

an11x1+…am,nxn; xn+i>=0, i=(1,m)

3) Якщо серед змінних хj. Пикпускається, що е обов”язково вся змінні невід”ємні, то то відповідні змінні розглядаються у вигляді Xi =Xi'-Xj” Xi>=0, Xj>=0

Кожне обмеження зі знаком відношення = можна представити у виді 2-х неівностей:

ai1X1+....+ainXn=bi

Від канонічної до симетричної:

З ціїєї сис-ми Жордановими перетвореннями отримуємо сис-му з одиночними векторами:

rA= m (r<=m<=n), xj + ai m+j Xm+j=bi, I=(1,2..m)

aim+j Xm+j<=bi. Xj>=0, j= (1,n+1,n) – для зменшення кількості невідомих.

Опорним планом задачі ЛП наз-ся план, утворений координатами вершин многогранника планів задачі. Тобто,це план, який задовольняє не менш ніж n лінійно незалежних обмежень у вигляді строгих рівностей разом з обмеженням щодо знака. Опорний план наз-ся невиродженим, якщо він є вершиною многогранника планів задачі, утвореного перетином точно n гіперплощин, тобто задовольняє n лінійно незалежн.обмежень-строгих рівностей.У противному випадку опорний план вроджений. Оптимальний план шукається серед опорних планів. X*.f (x*)- найкращій план. Оптимальний план шукається серед вершин многогранника.


6.Властивості розв'язків задач ЛП. Графічний метод розв'язування задач ЛП з двома, трьома та п
змінними.

Властивості розв”язків задач ЛП. Сукупність усіх розв”язків задачі ЛП є многогранною опуклою множиною, яку називають многогранником розв”язків. Якщо задача ЛП має оптимальний план, то екстремального значення цільова фун-ція набуває в одній із вершин многогранника розв”язків. Якщо цільова фун-ціія набуває екстрем.значення більш як в одній вершині цього многогранника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією таких вершин. Множина усіх планів задачі ЛП опукла. Лінійна фун-ція задачі ЛП досягає мінімума в кутовій точці многогранника розв”язків. Якщо лінійна фун-ція приймає миним. Значення більш ніж в 1 кутовій точці, то вона досягає того ж значення в будь-якій точці, яка є опуклою лінійною комбінацією цих точок.

Графічний метод розв”язування задач ЛП з двома, 3 та nзмінними. Вінгрунтується на геометричній інтерпретації та аналіт.власт-тях задач ЛП. Припустимо задача ЛП задана:

Z = c1x1+c2x2 -> max

U=2

Кожне граничне обмеження відповідає прямій лінії a11x1+a12x2=b1 ax+by+c=0

1)Будується кожна з цих прямих на площині.Але ж нерівностям відповідають півплощини від прямої, для встановлення яка є півплощина підставляють координати довільної точки, напр. О(0,0). 2)Якщо ці координати відповідають нерівності, то півплощина направлена на дану точку, якщо не відповідають-направлена від неї. 3)Знаходимо многокутник розв”язків -Область Д-многокутник допустимих розв”язків.

4)Будуємо вектор, градієнт, що задає напрям зростаняя значеньо цільової фун-ції.

5)Будуємо пряму c1x1+c2x2=cоnst , перпендикулярну до вектора.

6)Переміщуємо пряму c1x1+c2x2=cоnst в напрямі вектора (на макс), або в протилежному (мін), знаходимо вершину, де цільова фун-ція досягає екстремуму.

7)Визначаємо координати знайденої точки, и обчислюємо значення цільової ф.в ній.

Якщо n =3 задачу ЛП теж можна розв”язувати графічно. Але це буде не пряма, а площина.

Z=c1x1+c2x2+c3x3. Якщо n-m=2 v 3 задача ЛП задана в канонічній формі, то за допомогою Жарданових претв. Вирішуємо


7. Геометрична інтерпретація симплексного методу. Опорний розв'язок задачі ЛП. Табличний симплекс-метод.

Геометрична інтерпретація симплекс методу. Опорний розв”язок задачі ЛП. Табличний симплекс-метод. За допомогою алгоритма симплекс-методу ми рухаємося в пошуку оптимального плану цілоспрямовано, на кожному кроці покращуючи значення цільової фун-ції. f(A)<f(B)<f(C) знаходимо макс.

В

А / \ С Опорний розв”язок x0 ={b1'; bn';0...0} bj>=0; i=1..m

| | Базисні вектори А1= 1,0,0...0 (записать вертикально), Аm 0..0,1(записать вертикально)-базисні зм

___

Послідовність симплекс-методу:

1)Знаходиться 1-й опорний план в конан.формі.

2)За допомогою Жорданових перетворень отримується симплекс-таблиця.

3)Перевіряється умова закінчення.

i

базис

C базис

A0(с чертой

C1

С2

.

Cl

.

Cm

Cm+1

.

Cj

.

Ck

.

Cn

A1

А2

.

Al

.

Am

Am+1

.

Aj

.

Ak

.

An

1

A1

C1

X1

1

0

.

0

.

0

X1,m+1

.

X1j

.

X1k

.

X1n

2

A2

C2

X2

0

1

.

0

.

0

X2,m+1

.

X2j

.

X2k

.

X2n

.

.

.

.

.

.

.

.

 

.

.

.

.

.

.

.

.

l

Al

cl

xl

0

0

.

1

.

0

Xl,m+1

.

xij

.

xik

.

Xln

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

m

Am

Cm

xm

0

0

.

0

.

1

Xm,m+1

.

xmj

.

xmk

.

Xmn

M+1

Zj-Cj

 

z0

0

0

.

0

.

0

Zm+1-cm+1

.

Zj-cj

.

Zh-ch

.

Zn-Cn

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Симплекс-метод може бути реалізований також за допомогою ітераційних ф-й, або як аналітичний симплекс-метод. Існують також і інші форми запису симплекс-таблиць.

8.Метод штучного базису в задачах ЛП. Задачі ЛП з мішаними обмеженнями.

Метод штучного базису в задачах ЛП,Задачі ЛП з мішаними обмеженнями.

Якщо маємо мішані обмеження, або перший опорний план знаходиться достатьон складно для задачі ЛП, то використовують метод штучного базису. М-метод. Напр.задача ЛП має відразу канонічний вигляд, у нас нема одиничних векторів.Тоді, додаємо кожне в обмеження штучну змінну, обмеження приймають вигляд.

f=

Якщо задача має розв”язок,то штучні змінні в оптим.плані повинні прийняти зн-ння 0.

У симплекс-таблиці для М-задачі використ-ся 2 рядки. В першому пишуться вільні члени,у 2-коефіцієнти при М. Після виведення вектора, який відповідає штучній змінній з базиса обчислення відповідного стовбчику можна не виконувати Жорданові перетворення робляться аналогічно як для симплекс-методу.

Ще один частний випадок:

Віднімамо додаткові змінні в перших k нерівностях, у відношеннях всі „=”.Припускається, що всі bi=0. Кільк-ть штучних змінних можна зменшити до кількості n-k, якщо відняти від рівнянно, яке має найбільше Ві перші k-рівнянь. Якщо всі обмеження мають від-ня >=0, то можна зробити перетворення, які зменшать кіл-ть штучних змінних до 1.

Задача з мішаними обмеженнями - сис-ма обмежень складається з к нерівностей(1<=k<m) і m –k рівнянь і не має одиничної матриці. Базис її складається з додаткових і штучних базисів. Мішана сис-ма обмежень має d рівнянь. Повинно бути не > d штучних змінних..

Якщо сис-ма має k нерівностей виду AX<=A0, A0>=0. Маємо рівність AX-X'=A0, де

X'=(Xn+1,Xn+2,..Xn+k)сис-ма обмежень має К від”ємних векторіів. Потім зробимо додатні вектори.


9.Види математичних моделей взаємно двоїстих задач ЛП та їх властивості. Теореми теорії двоїстості. Знаходження розв'язку двоїстої задачі за таблицею прямої.

1 ТЕОРЕМА Двоїстості : Якщо перша з пари двоїстих задач має розв”язок, то маає розв”язок і друга. Причому fmax=Zmin, якщо перша розв”язку не має(z необмежена), то друга теж не має,обмеження суперечливі.За симплекс-таблицею для 1 задачі отримується розв”язок 2 У* - Сбаз * Д- х Д- 1 -обернена матриця, будується з останньої симплекс-таблиці, ті стовбчики, які відповідають першому базису.

2 ТЕОРЕМА двоїстості : Для того,щоб плани х* і у* були оптимальними планами двоїстих задач,необхідні і достатні умови:

Якщо маємо пару двоїс.задач,то ця теорема записується:

3 ТЕОРЕМА двоїстості: Якщо ми маємо пару несеметричних здач, задач то уі*

yi*=dfmax/dbi, i=(1..m) Економічний зміст:

Двоїста задача отримуєтьс з прямої таким чином: кількість змінних відовідає кількості обмежень для 2 задачі-кількость обмежень-кількості обмежень.

Пара несеметр.двоїстих задач

 

z=

Пара симетр двоїстих задач

z=

Види мат.моделей двоїстих задач.

Несеметричні задачі: (1) Початкова задача Zmin=CX; AX=A0; X>0.

Двоїста задача t max=YA0; YA<C

(2) Початкова задача Zmax=CX; AX=A0; X>=0

Двоїста задача: t min=YA0; YA>=C

Симетричні задачі(3) Початкова задача Zmin=CX; AX>=A0; X>=0

Двоїста задача: tmax=YA0; YA<=C; Y>=0

(4) Початкова задача: Zmax=CX; AX<=A0; X>=0

Двоїста задача; tmin=YA0; YA>=C; Y>=0  


10.Економічний зміст оцінок ресурсів. Економічна інтерпретація двоїстих задач. Дефіцитні та недефіцитні ресурси. Аналіз стійкості двоїстих оцінок.??? Двоїстий симплекс-метод.

Економічний зміст оцінок ресурсів

; уі* > 0, ресурс дефіцитний,;уі*=0, ресурс недефіцитний.

Уі*-цінність одиниці і-го ресурсу, показує наскільки змінюється прибуток, якщо j-й ресурс змінюється на 1.

Економічна інтерперетація двоїстих задач. Нехай задана задача планування вир-ва(використання ресурсів). Модель№1.

 

Такій задачі відповідає двоїста задача:

 

Економічний зміст (3),(4). Уі-оцінка і-го ресурсу, при закупівлі усих ресурсів покупець намагається мінімізувати загальну ціну всих ресурсів. Обмеж.(4) означає, що ціна усих ресурсів, які ідуть на виготовлення одиниці продукції не менше ціни одиниці продукції. (1,2,3,4)-пара симетричних двоїстих задач.

Двоїстий симплекс-метод. Припустимо задача ЛП задана у каноничному вигляді і перші М векторів одиничні.

f = cjxj -> max

A1X1+...+AmXm+Am+1+Xm+1+..+AnXk

Не всі елементи матриці В невід”ємні. Псевдоплан-це планб для якого усі оцінки j>=0

Для псевдоплана елементи можуть бути і від”ємні. Симплекс таблиця будується аналогічно, але спочатку знаходиться номер напрямного рядка, який відповідає найменшому з від”ємних ві

А потім, напрямного стовбчика, який відповідає

min

Перетворення робиться до тих пір, поки всі елементи стовбчика будуть невід”ємними.


11.Постановка транспортної задачі, її математична модель та властивості. Відкрита модель транспортної задачі та її зведення до закритої. Методи пошуку початкових опорних планів.

Постановка транспортної задачі, її мат. модель та властивості.

Припустимо,існує m:A1...Am постачальників з запасом вантажу відповідно a1...am та n споживачів B1...Bn з потребами в1...вn .Загальні запаси=занальним потребам.

Задана матриця Сі, з елементами ij, С=(С ij), де С ij-вартості перевезень 1 вантважу від і-го постачальника j-му споживачеві. Для розв”язку вводиться Xij, X=(Xij)min, де xij-кіл-сть вантажу, яка перевозиться від i пост-ка j
споживачеві.

Мат модель ТЗ:

Z=

Відкрита модель ТЗ та її зведення до закритої..Сумарні запаси=Сумарним потребам.

Така ТЗ зводиться до відкритого типу введенням фіктивного споживача з потребами (вn+1).

Мат.модель такої задачі має вигляд:

 

В моделі замість n буде n+1,замість „<=”у, пишеться”=”.Збільшилася матриця С.

Х*=

Після знаходження оптим.розв”язку викреслюються ост.стовбець.

2)Сумарні запаси <сумарн.потребам.

Вводимо фікт.постачальника з запасами

; ; ;

Сm+11=Cm+1n=0

X*=

Методи пошуку початкових опорних планів. Півн-західного кута Заповнюється таблиця з лівого верхнього в напр. Правого нижнього.В ліву верхню записується менше з чисел. Заповнюється таблиця,треба щоб збігалася сума перевезень по рядку і стовбцю з запасами та потребами.

Метод мін.елемента. Знаходимо клітинку з найменшим тарифом і внеї записуємо менше з чисел Аі і вj на перетині. Потім знову знаходимо найменший тариф.

Метод подвійної переваги. Знаходяться найменші тарифи в кожному рядку і в кожному стовбці і відповідні клітинки позначаються голочкою(найбільші 2,наймен-0).Таблиця починається заповнюватися з 2-ч галочок,потім 1,а потім ті, в яких найменші тарифи.

12.Розв'язання транспортної задачі методом потенціалів.

Розв”язаня ТЗ методом потенцілів. (*)-відповідає зайнятим клітинкам і потенціали знаходяться для заповнених клітинок m+n невідомих, рангматриці (m+n+1). Ця сис-ма має безліч розв”язків. 1-й частинний розв”язок знаходиться, якщо якийсь потенціал взяти довільним числом. ui=0 ,

З таблиці, або сис-ми * знаходимо потенціал (для незаповнених).Розглядаються такі оцінки Sij=cj-(ui+Vj),якщо Sij>=0,-задача розв”язана. (поожит).

Якщо хоча б 1 від”ємна оцінка, то слідуюча таблиця. Треба знайти чарунку, в якій най1менше значення Sij з усіх від”ємних значень.Ця клітинка перспективна, в ній ставимо”+”.Кіл-ть заповнених клітинок=m+n-1(ранг матр). Якщо вона менша,то недостаюча кіл-ть заповнюється 0-ми.Після заповнення перспективної клітинки знаком”+” будуємо цикл,який є ломаною замкненою лінією, іде через зай няті клітинки,в яких робимо поворот на 90”.Цикл 1,знаки чередуємо.Знаходимо найменше перевезення в клітинах зі знаком „ - ”,Xij(для зайнятих) min(Xij) і це значення віднімаємо від перевезень в клітинах зі знаком „-” і додаємо до перевезень в клітинах зі знаком „+”.На кожному кроців кількість зайнятих m+n-1 в кожній клітині.Після цього знаходимо потенціали з (*) і перевіримо умову закінчення(**)  


13.Транспортна задача за критерієм часу та її розв'язання.

Транспортні задачі за критерієм часу використовуються тоді коли вартість перевезення не враховується, а має значення час.Такі задачі виникають при перевезенні швидкопсуючого вантажу або людей з зон лиха. Розглянемо математичну постановку такої задачі. Вважаємо, що ТЗ відкритого типу, тобто виконується умова ∑ai=∑bj

T(x)- max(tij)→min Таку ТЗ будемо розв., методом розвантажувальних

∑xij=ai i=1,m; циклів. Перший опорний план знаходиться як і для

∑xij=bi j=1,n; всіх ТЗ. Серед заповнених клітин знаходимо

xij≥0 , i=1,m; j=1,n. клітину в якій найбільший час перевезення, в цю клітину ставимо знак ”-”, а в всі клітинки вільні в яких час перевезення не менше знаденого викреслються і будуємо розвантажувальний цикл. Цикл починається зі знаком „-”, знаки ставляться через раз у містах повороту на 900 всі клітини зі знаком „-” повинні ьути зайняті, а з „+” зайняті, або ні. Найкращій цикл такий, коли відразу вдається розвантажити клітину. Як і раніше занходиться найм., перевезення в клітинах зі знаком „-„це перевезення віднімається від клітин з „-” і додається доклітин з „+”. Задача розв., до тих пір поки існує розв., цикли.


14.Класифікація розподільних задач. Задача щодо призначення та її розв'язок угорським методом та методом потенціалів.

Роподільчи задачі – це такі задачі в яких мається обмежена кількість ресурсу які треба н6айкращим чином розподілити між споживачами. Класифікація розподільчих задач: 1) по вигляду цільової функції: а)лінійні; б) не лінійні; 2) по наявним потребам ресурсами:а) збалансовані

б) не збалансовані; 3) по характеру змінення змінних:неперервні, цілочислові, дискретні, бульові; 4) за кількостю екстремумів: одно- та багатоекстремальні; 5)за характером розподілу ресурсів у часі: статичні та динамічні. Задачі, щодо призначення: існує n-різних робіт, та m- робітників(автоматів), які будуть виконувати ці роботи, треба найкращим чином розподілити робітників на роботи, щоб отримати найбільшу загальну ефективність, якщо відома C=(Cij)mn матриця ефективності, де ij- це ефективність відвиконання i-працівником, j- роботи.

Постановка задачі: Припустимо,що кожний робітник виконує тільки одну роботу і кожна робота може зайнятий тільки один робітник:

f=∑∑СijXij→min(max) Задача на min якщо під Cij розуміти час або

Xij=1 i=1,n витрати при виконанні i-робітником, j- роботи,

Xij=1 j=1,n і на max –якщо Cij розуміти продуктивність,

Xij={0;1}, i=1,n; j=1,n прибуток.Така задача може бути розв., методом потенціалів, як ТЗ. ai={1,…,1}; bj={1,…,1}. Але більш ефективний є Угорський метод: 1) отримання нулів:а) Якщо задачі на min то в кожному рядку матриці C знаходиться найменше значення, яке віднімається від усіх інших елементів даного рядка, а потім в кожному стопчику знаходять найменше значення, які віднімаються від усіх інших елементів відповідного стовпця.C=(Cij)mn→C1=(Cij)mn=(Cij-minCij)→D=(dij)mn=(Cij-minCij);

б) якщо задача на max від найбільшого значення кожного стопчика віднімаються всі елементи відповідного стовпця, а потім для отриманої матриці віднімається найменше значення від усіх елементів відповідного рядка C=(Cij)mn→C1(Cij)mn=(maxCij-Cij)→D=(dij)mn=(Cij-minCij);

2)Пошук оптимального розв.,: знаходимо в якому найменше всього нулів і один з нулів даного рядка помічається і викреслюється усі інші нулі відповідного рядка і стопчика де знаходиться помічений нулі не торкаються, оптім в іешому рядку та стопчику знаходиться найменша кількість нулів і один помічаємо. Так робиться до тих пір поки. Якщо кількість помічених нулів = m то задача розв'язана. Якщо менше то переходимо до пункту 3).

3)Пошук мінімальної кількості рядків: а) Помічаються рядки в яких немає ніодного поміченогонуля;б) Для помічених рядків через викреслення нулів помічаються стопчики; в) Для помічених стопчиків через нулі помічпаються рядки. Пункти б) і в) можуть повторюватися циклічно.Потім викреслюємо усі не помічені рядки та всі помічені стопчики. Логічна перевірка – всі нулі потряпляють під викреслення.

4) Перестановка нулів. Знаходимо найменше значення серед не викреслених елементів і це значення віднімаємо від усіх елементів не викреслених стопчиків і додаємо до усіх елементів викреслених рядків, після цього переходимо до пункту 2).


15.Постановка задачі ЛЦП. Приклади задач ЛЦП.

Мат. модель : Приклади задач ЛЦП:задача щодо призначення,

f=∑CjXj→max; задача розкрою матеріалу, задачи про ранець.

∑aijxj{≥;≤;=}bi i=1,m; Припустимо треба перевести n предметів різних

x≥0, j=1,m; n-назв., кількість предметів одніє назви може

xj-цілі j=1,n; повторюватись.Відомі обмеження по кожній

n1≤n; характеристиці предметів відповідної назви задається мтарицею B=(bi) i=1,m і елементи A=(aij)mn aij- означає і-характеристику предмета j- назви. Задається матриця C=(Cj) j=1,n; j – корисність від перевезення предмета j- назви; xj-кількість предметів j –назви.

z=∑CjXj→max Перевезення неподільного вантажу в

∑aijXj≤bi i=1,m; j=1; транспортному засобі мається m-відсіків,

xj≥0,цілі, j=1,n в якому перевозиться n-видів вантажу. bi – вмістимість і-відсіку Cj- корисність при перевезенні j-типу вантажу і матриця aij- занятість і-відсіка одним предметом j-назви.

Задача комівояжера:Існує n-різних міст. Комівояжер виїзджає з одного міста і повинен об'їхати всі міста і повернутися назад найкращим шляхом. Задані ел.матриця C=(Cij) відстані від і-міста до j- міста, вводяться змінні xij. Математична модель така сама,як в задачі щодо призначення.


16. Геометричний метод, метод Гоморі, метод гілок і меж розв'язання задач лінійного цілочислового програмування.

Метод Гоморі:Спочатку розв'язуємо ослаблена задача ЛП(не враховується цілочисловість) симплекс методом, якщо в оптимальному плані всі цілочислові значення, то розв'язана задача ЛЦП,Якщо ні, то до симплекс таблиці додається додаткове обмеження, яке робиться для тієї змінної яка має найбільшу дробову частину.

∑f(aij)xj≥f(bi); f – оператор знаходження дробової частини.

{a}= a-[a]. І розв'язуємо задачу ЛП двоїстим симплекс методом. Продовжуючи розв'язок останньої симплекс таблиці так робиться до знаходження цілочислового плану.

Гілок та меж: Спочатку задачя ЛЦП розв'язується, як ослаблена, якщо не отримаємо цілочислового плану, то використовуємо метод гілок та меж. Xk*- не цілочислове значення- задачі розгалужуються на дві підзадачі з додатковим обмеженням Xk ≤[Xk*];Xk [Xk*]+1; Vk≤Xk≤Wk;

Vk≤Xk≤[Xk*]; [Xk*]+1≤Xk≤Wk.Якщо ці дві підзадачі немають цілочислового значення то вони далі розгалужуються.Якщо ослаблена задача гірший ніж цілочисловий розв'язок вона далі не проробляється.





Реферат на тему: Відповіді на питання з предмету "Математичне програмування" (МАТПРО) (шпора)


Схожі реферати



5ka.at.ua © 2010 - 2016. Всі права застережені. При використанні матеріалів активне посилання на сайт обов'язкове.    
.