- •1.Постановка задач математ.Програмування:
- •4.Постановка злп
- •5.Зведення злп до канонічної форми:
- •6. Властивості злп.
- •7. Графічне розв`язання злп.
- •8. Симплекс-таблиці.
- •9. Перетворення симплекс-таблиць
- •10. Критерій оптимальності,розв’язності.
- •14. Постановка транспортної задачі, її мат. Модель та властивості.
- •15. Властивості т-задачі
- •20. Виродження у т-задачах
- •16. Побудова початкового опорного плану.
- •18. Перетворення планів т-задачі. Цикли т-задачі.
- •19. Знаходження потенціалів, критерій оптимальності.
- •22, 23. Метод гілок та границь.
- •24.Економічна постановка задач, що приводять до нелінійних оптимізаційних моделей.
- •25. Графічний метод рішення длп
- •26. Властивості нп
- •27.Основні труднощі розв’язування задач нелінійного програмування
- •29. Метод множників Лагранжа
- •30. Економічна інтерпретація множників Лагранжа
- •31.Задачі дробово-лінійного програмування, методи їх розв’язування
1.Постановка задач математ.Програмування:
Схематично ек.систему можна подати у вигляді прямокутника:
y1 y2 … ym
x
Ck
1x 2 F
. .....
x n
Параметр Ck , k= є кількісними характеристиками системи;
, j= (керовані змінні, тобто можна змінювати в деякому інтервалі).
Уі , (некеровані змінні).
F – це обрана мета.
F= f(x1,…,xn; y1,…,ym; c1,…,ce) (1)
Задача мат.програмування формулюється так:
Знайти такі значення керованих змінних xj, j= , щоб цільова функція набувала свого екстремал.значення.
F*=minxj(max) f( x1,…,xn; y1,…,ym; c1,…,ce) (2)
Можливості вибору xj обмежені зовнішніми,щодо системи, умовами, параметрами виробничо-ек.системи. Ці процеси можна описати системою мат.рівностей та нерівностей виду:
qr(x1,…,xn; y1,…,ym; c1,…,ce) 0 (3)
Для ек.системи параметри xj мають бути невід’ємними:
xj≥0, j= (4)
(2-4) – є ек.-мат.моделлю ек.системи
Розробляючи модель слід керуватися правилами:
Модель має адекватно описувати реальні технолог.та ек.процеси
В моделі слід враховувати все істотне в досліджув.явищі
Модель має бути зрозумілою для користувача
Потрібно забезпечити, щоб множинна змінних чи наборів була не порожньою
Будь-який набір змінних x1,…,xn , що задовольняє умови 3-4 назив.допустимим планом або план. Сукупність усіх розв’язків систем обмежень 3-4,тобто множина всіх допустимих планів становить обл.існування довільних планів. План, за якого цільова функція набуває екстрем.значення, наз.оптимальним. Оптим.план є розв’язком задачі (2-4).
4.Постановка злп
ЗЛП – означає знайти мін,мах функції при обмеженнях:
Z= c1x1+…+cnxn max (min) (1)
a11x1+a12x2+…+a1nxn b1
……… (2)
am1x1+am2x2+…+amnxn bm
x1 0, xn 0 (3)
Отже, треба знайти значення змінних x1 і xn, які задовольнять умови (2-3), тоді як цільова функція набуває екстремального значення.
5.Зведення злп до канонічної форми:
Z= c1x1+…+cnxn max (min) (1)
a11x1+a12x2+…+a1nxn b1
……… (2)
am1x1+am2x2+…+amnxn bm
x1 0, xn 0 (3)
Задачу 1-3 можна звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (2) всі bі , (і=1, m) невід’ємні, а всі обмеження є рівностями. Якщо якесь bі від’ємне, то помноживши і-те обмеження на «-1» дістанемо у правій частині відповідної рівності додатне значення. Коли і-те обмеження має вигляд нерівності:
аі1x1+aі2x2+…+aіnxn bі ,
то останню можна звести , до рівності додати допоміжну змінну хn+1
Аналогічно:
аk1x1+ak2x2+…+aknxn bk ,
зводимо до рівності віднімаючи від лівої частини допом.змінну хn+2
6. Властивості злп.
Властивості розв’язків задачі лінійного програмування формулюються у вигляді чотирьох теорем.
Теорема 1.
Множина всіх планів задачі лінійного програмування опукла.
Теорема 2
Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин багатогранника розв’язків. Якщо цільова функція набуває екстремального значення більш як в одній вершині цього багатогранника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією таких вершин.
Теорема 3
Якщо відомо, що система векторів А1, А2….Аk (k≤n) у розкладі А1Х1+А2Х2…+.АnХn = A0 (X≥0) лінійно незалежна і така, що A1X1 + A2X2..+ AnXn =A0, де всі Xj≥0, то точка X = (x1,x2,...,xk,0,...,0) є кутовою точкою багатогранника розв’язків.
Теорема 4
Якщо X = (x1,x2,...,xk) - кутова точка багатогранника розв’язків, то вектори в розкладі А1Х1+А2Х2…+.АnХn = A0 (X≥0), що відповідають додатним Xj , є лінійно незалежними.