Федеральне агентство з освіти
Державна освітня установа вищої професійної освіти
Пермський державний технічний університет
Лисьвенського філія
Кафедра ЄП
Курсова робота
з дисципліни «Системний аналіз і дослідження операцій»
по темі: «Симплекс метод у формі презентації»
Виконав студент групи ВІВТ-06-1:
Старцева Н. С.
Перевірив викладач:
Мухаметьянов І.Т.
Лисьва 2010р.
Зміст
Введення
Математичне програмування
Графічний метод
Табличний симплекс - метод
Метод штучного базису
Модифікований симплекс - метод
Двоїстий симплекс - метод
Загальний вид задачі лінійного програмування
Рішення задачі лінійного програмування симплекс-методом
Обчислювальні процедури симплекс - методу
Теорема 1:
Теорема 2:
Теорема 3:
Теорема 4:
Теорема 5:
Перехід до нового опорного плану
Двоїста задача
Теорема 1 (перша теорема подвійності)
Теорема 2 (друга теорема подвійності)
Висновок
Додаток
Введення
В останні роки в прикладній математиці велика увага приділяється нового класу задач оптимізації, які полягають у знаходженні в заданій області точок найбільшого або найменшого значення певної функції, що залежить від великого числа змінних. Це так звані завдання математичного програмування, що виникають у найрізноманітніших галузях людської діяльності і перш за все в економічних дослідженнях, в практиці планування й організації виробництва («Визначення найкращого складу суміші», «Завдання про оптимальний плані випуску продукції», «Оптимізація міжгалузевих потоків», «Задача про дієту», «Транспортна задача» і т.д.).
Лінійне програмування - це наука про методи дослідження і відшукання найбільших і найменших значень лінійної функції, на невідомі якої накладено лінійні обмеження. Таким чином, завдання лінійного програмування ставляться до завдань на умовний екстремум функції. Здавалося б, що для дослідження лінійної функції багатьох змінних на умовний екстремум досить застосувати добре розроблені методи математичного аналізу, однак неможливість їх використання можна досить просто проілюструвати.
Дійсно, шлях необхідно досліджувати на екстремум лінійну функцію
Z = С 1 х 1 + С 2 х 2 + ... + С N x N
при лінійних обмеженнях
a 11 x 1 + a 22 x 2 + ... + a 1N Х N = b 1
a 21 x 1 + a 22 x 2 + ... + A 2N Х N = b 2
. . . . . . . . . . . . . . .
a М 1 x 1 + a М 2 x 2 + ... + A М N Х N = b М
Так як Z - лінійна функція, то Z = С j, (j = 1, 2, ..., n), то всі коефіцієнти лінійної функції не можуть бути рівні нулю, отже, всередині області, утвореної системою обмежень, екстремальні точки не існують. Вони можуть бути на кордоні області, але досліджувати точки кордону неможливо, оскільки приватні похідні є константами.
Для вирішення завдань лінійного програмування треба було створення спеціальних методів. Особливо широке поширення лінійне програмування отримало в економіці, так як дослідження залежностей між величинами, що зустрічаються в багатьох економічних завданнях, призводить до лінійної функції з лінійними обмеженнями, накладеними на невідомі.
Мета даної курсової роботи: вивчити і навчитися застосовувати на практиці симплекс - метод для вирішення завдань лінійного програмування.
Завдання курсової турботи:
привести теоретичний матеріал;
на прикладах розглянути симплекс метод;
представити дану курсову роботу у вигляді презентації.
Математичне програмування
Математичне програмування займається вивчення екстремальних завдань і пошуком методів їх вирішення. Завдання математичного програмування формулюються так: знайти екстремум деякою функції багатьох змінних f (x 1, x 2, ..., x n) при обмеженнях g i (x 1, x 2, ..., x n) * b i, де g i - функція, що описує обмеження, * - один з таких знаків £, =, ³, а b i - дійсне число, i = 1, ... , M. f називається цільовою функцією.
Лінійне програмування - це розділ математичного програмування, в якому розглядаються методи вирішення екстремальних задач з лінійним функціоналом і лінійними обмеженнями, яким повинні задовольняти шукані змінні.
Задачу лінійного програмування можна сформулювати так. Знайти max
за умови: a 11 x 1 + a 12 x 2 +. . . + A 1n x n £ b 1;
a 21 x 1 + a 22 x 2 +. . . + A 2n x n £ b 2;
. . . . . . . . . . . . . . . . . . . . . . . . . . .
a m1 x 1 + a m2 x 2 +. . . + A mn x n £ b m;
x 1 ³ 0, x 2 ³ 0,. . . , X n ³ 0.
Ці обмеження називаються умовами не заперечності. Якщо всі обмеження задані у вигляді строгих рівностей, то дана форма називається канонічною.
У матричній формі завдання лінійного програмування записують наступним чином.
Знайти:
max c T x
за умови:
A x £ b;
x ³ 0,
де А - матриця обмежень розміром (m 'n),
b (m '1) - вектор-стовпець вільних членів,
x (n '1) - вектор змінних,
з Т = (c 1, c 2, ..., c n) - вектор-рядок коефіцієнтів цільової функції.
Рішення х 0 називається оптимальним, якщо для нього виконується умова:
з Т х 0 ³ ст х, для всіх х Î R (x).
Оскільки min f (x) еквівалентний max [- f (x)], то завдання лінійного програмування завжди можна звести до еквівалентної задачі максимізації.
Для вирішення завдань даного типу застосовуються методи:
1) графічний;
2) табличний (прямий, простий) симплекс - метод;
3) метод штучного базису;
4) модифікований симплекс - метод;
5) двоїстий симплекс - метод.
Графічний метод
Графічний метод досить простий і наочний для вирішення завдань лінійного програмування з двома змінними. Він заснований на геометричному представленні допустимих рішень і цільової функції задачі.
Кожне з нерівностей завдання лінійного програмування визначає на координатній площині деяку полуплоскость, а система нерівностей в цілому - перетин відповідних площин. Безліч точок перетину даних півплощини називається областю допустимих рішень (ОДР). ОДР завжди являє собою опуклу фігуру, тобто володіє наступною властивістю: якщо дві точки А і В належать цій фігурі, то і весь відрізок АВ належить їй. ОДР графічно може бути представлена опуклим багатокутником, необмеженої опуклої багатокутної областю, відрізком, променем, однією точкою. У разі несумісної системи обмежень задачі ОДР є порожнім безліччю.
Табличний симплекс - метод
Для його застосування необхідно, щоб знаки в обмеженнях були виду "менше або дорівнює", а компоненти вектора b - позитивні.
Алгоритм рішення зводиться до наступного:
Приведення системи обмежень до канонічного виду шляхом введення додаткових змінних для приведення нерівностей до рівності.
Якщо у вихідній системі обмежень були присутні знаки "одно"
або "більше або дорівнює", то в зазначені обмеження додаються
штучні змінні, які так само вводяться і в цільову функцію зі знаками, що визначаються типом оптимуму.
Формується симплекс-таблиця.
Розраховуються симплекс - різниці.
Приймається рішення про закінчення або продовженні рахунку.
При необхідності виконуються ітерації.
На кожній ітерації визначається вектор, що вводиться в базис, і вектор, виведений з базису. Таблиця перераховується за методом Жордана-Гаусса або яким-небудь іншим способом.
Метод штучного базису
Даний метод рішення застосовується при наявності в обмеженні знаків
"Дорівнює", "більше або дорівнює", "менше або дорівнює" і є модифікацією табличного методу. Рішення системи виробляється шляхом введення штучних змінних зі знаком, що залежать від типу оптимуму, тобто для виключення з базису цих змінних останні вводяться в цільову функцію з великими негативними коефіцієнтами m, а в завдання мінімізації - з позитивними m. Таким чином, з вихідної виходить нова m - завдання.
Якщо в оптимальному рішенні m - завдання немає штучних змінних, це рішення є оптимальне рішення вихідної завдання. Якщо ж в оптимальному рішенні m - завдання хоч одна з штучних змінних буде відмінна від нуля, то система обмежень вихідної задачі несовместна і вихідна завдання нерозв'язна.
Модифікований симплекс - метод
В основу даного різновиду симплекс-методу покладені такі особливості лінійної алгебри, які дозволяють в ході виконання завдання працювати з частиною матриці обмежень. Іноді метод називають методом зворотної матриці.
У процесі роботи алгоритму відбувається спонтанне звернення матриці обмежень по частинах, відповідним поточним базисним векторам. Зазначена здатність робить дуже привабливою машинну реалізацію обчислень внаслідок економії пам'яті під проміжні змінні і значного скорочення часу рахунку, хороша для ситуацій, коли число змінних n значно перевищує число обмежень m.
В цілому, метод відображає традиційні риси загального підходу до вирішення завдань лінійного програмування, що включає в себе канонізацію умов завдання, розрахунок симплекс - разностей, перевірку умов оптимальності, прийняття рішень про корекцію базису і виключення Жордана-Гаусса.
Особливості полягають у наявності двох таблиць - основний і допоміжної, порядку їх заповнення і деякої специфічності розрахункових формул.
Двоїстий симплекс - метод
Двоїстий симплекс-метод, як і симплекс-метод, використовується при знаходженні розв'язку задачі лінійного програмування, записаної у формі основної задачі, для якої серед векторів, складених з коефіцієнтів при невідомих у системі рівнянь, є m одиничних. Разом з тим двоїстий симплекс-метод можна застосовувати при вирішенні завдання лінійного програмування, вільні члени системи рівнянь якої можуть бути будь-якими числами (при виконанні завдання симплексним методом ці числа передбачалися невід'ємними).
Загальний вид задачі лінійного програмування
,
Обмеження:
1. Праві частини всіх обмежень повинні бути невід'ємними b i ≥ 0, i = 1, .. m. Якщо який-небудь з коефіцієнтів b i <0, то необхідно коефіцієнти обмеження ліворуч і праворуч домножити на "-1" і змінити знак даного обмеження на протилежний;
2. Всі обмеження мають бути представлені у вигляді рівності, тому при переході від нерівності до рівності використовують апарат додаткових змінних. Якщо вихідні обмеження визначають витрата деякого ресурсу (знак " "), То змінні x j ≥ 0, j = n +1, ... k слід інтерпретувати як залишок, або невикористану частину ресурсу. У цьому випадку x j - залишкова змінна і вводиться в рівняння зі знаком" + ". Якщо вихідні обмеження визначають надлишок деякого ресурсу (знак "
"), То вводиться надлишкова мінлива x j ≥ 0, j = k +1, ... N знаком" - ".
Змінні:
Всі змінні повинні бути невід'ємними, тобто x j ≥ 0, j = 1, ... n.
Якщо змінна не має обмеження в знаку, то її потрібно представити як різниця двох невід'ємних змінних: x = x '- x'', де x' ≥ 0, x''≥ 0. Таку підстановку варто використовувати у всіх обмеженнях, що містять цю змінну, а також у вираженні для цільової функції. Якщо така мінлива потрапляє в оптимальне рішення, то
.
Цільова функція:
Підлягає максимізації або мінімізації. Max z = - min (- z)
Система обмежень у вигляді рівностей і нерівностей утворює опукле безліч - опуклий багатогранник. Це безліч може бути обмеженим і необмеженим. Цільова функція задачі лінійного програмування також є опуклою функцією. Таким чином, завдання лінійного програмування є окремим випадком завдання опуклого програмування.
Розглянемо систему обмежень задачі лінійного програмування у вигляді рівностей
Система (1) лінійних рівнянь сумісна, якщо вона має, принаймні, одне рішення.
Система (1) називається надмірною, якщо одне з рівнянь можна виразити у вигляді лінійної комбінації інших.
У системі (1) число змінних (невідомих x j) n більше, ніж число обмежень m. Будемо вважати, що ранг цієї системи дорівнює m (система не надлишкова) і що система (1) совместна. Тоді m змінних із загального їх числа утворюють базисні змінні, а решта (n - m) змінних називають небазисних.
Якщо система рівнянь має рішення, то вона має і базисне рішення.
Рішення системи рівнянь (1) називають допустимим, якщо всі його компоненти ненегативні.
Якщо система лінійних рівнянь має допустимим рішенням, то вона має і базисне допустиме рішення. Сукупність усіх допустимих рішень системи (1) є опукле безліч, тобто безліч рішень задачі лінійного програмування опукло. Так як це безліч утворено площинами (гіперплощинами), то воно має вигляд опуклого багатогранника. Базисне допустиме рішення відповідає крайній точці опуклого багатогранника (його грані або вершині). Якщо існує оптимальне рішення задачі лінійного програмування, то існує базисне оптимальне рішення.
Цільова функція задачі лінійного програмування є рівняння площини (або гіперплощини для числа змінних більше трьох). Максимальне або мінімальне значення цільова функція задачі лінійного програмування досягає або у вершині опуклого багатогранника, або на одній з його граней. Таким чином, рішення (рішення) задачі лінійного програмування лежить в вершинах випуклого многогранника і для його знаходження треба обчислити значення цільової функції в вершинах випуклого многогранника, що визначається умовами - обмеженнями завдання.
Рішення задачі лінійного програмування симплекс-методом
Пряма задача.
Розглянемо задачу лінійного програмування у канонічній формі:
Знайти максимум (мінімум) функції
за умов
Передбачається, що рішення цього завдання існує. Щоб знайти оптимальне рішення, треба знайти допустимі базисні рішення, а з них вибрати оптимальне базисне рішення.
Симплекс - метод - це алгебраїчний метод вирішення завдань лінійного програмування. В процесі обчислень проводитися послідовний обхід вершин багатогранника рішень (ОДР) з перевіркою в кожній вершині умов оптимальності. При цьому кожен перехід в суміжну вершину супроводжується поліпшенням цільової функції.
Обчислювальні процедури симплекс - методу
При графічному методі розв'язання задачі лінійного програмування (ЗЛП) оптимального рішення відповідає завжди одна з кутових (екстремальних) точок простору рішень. Це результат покладений в основу побудови симплекс-метода. Симплекс-метод не має наочністю геометричного представлення простору рішень.
Симплекс-метод реалізує упорядкований процес, при якому, починаючи з деякої вихідної припустимою кутовий точки, здійснюються послідовні переходи від однієї припустимою екстремальній точки в іншу, поки не буде знайдена точка оптимального рішення.
Позначимо: N - загальна кількість змінних в ЗЛП, представленої в канонічній формі; n - кількість вихідних змінних; m - кількість обмежень, n q - кількість додаткових змінних, тоді N = n + n q. Кожна вершина багатогранника рішень має m - ненульових змінних і
(N - m) - нульових змінних. Ненульові змінні називаються базисними, нульові змінні - небазисних. Доповнимо систему рівностей рівністю цільової функції, при цьому будемо вважати, що z є m +1 базисної змінної, яка завжди присутня в базисі для будь-якої вершини.
Для отримання рішення складається початковий допустимий базис, в якому базисні змінні повинні бути представлені у вигляді одиничних орт. Це означає, що рівняння, що представляють дану вершину повинні включати кожну базисну змінну тільки в одному рядку з коефіцієнтом, рівним 1.
При виборі початкового допустимого базису для складання симплекс-таблиці на першому кроці вихідні x 1, x 2 змінні прирівнюються до нуля і є небазисних, серед введених додаткових змінних вибираються змінні з коефіцієнтами рівними одиниці. Змінні x 3, x 4, x 5 в равенствах (2) - (4) є базисними і в z - рядок входять з коефіцієнтами, рівними 0. Для заповнення симплекс-таблиці необхідно цільову функцію перетворити до виду
.
Таким чином, остаточно отримуємо:
(1)
(2)
(3)
(4)
При складанні симплекс-таблиці дотримуються наступних правил:
в крайньому лівому стовпчику розташовуються базисні змінні і z;
в крайньому правому стовпчику розташовуються праві частини обмежень;
в першому рядку розташовуються змінні в певному порядку: спочатку z, потім небазисних змінні, базисні змінні розташовуються в останніх m стовпцях перед правою частиною.
св. | z | x 1 | x 2 | x 3 | x 4 | x 5 | |
z | 0 | 1 | -C 1 | -C 2 | 0 | 0 | 0 |
X 3 | b 1 | 0 | a 11 | a 12 | 1 | 0 | 0 |
X 4 | b 2 | 0 | a 21 | a 22 | 0 | 1 | 0 |
X 5 | b 3 | 0 | a 31 | a 32 | 0 | 0 | 1 |
Ідею розглянемо на прикладі:
7 x 1 +5 x 2 → max
2 x 1 +3 x 2 ≤ 19
2 x 1 + x 2 ≤ 13
3 x 2 ≤ 15
3 x 1 ≤ 18
x 1 ≥ 0, x 2 ≥ 0
Запишемо завдання в канонічному вигляді. При необхідності попередньо нерівність перетворити так щоб всі вільні члени були невід'ємними.
Симплекс метод в послідовному перетворенні системи рівнянь до отримання потрібного рішення. У загальному випадку ті змінні, в системі рівнянь, визначник при яких не дорівнює 0 і є максимумом порядку, називаються базисними змінними.
7 x 1 +5 x 2 → max
2 x 1 +3 x 2 + x 3 = 19
2 x 1 + x 2 + x 4 = 13
3 x 2 + x 5 = 15
3 x 1 + x 6 = 18
x i ≥ 0, (i = 1, ... n)
У нашому випадку базисними змінними є x 3, x 4, x 5, x 6. Решта змінні є вільними (x 1, x 2). Надаючи довільні значення вільним змінним ми будемо отримувати різні значення базисних. Будь-яке рішення системи обмежень задачі називається допустимим. Опорним називається рішення задачі, записане в канонічному вигляді в якому вільні змінні рівні 0.
Теорема 1:
Оптимальне рішення задачі лінійного програмування перебувати серед опорних рішень. Ідея симплекс методу полягає в тому, що певним правилом перебираються опорні рішення до знаходження оптимального серед них, перебираючи опорні рішення, по суті, ми перебираємо різні базисні змінні, тобто на черговому кроці деяка змінна перекладається з числа базисних, а замість неї деяка змінна з числа вільних в число базисних.
7x 1 +5 x 2 → max
x 3 = 19-2 x 1 -3 x 2 (0, 0, 19, 13, 15, 18)
x 4 = 13-2 x 1 - x 2 Первісна опорний план
x 5 = 15 - 3x 2
x 6 = 18 - 3x 1 F (x 1, x 2) = 7 * 0 +5 * 0 = 0
x i ≥ 0, (i = 1, ... n)
На інтуїтивному рівні зрозуміло, що природним буде збільшення x 1, так як коефіцієнт при ньому більше ніж при x 2. Залишаючи x 2 = 0, ми можемо збільшувати до тих пір, поки x 3, x 4, x 5, x 6 будуть залишатися невід'ємними.
x 1 = min {19 / 2, 13 / 2; ∞; 18 / 3} = 6
Це означає що при x 1 = 6, x 6 = 0, тобто x 1-переходить у число базисних, а x 6-в число вільних.
x 1 = 6-1/3 x 6
Висловлюємо невідомі змінні і цільову функцію через вільні змінні:
x 3 = 19-2 (6-1/3 x 6) -3 x 2 = 19-12 +2 / 3 x 6 -3 x 2 = 7 +2 / 3 x 6 -3 x 2
x 4 = 13-2 (6-1/3 x 6) - x 2 = 1 +2 / 3 x 6 - x 2
x 5 = x 5 = 15
F (x 2; x 6) = 42-7/3 x 6 +5 x 2
При цьому опорному плані (6; 0; 7; 1; 15; 0) x 2 Переклад з вільних в базисні змінні:
x 2 = min {∞; 7 / 3, 1 / 11; 15 / 3} = 1
Висловлюємо x 2 через x 4
x 2 = 1 +2 / 3 x 6 - x 4
Висловлюємо невідомі змінні і цільову функцію через вільні змінні:
x 3 = 7 +2 / 3 x 6 -3 (1 +2 / 3x 6-x 4) = 7 +2 / 3 x 6-3-2x 6 +3 x 4 = 4-4/3x 6 +3 x 4
x 5 = 12-2x 6 +3 x 4 -
F = 42-7/3 x 6 +5 (1 +2 / 3x 2 - x 4) = 47-7/3x 6 +10 / 3x 6-5x 4 = 47 + x 6 -5 x 4
x 6 позитивне, отже можна збільшувати
x 6 = min {18; ∞; 3; 6} = 1
x 4 = 4/3-4/9 x 6 - 1 / 3 x 3
F = 47 + x 6 -5 (4/3-4/9-1/3 x 3)
В цільової функції всі коефіцієнти при змінних негативні, значення функції збільшувати не можна, аналогічно перетворюємо інші змінні, знаходимо опорний план, з якого визначаємо x 1, x 2.
Теорема 2:
Перетин замкнутих множин, безліч нетривіальних обмежень.
Безліч рішень системи лінійних нестрогих нерівностей та рівнянь є замкнутим.
α X = (α x 1, x 2, ..., α x n)
X + Y = (x 1 + y 1, x 2 + y 2, ... x n + y n)
Лінійні координати X 1, X 2, ... X n називається точка P = λ 1 x 1 + λ 2 x 2 + ... + λ k x k
Теорема 3:
Безліч P = {λ 1 x 1 + λ 2 x 2 + ... + λ k x k} 0 ≤ h i ≤ 1 для i = 1, ... k n å R i = 1, 1 ≤ i ≤ k опукла лінійна комбінація точок x 1, x 2, ... x n. Якщо k = 2, то це множина називається відрізком. X 1, X 2 - кінці відрізка. Кутовий точкою замкнутого безлічі називається точка, яка не є нетривіальною лінійної комбінацією точок безлічі (кутова точка).
Нетривіальність означає, що хоча б одна з λ відрізняється від 0 або 1.
Теорема 4:
Будь опорне рішення задачі лінійного програмування є кутовий точкою області допустимих рішень.
Теорема 5:
Якщо задача лінійного програмування має єдине рішення, то воно лежить серед кутових точок ОДР. А якщо рішення не одне, то серед рішень є декілька кутових, таких що безліч всіх рішень є їх опуклої лінійної комбінацією.
Симплекс метод полягає в тому, що спочатку знаходиться деякий опорне рішення задачі (первинний опорний план), а потім, цілеспрямовано переходячи від одного опорного плану до іншого, шукається оптимальний план. Якщо таких кілька, то знаходяться всі кутові, а безліч рішень представляється як їх лінійна комбінація.
Перехід до нового опорного плану
F 1 = F (x 1); F 2 = F (x 2) F 2 - F 1 =- υ k Δ k = F 2 можна довести, де υ k розглянутий вище мінімум, який визначається при введенні k - ої змінної в базис, а Δ k = å з j x j (1)-С k, де n ≤ j ≤ 1, X 1 = (x 1 (1); x 2 (1); ... x n (1)) - оцінка k - ої змінної, тому якщо вирішується завдання на максимум, то величина Δ F 2 позитивних повинна бути, Δ k - негативна. При вирішенні задач на мінімум Δ F 2-негативна, Δ k - позитивна. Ці величини обчислюються і якщо серед Δ F 2 всі значення не позитивні, то при вирішенні задач на мінімум навпаки. Якщо при вирішенні на максимум серед Δ F 2 кілька позитивних, то вводимо в базис той вектор, при якому ця величина досягає максимум, а якщо завдання вирішується на мінімум і серед Δ F 2 кілька негативних, то в число базисних включається вектор з найменшим значенням Δ F 2, тобто з найбільшим за абсолютною величиною. При виконанні цих умов гарантується найбільш можливу зміну значення функції.
Рішення завдання буде єдиним, якщо для будь-яких векторів x k не входять в базис, оцінки Δ k ≠ 0, якщо хоча б одна з таких Δ k = 0, то рішення не є єдиним, для знаходження іншого рішення переходимо до іншого опорному плану, включаючи в базис x k, де Δ k = 0. Перебір всі такі опорні рішень складають їх в лінійну комбінацію, яка і буде рішенням завдання.
Якщо для будь-якого деякого Δ k суперечать умові оптимальності коефіцієнти при змінної x k ≤ 0, то система обмежень не обмежена, тобто оптимального плану не існує.
Двоїста задача
Двоїста задача (ДЗ) - це допоміжна задача лінійного програмування, що формулюється за допомогою певних правил безпосередньо з умов прямої задачі. Зацікавленість у визначенні оптимального рішення прямої задачі шляхом вирішення двоїстої до неї завдання обумовлена тим, що обчислення при вирішенні ДЗ можуть виявитися менш складними, ніж за прямої задачі (ПЗ). Трудомісткість обчислень при вирішенні ЗЛП більшою мірою залежить від числа обмежень, а не від кількості змінних. Для переходу до ДЗ необхідно, щоб ПЗ була записана в стандартній канонічної формі. При поданні ПЗ в стандартній формі до складу змінних x j включаються також надлишкові і залишкові змінні.
Двоїста задача має:
m змінних, які відповідають числу обмежень прямої задачі;
n обмежень, відповідних числу змінних прямої задачі.
Двоїста задача виходить шляхом симетричного структурного перетворення умов прямої задачі за такими правилами:
Кожному обмеженню b i ПЗ відповідає мінлива y i ДЗ;
Кожній змінній x j ПЗ відповідає обмеження C j ДЗ;
Коефіцієнти при x j в обмеженнях ПЗ стають коефіцієнтами лівій частині відповідного обмеження ДЗ;
Коефіцієнти C j при x j в цільової функції ПЗ стають постійними правій частині обмеження ДЗ;
Постійні обмежень b i ПЗ стають коефіцієнтами цільової функції ДЗ.
Розглянемо наступні два завдання:
F = С 1 х 1 + С 2 х 2 + ... + С n x n → max
a 11 x 1 + a 22 x 2 + ... + A 1m x n ≤ b 1
a 21 x 1 + a 22 x 2 + ... + A 2m x n ≤ b 2
. . . . . . . . . . . . . . . . . . . . . . .
a m1 x 1 + a m2 x 2 + ... + A mn x n ≤ b m
x j ≥ 0 j = 1, ..., n
Z = b 1 х 1 + b 2 х 2 + ... + B n x n → min
a 11 y 1 + a 21 y 2 + ... + A m1 y 1 ≤ C 1
a 12 y 1 + a 22 y 2 + ... + a m 2 y 2 ≤ C 2
. . . . . . . . . . . . . . .. . . . . . . .
a 1 n y n + a 2 m y n + ... + A nm y n ≤ C n
y i ≥ 0 i = 1, ..., m
Теорема 1 (перша теорема подвійності)
Якщо вирішується мати одне рішення. З пари двоїстих задач не обов'язково симетричних, то має рішення (як наслідок отримує, що якщо одна задача має рішення, то не має рішення інша) при цьому значення цільових функцій на обох задачах збігаються.
Fmax = Zmin
Теорема 2 (друга теорема подвійності)
Якщо (5) і (6) пара симетричних двоїстих задач, то (x 0 1, x 0 2, ..., x 0 n) і (y 0 1, y 0 2, ..., y 0 n) є їх оптимальними рішеннями, то компоненти оптимальних рішень задовольняються системі.
x 1 0 (a 11 y 1 0 + a 21 y 2 0 + ... + a m1 y n 0-c 1) = 0
x 2 0 (a 12 y 1 0 + a 22 y 2 0 + ... + a m2 y n 0-c 2) = 0
. . . . . . . . . . . . . . . . . . . . . . . . . . .
x n 0 (a 1n y 1 0 + a 2m y 2 0 + ... + a m1 y n 0-c 1) = 0
y 1 0 (a 11 x 0 1 + a 22 x 0 2 +...+ a 1m x 0 n-b 1) = 0
y 2 0 (a 21 x 0 1 + a 22 x 0 2 + ... + a 2m x 0 n-b 2) = 0
. . . . . . . . . . . . . . . . . . . . . . . . . . .
y n 0 (a m1 x 0 1 + a m2 x 0 2 +...+ a mn x 0 n-b m) = 0
Висновок
У цій роботі було закладено основи математичних методів вирішення завдань лінійного програмування. Тому більшу увагу приділялася наступних розділів:
Основи математичних методів та їх застосування;
Рішення задач за допомогою симплекс - методу.