Розв'язок задачі лінійного програмування
Контрольная работа - Математика и статистика
Другие контрольные работы по предмету Математика и статистика
де лінійно незалежні і за властивістю 3 розвязків задачі лінійного програмування план є кутовою точкою багатогранника розвязків, а отже може бути початковим опорним планом.
Розглянемо, як виходячи з початкового опорного плану (5) перейти до наступного опорного плану, що відповідає процесу перебору кутових точок багатогранника розвязків.
Оскільки є базисом m-вимірного простору, то кожен з векторів співвідношення (5) може бути розкладений за векторами базису причому єдиним чином:
Розглянемо такий розклад для довільного не базисного вектора, наприклад, для :
(7)
Припустимо, що у виразі (7) існує хоча б один додатній коефіцієнт .
Введемо до розгляду деяку поки що невідому величину , помножимо на неї обидві частини рівності (3.34) і віднімемо результат з рівності (3.33), маємо:
(8)
Таким чином вектор
є планом у тому випадку, коли його компоненти невідємні. За припущенням , отже ті компоненти вектора в які входять будуть невідємними, тому необхідно розглядати лише ті компоненти, які містять додатні . Отже необхідно знайти таке значення , при якому для всіх буде виконуватися умова невідємності плану задачі:
(9)
З (3.36) отримуємо, що для шуканого має виконуватися умова . Отже вектор буде планом задачі для будь-якого , що задовольняє умову
,
де мінімум знаходимо по тих i, для яких .
Опорний план не може містити більш ніж m додатних компонент, тому в плані необхідно перетворити в нуль хоча б одну з компонент. Припустимо, що
для деякого значення і, тоді відповідна компонента плану перетвориться в нуль. Нехай це буде перша компонента плану, тобто
.
Підставимо значення у вираз:
,
якщо позначити
, ,
то рівняння можна подати у вигляді розкладу:
,
якому відповідає наступний опорний план:
.
Для визначення наступного плану необхідно аналогічно продовжити процес: будь-який вектор, що не входить в базис розкласти за базисними векторами, а потім визначити таке , для якого один з векторів виключається з базису.
Узагальнюючи розглянутий процес, маємо визначення нових опорних планів полягає у виборі вектора, який має ввійти в базис і вектора, що має вийти з базису. Така процедура відповідає переходу від одного базису до іншого за допомогою методу Жордана-Гауса.
Необхідно відмітити, що для випадку коли вектор підлягає включенню в базис, а в його розкладі всі , то, очевидно, не існує такого , який виключав би один з векторів розкладу (3.35). В такому випадку план містить m+1 додатних компонент, отже система векторів буде лінійно залежною і визначає не кутову точку багатогранника розвязків, а функціонал не може в ній досягати свого максимального значення. Це означає, що функціонал є необмеженим на багатограннику розвязків.
Симплексний метод здійснює направлений перебір опорних планів, що дозволяє переходити від одного плану до іншого, який є хоча б не гіршим від попереднього за значенням, що він надає функціоналу. Отже окремим питанням постає вибір вектору, який необхідно вводити в базис при здійсненні ітераційної процедури симплексного методу.
Теорема 1. Якщо для деякого вектора виконується умова , то план не є оптимальним і можливо побудувати такий план Х, для якого виконуватиметься нерівність .
Доведення. Помножимо (3.39) і (3.40) на і віднімемо результати відповідно з (3.37) та (3.38), отримаємо:
(*)
У співвідношенні до обох частин додається величина для , додатні, тому завжди можливо знайти таке , що всі коефіцієнти при векторах були невідємними, іншими словами отримати новий план задачі виду:
,
якому згідно відповідає значення функціоналу
Так як за умовою теореми
і , то .
Що і потрібно було довести.
Теорема 2. Якщо для деякого вектора виконується умова , то план не є оптимальним і можливо побудувати такий план Х, для якого виконуватиметься нерівність .
Запишемо канонічну задачу:
Розвяжемо симплекс-методом:
110-M00x1x2x3x4x5x6BTx443-1100123**x5-1200104x61-1000144F-1-1000000Mf-4-31000-120**
110-M00x1x2x3x4x5x6BTx110,75-0,250,250034x502,75-0,250,251072,545**x60-1,750,25-0,25011F0-0,25-0,250,250030Mf00010000**
110-M00x1x2x3x4x5x6BTx110-0,18180,1818-0,272701,091x201-0,090910,090910,363602,545x6000,09091-0,090910,636415,45560**F00-0,27270,27270,0909103,6360Mf00010000**
110-M00x1x2x3x4x5x6BTx110001212x20100118x3001-17116060F000023200Mf00010000
Отже, х* = (12, 8, 60), L(x*)max = 20.
Задача 3
Для задачі побудувати двоїсту, розвязати і за розвязком знайти розвязок двоїстої:
Розвязання:
Кожна задача лінійного програмування повязана з іншою, так званою двоїстою задачею.
Економічну інтерпретацію кожної з пари задач розглянемо на прикладі виробничої задачі.
Початкова задача:
max z = c1x1 + c2x2 + … + cnxn
,
Визначити, яку кількість продукції кожного j-го виду необхідно виготовляти в процесі виробництва, щоб максимізувати загальну виручку від реалізації продукції підприємства. Причому відомі: загальна кількість ресурсів , нормативи використання кожного і-го виду ресурсу на кожен j-ий вид продукції , а також ціна реалізації одиниці продукції.
Розглянемо тепер ту саму задачу з іншої точки зору. Припустимо, що за певних умов доцільно продавати деяку частину чи всі наявні в господарстві ресурси. Необхідно визначити цінність ресурсів. Кожному ресурсу поставимо у відповідніс