Розв'язання задач математичного програмування
Математична постановка задачі математичного програмування. Зародження математичного програмування в працях Л. Канторовича. Класифікація задач математичного програмування. Постановка та розробка моделі для задачі визначення оптимального плану виробництва.
| Рубрика | Экономико-математическое моделирование |
| Вид | курсовая работа |
| Язык | украинский |
| Дата добавления | 08.02.2015 |
| Размер файла | 1,1 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
,
(2.19.1)
Узявши величину х3 рівною нулю, отримаємо рівняння:
.
Для такої прямої ,
Відмітимо ту півплощину , де . Аналогічно ; ;...;. Спільна частина площини в - багатокутник допустимих розв'язків.
Необхідно знайти максимальне значення функціонала:
.
Підставивши , , ,...; з (2.19.1) у функціонал, отримаємо F через дві вільні змінні та :
,
де -- вільний член. Далі відшукання оптимального плану здійснюється за алгоритмом для випадку двох змінних.
Розв'язати графічним методом задачу лінійного програмування
.
Розв'язання.
n = 7 -- кількість змінних, m = 5 -- кількість обмежень.
вільні змінні х1 та х2 і виразимо через них всі базисні змінні.
(2.19.2)
, (2.19.3)
. (2.19.4)
;
.
Далі за алгоритмом беремо х1 = 0 та х2 = 0 -- координатні осі; інші обмежуючі прямі знаходимо, узявши х3 = 0, х4 = 0, х5 = 0, х6 = 0, х7 = 0. Багатокутник допустимих розв'язків зображено на рис. 2.12.
Рис. 2.12
Знайдемо вигляд функціонала, вираженого через х1 та х2.
.
Відкидаючи вільний член, маємо: .
Будуємо вектор (-5, -2), а перпендикулярно пряму F.
Рухаючи пряму F в напрямку, протилежному (необхідно знайти мінімальне значення функції F), отримаємо точку мінімуму -- А (рис. 2.13).
Рис. 2.13
У точці А перетинаються дві обмежуючі прямі: х6 = 0 та х7 = 0.
= 8,5; = 5.
Звідки
= 0,5; = 16,5; = 17,5; = 0; = 0.
Підстановкою значень та в лінійну функцію F отримуємо значення цільової функції:
.
Симплексний метод розв'язування задач лінійного програмування
З властивостей розв'язків задачі лінійного програмування відомо: оптимальний розв'язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв'язків. Загальна кількість опорних планів визначається кількістю комбінацій .
1949 року американським вченим Дж. Данцігом запропоновано симплекс-метод.
13. Початковий опорний план
Розглянемо задачу лінійного програмування, записану в канонічній формі:
.
Не порушуючи загальності, допустимо, що система рівнянь містить перші m одиничних векторів. Отримаємо:
(2.36)
(2.37)
(2.38)
Система обмежень (2.37) у векторній формі матиме вигляд:
, (2.39)
де
, ,..., ,
, …, , ,
-- лінійно незалежні одиничні вектори m-вимірного простору, що утворюють одиничну матрицю і становлять базис цього простору.
Тому в розкладі (2.39) базисними змінними будуть , а інші змінні -- вільні.
Прирівняємо всі вільні змінні до нуля,
.
Оскільки , а вектори -- одиничні, то отримаємо один із розв'язків системи обмежень (2.37):
(2.40)
тобто допустимий план.
Такому плану відповідає розклад
(2.41)
де -- лінійно незалежні вектори і за властивістю 3 розв'язків задачі лінійного програмування план є кутовою точкою багатогранника розв'язків, а отже, може бути початковим опорним планом.
14. Перехід від одного опорного плану до іншого
Оскільки є базисом m-вимірного простору, то кожен з векторів співвідношення (2.39) може бути розкладений за цими векторами базису, причому у єдиний спосіб:
Розглянемо такий розклад для довільного небазисного вектора, наприклад, для :
(2.42)
Припустимо, що у виразі (2.42) існує хоча б один додатний коефіцієнт .
Нехай , помножимо на неї (2.42) і віднімемо (2.41):
(2.43)
Вектор
буде планом задачі у тому разі, якщо його компоненти невід'ємні. За допущенням , отже, ті компоненти вектора , в які входять , будуть невід'ємними, тому необхідно розглядати лише ті компоненти, які містять додатні .
Необхідно знайти таке значення , за якого для всіх буде виконуватися умова невід'ємності плану задачі:
(2.44)
З (2.44) отримуємо, що для шуканого має виконуватися умова . Отже, вектор буде планом задачі для будь-якого , що задовольняє умову:
,
де мінімум знаходимо для тих i, для яких .
Опорний план не може містити більше ніж m додатних компонент, тому в плані необхідно перетворити в нуль хоча б одну з компонент. Допустимо, що для деякого значення і, тоді відповідна компонента плану перетвориться в нуль. Нехай це буде перша компонента плану, тобто:
.
Підставимо значення у вираз (2.43):
,
якщо позначити , , то рівняння можна подати у вигляді:
,
якому відповідає такий опорний план:
.
Для визначення наступного опорного плану необхідно аналогічно продовжити процес: будь-який вектор, що не входить у базис, розкласти за базисними векторами, а потім визначити таке , для якого один з векторів виключається з базису.
Отже, узагальнюючи розглянутий процес, можемо висновувати: визначення нових опорних планів полягає у виборі вектора, який слід ввести в базис, і вектора, який необхідно вивести з базису. Така процедура відповідає переходу від одного базису до іншого за допомогою методу Жордана--Гаусса.
Зауваження: Для випадку, коли вектор підлягає включенню в базис, а в його розкладі (2.42) всі , то, очевидно, не існує такого значення , яке виключало б один з векторів. У такому разі план містить m+1 додатних компонент, отже, система векторів буде лінійно залежною і визначає не кутову точку багатогранника розв'язків. Функціонал не може в ній набирати максимального значення. Це означає, що функціонал є необмеженим на багатограннику розв'язків.
15. Оптимальний розв'язок. Критерій оптимальності плану
Розглянемо задачу лінійного програмування (2.36)--(2.38).
Допустимо, що вона має опорні плани і вони є невиродженими. Розглянемо початковий опорний план виду (2.40):
Такому плану відповідає розклад за базисними векторами
(2.45)
та значення функціонала:
(2.46)
Кожен з векторів можна розкласти за векторами базису, причому у єдиний спосіб:
, (2.47)
тому такому розкладу відповідатиме і єдине значення функціонала:
. (2.48)
Позначимо через коефіцієнт функціонала, що відповідає вектору , та позначимо
(їх називають оцінками відповідних векторів плану) .
Теорема 2.6. Якщо для деякого вектора виконується умова , то план не є оптимальним і можна відшукати такий план Х, для якого виконуватиметься нерівність .
Доведення. Помножимо (2.47) і (2.48) на і віднімемо результати відповідно з (2.45) та (2.46). Отримаємо:
; (2.51)
(2.52)
У співвідношенні (2.52) до обох частин додається величина для . У (2.51) додатні, тому завжди можна знайти таке , що всі коефіцієнти при векторах були б невід'ємними, інакше кажучи, отримати новий план задачі виду:
, якому згідно з (2.52) відповідає таке значення функціонала:
. (2.53)
Оскільки за умовою теореми і , то , що й потрібно було довести.
Якщо розглядається задача на відшукання мінімального значення цільової функції, то формулюється така теорема.
Теорема 2.7. Якщо для деякого вектора виконується умова , то план не є оптимальним і можна побудувати такий план Х, для якого виконуватиметься нерівність .
Доведення аналогічне попередньому.
Наслідок: (умова оптимальності плану задачі максимізації): якщо для деякого плану розклад всіх векторів у даному базисі задовольняє умову:
, (2.49)
то план є оптимальним розв'язком задачі лінійного програмування (2.36)--(2.38).
(умова оптимальності плану задачі мінімізації): якщо для деякого плану розклад всіх векторів у даному базисі задовольняє умову
, (2.50)
то план Х0 є оптимальним розв'язком задачі лінійного програмування.
Отже, для того, щоб план задачі лінійного програмування був оптимальним, необхідно і достатньо, щоб його оцінки були невід'ємними для задачі на максимум та недодатними для задачі на мінімум.
16. Розв'язування задачі лінійного програмування симплексним методом
Розглянемо, як, виходячи з початкового опорного плану задачі лінійного програмування, за допомогою симплексного методу знайти оптимальний план.
Продовжимо розгляд задачі (2.36)--(2.38), опорний план якої . Для дослідження даного плану на оптимальність (за умовою оптимальності плану задачі лінійного програмування) необхідно вектори системи обмежень (2.37) розкласти за базисними векторами і розрахувати значення оцінок .
Всі подальші обчислення зручно проводити в симплексній таблиці (табл. 2.6). У стовпці «Базис» записані змінні, що відповідають базисним векторам, а в стовпці «Сбаз» -- коефіцієнти функціонала відповідних базисних векторів. У стовпці «План» -- початковий опорний план , в цьому ж стовпці в результаті обчислень отримують оптимальний план. У стовпцях записані коефіцієнти розкладу кожного j-го вектора за базисом, які відповідають у першій симплексній таблиці коефіцієнтам при змінних у системі (2.37). У (m + 1)-му рядку в стовпці «План» записують значення функціонала для початкового опорного плану , а в інших стовпцях -- значення оцінок . Цей рядок симплексної таблиці називають оцінковим.
Значення знаходять підстановкою компонент опорного плану в цільову функцію, а значення -- при підстановці коефіцієнтів розкладу кожного j-го вектора за векторами базису, тобто ці значення в табл. 2.6 отримують як скалярний добуток:
,
де сі -- коефіцієнти функціонала, що відповідають векторам базису.
Таблиця 2.6
Перша симплексна таблиця для розв'язку задач лінійного програмування
|
і |
Базис |
Сбаз |
План |
c1 |
c2 |
… |
cl |
… |
cm |
cm + 1 |
… |
cj |
… |
ck |
… |
cn |
иі |
|
|
x1 |
x2 |
… |
xl |
… |
xm |
xm + 1 |
… |
xj |
… |
xk |
… |
xn |
||||||
|
1 |
x1 |
c1 |
b1 |
1 |
0 |
… |
0 |
… |
0 |
a1, m +1 |
… |
a1j |
… |
a1k |
… |
a1n |
и1 |
|
|
2 |
x2 |
c2 |
b2 |
0 |
1 |
… |
0 |
… |
0 |
a2, m + 1 |
… |
a2j |
… |
a2k |
… |
a2n |
и2 |
|
|
l |
xl |
cl |
bl |
0 |
0 |
… |
1 |
… |
0 |
al, m + 1 |
… |
alj |
… |
alk |
… |
aln |
иl |
|
|
m |
xm |
cm |
bm |
0 |
0 |
… |
0 |
… |
1 |
am, m + 1 |
… |
amj |
… |
amk |
… |
amn |
иm |
|
|
m + 1 |
Fj - cj ? 0 |
F(X0) |
0 |
0 |
… |
0 |
… |
0 |
Дm + 1 |
… |
Дj |
… |
Дk |
… |
Дn |
Після заповнення табл. 2.6 розраховують значення оцінок плану (останній рядок): . Потім згідно з умовою оптимальності плану задачі лінійного програмування, якщо всі (для задачі на максимум), то план є оптимальним.
Допустимо, що одна з оцінок , тоді план не є оптимальним і необхідно здійснити перехід до наступного опорного плану, якому буде відповідати більше значення функціонала. Якщо від'ємних оцінок кілька, то включенню до базису підлягає вектор, який вибирається як . Мінімум знаходять для тих індексів j, де . Якщо існує кілька однакових значень оцінок, що відповідають , то з відповідних їм векторів до базису включають той, якому відповідає максимальне значення функціонала.
Якщо хоча б для однієї від'ємної оцінки всі коефіцієнти розкладу відповідного вектора недодатні, то це означає, що функціонал є необмеженим на багатограннику розв'язків, тобто багатогранник у даному разі являє собою необмежену область і розв'язком задачі є .
Нехай , тобто мінімальне значення досягається для k-го вектора . Тоді до базису включається вектор . Відповідний стовпчик симплексної таблиці називають напрямним.
Для того, щоб вибрати вектор, який необхідно вивести з базису (згідно з процедурою переходу від одного опорного плану задачі до іншого -- 2.7.2), розраховують останній стовпчик табл. 2.6 -- значення .
.
З розрахованих значень необхідно вибрати найменше . Тоді з базису виключають i-ий вектор, якому відповідає .
Допустимо, що відповідає вектору, що знаходиться в l-му рядку табл. 2.6. Відповідний рядок симплексної таблиці називають напрямним.
Перетином напрямного стовпчика та напрямного рядка визначається елемент симплексної таблиці alk, який називають розв'язувальним елементом. За допомогою елемента alk і методу Жордана--Гаусса розраховують нову симплексну таблицю, що визначатиме наступний опорний план задачі.
Для визначення нового опорного плану необхідно всі вектори розкласти за векторами нового базису. Вектор Аk, який необхідно вводити до базису, в розкладі за початковим базисом має вигляд:
(2.54)
Вектор Аl виходить з базису, і його розклад за новим базисом отримаємо з виразу (2.54):
. (2.55)
Розклад вектора А0 за початковим базисом має вигляд:
. (2.56)
Для запису розкладу вектора в новому базисі підставимо вираз (2.55) у рівняння (2.56), маємо:
.
Отже, значення компонент наступного опорного плану розраховуються за формулами:
(2.57)
Розклад за початковим базисом будь-якого з векторів:
. (2.58)
Розклад за новим базисом отримаємо підстановкою (2.55) у (2.58):
.
Новий план: , де
(2.59)
Формули (2.57) та (2.59) є формулами повних виключень Жордана--Гаусса.
Отже, щоб отримати коефіцієнти розкладу векторів за векторами нового базису (перехід до наступного опорного плану та створення нової симплексної табл. 2.7), необхідно:
розділити всі елементи напрямного рядка на розв'язувальний елемент;
розрахувати всі інші елементи за формулами повних виключень Жордана--Гаусса (правило прямокутника).
Потім необхідно здійснити перевірку нових значень оцінкового рядка. Якщо всі Fj - сj 0, то план Х1 -- оптимальний, інакше переходять до відшукання наступного опорного плану. Процес продовжують до отримання оптимального плану, чи встановлення факту відсутності розв'язку задачі.
Якщо в оцінковому рядку останньої симплексної таблиці оцінка Fj - сj = 0 відповідає вільній (небазисній) змінній, то це означає, що задача лінійного програмування має альтернативний оптимальний план. Отримати його можна, вибираючи розв'язувальний елемент у зазначеному стовпчику таблиці та здійснивши один крок (одну ітерацію) симплекс-методом. У результаті отримаємо новий опорний план, якому відповідає те саме значення функціонала, що і для попереднього плану, тобто функціонал досягає максимального значення в двох точках багатогранника розв'язків, а отже, за властивістю 2 (§ 2.5) розв'язків задачі лінійного програмування така задача має нескінченну множину оптимальних планів.
Таблиця 2.7
Друга симплексна таблиця для відшукання опорного (оптимального) плану
|
і |
Базис |
Сбаз |
План |
c1 |
c2 |
… |
cl |
… |
cm |
cm + 1 |
… |
cj |
… |
ck |
… |
cn |
иі |
|
|
x1 |
x2 |
… |
xl |
… |
xm |
xm + 1 |
… |
xj |
… |
xk |
… |
xn |
||||||
|
1 |
x1 |
c1 |
|
1 |
0 |
… |
0 |
… |
0 |
… |
… |
… |
и1 |
|||||
|
2 |
x2 |
c2 |
0 |
1 |
… |
0 |
… |
0 |
… |
… |
… |
и2 |
||||||
|
l |
xl |
cl |
|
0 |
0 |
… |
1 |
… |
0 |
… |
|
… |
|
… |
|
иl |
||
|
m |
xm |
cm |
|
0 |
0 |
… |
0 |
… |
1 |
… |
|
… |
|
… |
|
иm |
||
|
m + 1 |
Fj - cj ? 0 |
F(X1) |
0 |
0 |
… |
0 |
… |
0 |
… |
… |
… |
Зауваження Розв'язання задачі лінійного програмування на відшукання мінімального значення функціонала відрізняється лише умовою оптимальності опорного плану. До базису включають вектор, для якого , де максимум знаходять для тих j, яким відповідають . Всі інші процедури симплексного методу здійснюються аналогічно, як у задачі лінійного програмування на відшукання максимального значення функціонала.
17. Приклад розв'язування задачі симплекс-методом
Розглянемо застосування симплекс-методу для розв'язання деяких задач лінійного програмування.
Продукція чотирьох видів А, В, С і D проходить послідовну обробку на двох верстатах. Тривалість обробки одиниці продукції кожного виду наведена в табл. 2.8.
Таблиця 2.8
Тривалість обробки продукції на верстатах, год
|
Верстат |
Тривалість обробки одиниці продукції |
||||
|
А |
В |
С |
D |
||
|
1 |
2 |
3 |
4 |
2 |
|
|
2 |
3 |
2 |
1 |
2 |
Витрати на виробництво одиниці продукції кожного виду визначають як величини, прямо пропорційні до часу використання верстатів (у машино-годинах). Вартість однієї машино-години становить 10 грн для верстата 1 і 15 грн -- для верстата 2. Тривалість використання верстатів обмежена: для верстата 1 вона становить 450 машино-годин, а для верстата 2 -- 380 машино-годин.
Ціна одиниці продукції видів А, В, С і D дорівнює відповідно 73, 70, 55 та 45 грн.
Визначити оптимальний план виробництва продукції всіх чотирьох видів, який максимізує загальний прибуток.
Побудова економіко-математичної моделі. Нехай хj -- план виробництва продукції j-го виду, де j може набувати значень від 1 до 4.
Умовами задачі будуть обмеження на тривалість використання верстатів для виробництва продукції всіх видів:
для верстата 1 (маш.-год.);
для верстата 2 (маш.-год.).
Цільовою функцією задачі є загальний прибуток від реалізації готової продукції, який розраховується як різниця між ціною та собівартістю виготовлення продукції кожного виду:
.
Отже, математична модель цієї задачі має такий вигляд:
за умов:
Розв'язання. Розв'яжемо задачу симплекс-методом згідно з розглянутим алгоритмом.
I. Запишемо систему обмежень задачі в канонічному вигляді. Для цього перейдемо від обмежень-нерівностей до строгих рівнянь, увівши до лівої частини обмежень додаткові змінні х5 та х6:
Ці додаткові змінні за економічним змістом означають недовикористаний для виробництва продукції час роботи верстатів 1 та 2. У цільовій функції Z додаткові змінні мають коефіцієнти, які дорівнюють нулю:
Канонічну систему обмежень задачі запишемо у векторній формі:
Де
Оскільки вектори та одиничні та лінійно незалежні, то саме з них складається початковий базис у зазначеній системі векторів. Змінні задачі х5 та х6, що відповідають одиничним базисним векторам, називають базисними, а решту -- вільними змінними задачі лінійного програмування. Прирівнюючи вільні змінні до нуля, з кожного обмеження задачі дістаємо значення базисних змінних:
Згідно з визначеними векторна форма запису системи обмежень цієї задачі матиме вигляд:
.
Оскільки додатні коефіцієнти х5 та х6 відповідають лінійно незалежним векторам, то за означенням
є опорним планом задачі і для цього початкового плану
.
II. Складемо симплексну таблицю для першого опорного плану задачі.
|
Базис |
Сбаз |
План |
8 |
10 |
0 |
- 5 |
0 |
0 |
||
|
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
|||||
|
х5 |
0 |
450 |
2 |
3 |
4 |
2 |
1 |
0 |
150 |
|
|
х6 |
0 |
380 |
3 |
2 |
1 |
2 |
0 |
1 |
190 |
|
|
Zj - сj ? 0 |
0 |
-8 |
-10 |
0 |
5 |
0 |
0 |
Елементи останнього рядка симплекс-таблиці є оцінками j, за допомогою яких опорний план перевіряють на оптимальність. Їх визначають так:
;
;
;
;
;
.
У стовпчику «План» оцінкового рядка записують значення цільової функції Z, якого вона набуває для визначеного опорного плану: .
III. Після обчислення всіх оцінок опорний план перевіряють на оптимальність.
Для цього продивляються елементи оцінкового рядка. Якщо всі (для задачі на max) або (для задачі на min), то визначений опорний план є оптимальним. Якщо ж в оцінковому рядку є хоча б одна оцінка, що не задовольняє умову оптимальності (від'ємна в задачі на max або додатна в задачі на min), то опорний план є неоптимальним і його можна поліпшити.
У цій задачі в оцінковому рядку дві оцінки та від'ємні, тобто не задовольняють умову оптимальності, і тому перший визначений опорний план є неоптимальним. За алгоритмом симплекс-методу необхідно від нього перейти до іншого опорного плану задачі.
IV. Перехід від одного опорного плану до іншого здійснюють зміною базису, тобто через виключення з поточного базису якоїсь змінної та включення замість неї нової з числа вільних змінних.
Для введення до нового базису вибираємо змінну х2, оскільки їй відповідає найбільша за абсолютною величиною оцінка з-поміж тих, які не задовольняють умову оптимальності (|-10|>|-8|).
Щоб визначити змінну, яка підлягає виключенню з поточного базису, для всіх додатних елементів стовпчика «х2» знаходимо відношення і вибираємо найменше значення. Згідно з даними симплексної таблиці маємо, що , і тому з базису виключаємо змінну х5, а число а12 = 3 -- розв'язувальний елемент. Дальший перехід до нового опорного плану задачі полягає в побудові наступної симплексної таблиці, елементи якої розраховують за методом Жордана--Гаусса.
Друга симплексна таблиця має такий вигляд:
|
Базис |
Сбаз |
План |
8 |
10 |
0 |
- 5 |
0 |
0 |
||
|
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
|||||
|
х2 |
10 |
150 |
2/3 |
1 |
4/3 |
2/3 |
1/3 |
0 |
225 |
|
|
х6 |
0 |
80 |
5/3 |
0 |
-5/3 |
2/3 |
-2/3 |
1 |
48 |
|
|
Zj - сj ? 0 |
1500 |
-4/3 |
0 |
40/3 |
35/3 |
10/3 |
0 |
У цій таблиці спочатку заповнюють два перших стовпчики «Базис» і «Сбаз», а решту елементів нової таблиці розраховують за розглянутими нижче правилами:
1. Кожний елемент розв'язувального (напрямного) рядка необхідно поділити на розв'язувальний елемент і отримані числа записати у відповідний рядок нової симплексної таблиці.
2. Розв'язувальний стовпчик у новій таблиці записують як одиничний з одиницею замість розв'язувального елемента.
3. Якщо в напрямному рядку є нульовий елемент, то відповідний стовпчик переписують у нову симплексну таблицю без змін.
4. Якщо в напрямному стовпчику є нульовий елемент, то відповідний рядок переписують у нову таблицю без змін.
Усі інші елементи наступної симплексної таблиці розраховують за правилом прямокутника.
Щоб визначити будь-який елемент нової таблиці за цим правилом, необхідно в попередній симплексній таблиці скласти умовний прямокутник, вершини якого утворюються такими числами:
1 -- розв'язувальний елемент (число 1);
2 -- число, що стоїть на місці елемента нової симплексної таблиці, який ми маємо розрахувати;
3 та 4 -- елементи, що розміщуються в двох інших протилежних вершинах умовного прямокутника.
Необхідний елемент нової симплекс-таблиці визначають за такою формулою:
.
Наприклад, визначимо елемент , який розміщується в новій таблиці в другому рядку стовпчика «х4». Складемо умовний прямокутник:
Тоді . Це значення записуємо в стовпчик «х4» у другому рядку другої симплексної таблиці.
Аналогічно розраховують усі елементи нової симплексної таблиці, у тому числі й елементи стовпчика «План» та оцінкового рядка. Наявність двох способів зображення визначення оцінок опорного плану (за правилом прямокутника та за відповідною формулою) дає змогу контролювати правильність арифметичних обчислень на кожному кроці симплекс-методу.
Після заповнення нового оцінкового рядка перевіряємо виконання умови оптимальності Zj - сj ? 0 для другого опорного плану. Цей план також неоптимальний, оскільки . Використовуючи процедуру симплекс-методу, визначаємо третій опорний план задачі, який наведено у вигляді таблиці:
|
Базис |
Сбаз |
План |
8 |
10 |
0 |
- 5 |
0 |
0 |
|
|
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
||||
|
х2 |
10 |
118 |
0 |
1 |
2 |
2/5 |
3/5 |
-2/5 |
|
|
х1 |
8 |
48 |
1 |
0 |
-1 |
2/5 |
-2/5 |
3/5 |
|
|
Zj - сj ? 0 |
1564 |
0 |
0 |
12 |
61/5 |
14/5 |
4/5 |
В оцінковому рядку третьої симплексної таблиці немає від'ємних чисел, тобто всі і задовольняють умову оптимальності. Це означає, що знайдено оптимальний план задачі:
Або
Х* = (48; 118; 0; 0; 0; 0);
.
Отже, план виробництва продукції, що передбачає випуск 48 одиниць продукції А та 118 одиниць продукції В, є оптимальним. Він уможливлює отримання найбільшого прибутку за заданих умов (1564 грн). При цьому час роботи верстатів використовується повністю (х5 = х6 = 0).
Наведені вище три симплексні таблиці можна об'єднати в одну та послідовно записувати в ній всі ітерації.
Размещено на Allbest.ru
Подобные документы
Загальна модель задачі математичного програмування, задача лінійного програмування та особливості симплекс–методу для розв’язання задач лінійного програмування Економіко–математична модель конкретної задачі, алгоритм її вирішення за допомогою Exel.
контрольная работа [109,7 K], добавлен 24.11.2010Приклади задач математичного програмування (на добір оптимальної суміші сплавів, складання оптимального раціону, транспортна, про оптимальний добір). Економічна модель задачі. Геометрична інтерпретація стандартної задачі, її розв’язання симплекс-методом.
курсовая работа [8,3 M], добавлен 28.11.2010Задачі лінійного програмування. Побудова першого опорного плану системи нерівностей. Введення додаткових змінних. Індексний рядок та негативні коефіцієнти. Побудова математичної моделі. Визначення потенціалів опорного плану. Область допустимих значень.
контрольная работа [232,3 K], добавлен 28.03.2011Опис опуклих та вгнутих функцій. Загальна постановка задачі опуклого програмування. Теорема Куна-Таккера та її застосування для розв’язування задач опуклого програмування. Квадратична форма та її властивості. Постановка задачі квадратичного програмування.
презентация [454,1 K], добавлен 10.10.2013Визначення оптимальних обсягів виробництва, що максимізують дохід фірми, та розв'язання транспортної задачі за допомогою математичного моделювання та симплекс-методу. Знайдення графічним методом екстремумів функції в області, визначеній нерівностями.
контрольная работа [280,6 K], добавлен 28.03.2011Поняття задачі лінійного програмування та різні форми її задання. Загальна характеристика транспортної задачі, її математична модель. Графічний метод для визначення оптимального плану задач лінійного програмування. Правило побудови двоїстої задачі.
контрольная работа [1,5 M], добавлен 04.09.2015Побудова опорного плану систему нерівностей. Постановка задачі на максимум. Індексний рядок та негативні коефіцієнти. Задача лінійного програмування. Рішення задачі симплексним методом. Введення додаткових змінних. Оптимальний план двоїстої задачі.
контрольная работа [278,4 K], добавлен 28.03.2011Набуття навичок складання математичної моделі задачі планування виробництва та її реалізації із використанням табличного процесору Excel. Визначення плану виробництва та забезпечення максимуму прибутку від реалізації. Лінійне програмування задач.
лабораторная работа [130,4 K], добавлен 09.03.2009Розробка програмного комплексу для розв’язання задачі цілочисельного програмування типу "Задача комівояжера". Класифікація задач дослідження операцій. Вибір методу розв’язання транспортної задачі; алгоритмічне і програмне забезпечення, тести і документи.
курсовая работа [807,7 K], добавлен 07.12.2013Складання математичної моделі задачі планування виробництва та її реалізації із використанням табличного процесору MS Excel. Визначення плану виробництва та забезпечення максимуму прибутку від реалізації. Розв'язок задач з лінійного програмування.
лабораторная работа [105,7 K], добавлен 09.03.2009
