Рішення задачі лінійного програмування симплекс методом

Державна освітня установа вищої
професійної освіти
"Московський державний технічний університет ім. Н. Е. Баумана"
Калузький філія
Реферат
"Рішення задачі лінійного програмування симплекс-методом"
2008
Мета роботи: вивчити і навчитися застосовувати на практиці симплекс - метод для вирішення прямої і двоїстої задачі лінійного програмування
Теоретична частина.
Математична постановка задачі лінійного програмування.
З практики розгляду завдань математичного програмування випливає, що в загальному вигляді вирішити їх практично неможливо. Доцільно розглядати окремі класи (види) завдань. Для кожного такого класу вдається сформулювати алгоритм рішення, прийнятний тільки для даного класу задач. Найбільш розробленими в математичному програмуванні є завдання лінійного програмування (ЛП).
У задачах лінійного програмування цільова функція лінійна, а умови-обмеження містять лінійні рівності та лінійні нерівності. Змінні можуть бути підпорядковані або не підпорядковані вимогу неотрицательности. Одна і та ж задача лінійного програмування може бути записана в різній формі. Якщо всі обмеження мають вигляд нерівностей, то завдання записана в стандартній формі. Якщо всі її обмеження, крім

представляють собою рівності, то завдання лінійного програмування записана в канонічній формі.

Загальний вигляд задачі лінійного програмування

,
Обмеження:
1. Праві частини всіх обмежень повинні бути невід'ємними . Якщо який-небудь з коефіцієнтів <0, то необхідно коефіцієнти обмеження ліворуч і праворуч помножити на "-1" і змінити знак даного обмеження на протилежний;
2. Всі обмеження мають бути представлені у вигляді рівностей, тому при переході від нерівності до рівності використовують апарат додаткових змінних.
Якщо вихідні обмеження визначають витрата деякого ресурсу (знак " "), То змінні слід інтерпретувати як залишок, або невикористану частину ресурсу. У цьому випадку - Залишкова змінна і вводиться в рівняння зі знаком "+".
Якщо вихідні обмеження визначають надлишок деякого ресурсу (знак " "), То вводиться надлишкова мінлива знаком "-".
Змінні:
Всі змінні повинні бути невід'ємними, тобто .
Якщо змінна не має обмеження в знаку, то її потрібно представити як різниця двох невід'ємних змінних: , Де . Таку підстановку варто використовувати у всіх обмеженнях, що містять цю змінну, а також у вираженні для цільової функції.
Якщо така мінлива потрапляє в оптимальне рішення, то
.
Цільова функція:
Підлягає максимізації або мінімізації.
Система обмежень у вигляді рівностей та нерівностей утворює опукле безліч - опуклий багатогранник. Це множина може бути обмеженим і необмеженим. Цільова функція задачі лінійного програмування також є опуклою функцією. Таким чином, задача лінійного програмування є окремим випадком завдання опуклого програмування.
Розглянемо систему обмежень задачі лінійного програмування у вигляді рівностей
(1)
Система (1) лінійних рівнянь сумісна, якщо вона має, принаймні, одне рішення. Система (1) називається надмірною, якщо одне з рівнянь можна виразити у вигляді лінійної комбінації інших.
У системі (1) число змінних (невідомих n більше, ніж число обмежень m. Будемо вважати, що ранг цієї системи дорівнює m (система ненадлишковим) і що система (1) совместна. Тоді m змінних із загального їх числа утворюють базисні змінні, а інші змінних називають небазисних. Якщо система рівнянь має рішення, то вона має і базисне рішення. Рішення системи рівнянь (1) називають допустимим, якщо всі його компоненти ненегативні. Якщо система лінійних рівнянь має допустимим рішенням, то вона має і базисне допустиме рішення. Сукупність усіх допустимих рішень системи (1) є опукле безліч, тобто безліч рішень задачі лінійного програмування опукло. Так як це безліч утворено площинами (гіперплощинами), то воно має вигляд опуклого многогранника. Базисне допустиме рішення відповідає крайній точці опуклого багатогранника (його грані або вершині). Якщо існує оптимальне рішення задачі лінійного програмування, то існує базисне оптимальне рішення.
Цільова функція задачі лінійного програмування є рівняння площини (або гіперплощини для числа змінних більше трьох). Максимальне або мінімальне значення цільова функція задачі лінійного програмування досягає або у вершині опуклого багатогранника, або на одній з його граней. Таким чином, рішення (рішення) задачі лінійного програмування лежить у вершинах опуклого багатогранника і для його знаходження треба обчислити значення цільової функції в вершинах випуклого многогранника, що визначається умовами-обмеженнями завдання.
Рішення задачі лінійного програмування графічним методом.
Труднощі побудови математичної моделі полягає в ідентифікації змінних і наступному поданні мети і обмежень у вигляді математичних функцій цих змінних. Якщо модель містить тільки дві змінні, то завдання лінійного програмування можна вирішити графічно. У випадку трьох змінних графічний розв'язок стає менш наочним, а при більшому значенні змінних - навіть неможливим. Однак графічне рішення дозволяє зробити висновки, які служать основою для розробки загального методу розв'язання задачі лінійного програмування.
Перший крок при використанні графічного методу полягає в геометричному представленні допустимих рішень, тобто побудові області припустимих рішень (ОДР.), в якій одночасно задовольняються всі обмеження моделі. При отриманні графічного рішення мінлива відкладається по горизонтальній осі, а - По вертикальній. При формуванні ОДР необхідно запобігти отримання неприпустимих рішень, які пов'язані з необхідністю виконання умови невід'ємності змінних. Перед побудовою необхідно визначити квадранти, в яких буде розташовуватися ОДР. Квадранти визначаються знаками змінних і . Умови невід'ємності змінних і обмежують область їх допустимих значень першим квадрантом. Якщо змінна не обмежена в знаку, то область обмежується першим і другим квадрантом, якщо , То - першим і четвертим квадрантом. Інші межі простору рішень на площині , зображені прямими лініями, побудованими по рівняннях обмежень за умови заміни знака на знак "=". При цьому необхідно враховувати наступне: праві частини всіх обмежень повинні бути невід'ємними . Якщо будь-яке обмеження <0, то необхідно коефіцієнти відповідного обмеження ліворуч і праворуч до-множити на "-1" і змінити знак нерівності даного обмеження на протилежний. Області, в яких виконуються відповідні обмеження у вигляді нерівностей, вказуються стрілками, спрямованими убік допустимих значень змінних.
У результаті побудов виходить багатокутник, який визначає простір рішень. Якщо одне з обмежень має знак "=", то ОДР вироджується у відрізок.
У кожній точці, що належить області або межах багатокутника рішень, всі обмеження виконуються, тому всі рішення, що відповідають цим точкам, є допустимими. Простір рішень містить нескінченне число таких точок, незважаючи на це, можна знайти оптимальне рішення. Для цього необхідно побудувати у площині змінних , градієнт цільової функції. Визначення оптимальної точки залежить від того завдання, яке необхідно вирішити.
Якщо в цільовій функції визначено завдання максимізації, то оптимальна точка буде розташовуватися в напрямку збільшення градієнта, якщо завдання мінімізації - то в напрямку зменшення градієнта цільової функції. Для визначення оптимальної точки будемо переміщувати цільову функцію у напрямку збільшення (зменшення) градієнта до тих пір, поки вона не зміститися в область неприпустимих рішень.
Після знаходження оптимальної точки простору рішень визначають її координати , і значення цільової функції в ній. Правильність вибору оптимальної точки можна перевірити розрахунком цільової функції у вершинах многогранника рішень. У ЗЛП область допустимих рішень завжди є опуклою множиною, тобто таким безліччю, що поряд з будь-якими двома точками, що належать цій безлічі, цьому ж безлічі належить і відрізок, що з'єднує ці дві точки. Будь-яка функція порад задля чином збільшується в напрямку свого градієнта.
Рішення задачі лінійного програмування симплекс-методом.
Пряма задача.
Розглянемо задачу лінійного програмування у канонічній формі:
Знайти максимум (мінімум) функції за умов

Передбачається, що рішення цього завдання існує. Щоб знайти оптимальне рішення, треба знайти допустимі базисні рішення, а з них вибрати оптимальне базисне рішення.
Симплекс - метод - це алгебраїчний метод розв'язання задач лінійного програмування. У процесі обчислень проводитися послідовний обхід вершин багатогранника рішень (ОДР.) з перевіркою в кожній вершині умов оптимальності. При цьому кожен перехід в суміжну вершину супроводжується поліпшенням цільової функції.
Обчислювальні процедури симплекс - методу.
При графічному методі розв'язання ЗЛП оптимального рішення відповідає завжди одна з кутових (екстремальних) точок простору рішень. Це результат покладений в основу побудови симплекс-методу. Симплекс-метод не має наочністю геометричного представлення простору рішень.
Симплекс-метод реалізує упорядкований процес, у якому, починаючи із певною вихідної припустимою кутовий точки, здійснюються послідовні переходи від однієї припустимою екстремальній точки в іншу, поки не буде знайдена точка оптимального рішення.
Позначимо: - Загальна кількість змінних в ЗЛП, представленої в канонічній формі; - Кількість вихідних змінних; - Кількість обмежень, - Кількість додаткових змінних, тоді .
Кожна вершина багатогранника рішень має - Ненульових змінних і ( ) - Нульових змінних.
Ненульові змінні називаються базисними, нульові змінні - небазисних.
Доповнимо систему рівностей рівністю цільової функції, при цьому будемо вважати, що є базисної змінної, яка завжди присутня в базисі для будь-якої вершини.
Для отримання рішення складається початковий допустимий базис, в якому базисні змінні повинні бути представлені у вигляді одиничних орт. Це означає, що рівняння, що представляють дану вершину повинні включати кожну базисну змінну тільки в одному рядку з коефіцієнтом, рівним 1.
При виборі початкового допустимого базису для складання симплекс-таблиці-ці на першому кроці СТ (0) вихідні змінні прирівнюються до нуля і є небазисная, серед введених додаткових змінних вибираються змінні з коефіцієнтами рівними одиниці. Змінні в равенствах (2) - (4) є базисними і в - Рядок входять з коефіцієнтами, рівними 0. Для заповнення симплекс-таблиці необхідно цільову функцію перетворити до виду . Таким чином, остаточно отримуємо:
(1)
(2)
(3)
(4)
При складанні симплекс-таблиці дотримуються наступних правил:
в крайньому лівому стовпчику розташовуються базисні змінні і ;
в крайньому правому стовпчику розташовуються праві частини обмежень;
в першому рядку розташовуються змінні в певному порядку:
спочатку , Потім небазисних змінні, базисні змінні розташовуються в останніх стовпцях перед правою частиною (ПЧ). Запишемо коефіцієнти в СТ (0):

							ПЧ
	1	-	-	0	0	0	0
	0			1	0	0
	0			0	1	0
	0			0	0	1

Оптимальність кожної з вершин визначається коефіцієнтами при небазисних змінних в - Рядку поточної симплекс-таблиці:
Для задачі максимізації дана вершина є оптимальною, коли всі коефіцієнти при небазисних змінних в - Рядку є невід'ємними (> 0);
Для задачі мінімізації дана вершина є оптимальною, коли всі коефіцієнти при небазисних змінних в - Рядку є недодатні (<0).
Якщо в задачі максимізації (мінімізації) в однієї небазисной змінної в - Рядку коефіцієнт <0 (> 0), то поточна точка не є оптимальною і необхідно змінити базис. Для цього вибирають небазисную змінну, що має максимально негативний (позитивний) коефіцієнт у - Рядку. Обрана небазисная змінна буде включатися в новий базис, тому називається включається змінної. Базисна змінна, яка буде виведена з базису, називається исключаемой змінної.
Исключаемой зміною буде та базисна змінна, яка першою звернеться до "0" при переході в суміжну вершину після введення включається змінної.
Стовпець включається змінної будемо називати дозволяючим Столц.
Рядок исключаемой змінної будемо називати роздільної рядком.
Перетин дозволяє стовпця і рядка визначають дозволяє елемент (РЕ).
Щоб визначити исключаемую змінну необхідно:
розділити праві частини всіх базисних змінних (крім - Рядки) на відповідні позитивні коефіцієнти дозволяє стовпця;
вибрати з отриманих відносин найменше.
Ділити на "0" і негативну величину можна, тому що це призводить до відсутності пересічної вершини або до вершини поза ОДР.
Для переходу в суміжну вершину необхідно сформувати матрицю переходу B (0), яка визначить зв'язок між СТ (0) і СТ (1): СТ (1) = У (0) СТ (0).
Для довільної квадратної матриці розмірності n, що має в якості (n - 1) стовпця одиничні орти, розташовані у відповідності з одиничними ортами одиничної матриці, і одного довільного стовпця з ненульовим елементом на головній діагоналі, зворотна матриця знаходиться за наступним правилом:

Кожен елемент j - стовпця ділиться на РЕ і змінює знак на протилежний, крім дозволяє елемента.
Штучний початковий базис. М - метод.
Якщо вихідне обмеження записано у вигляді рівності "=" або має знак " ", То не можна відразу отримати допустимий початкове базисне рішення, тому що при запису задачі в стандартній формі, після введення додаткових змінних може вийти варіант, коли отримані рівняння не дозволяють сформувати початковий допустимий базис у вигляді одиничних орт.
У цьому випадку для знаходження початкового допустимого базису вводяться додатково штучні змінні . Штучні змінні не мають відношення до змісту поставленого завдання, їх введення допустимо тільки в тому випадку, якщо відповідна схема обчислень буде забезпечувати отримання оптимального рішення, в якому всі штучні змінні виявляться рівними нулю.
Змінні R визначають початковий допустимий базис з точки зору можливого подальшого переходу в одну з вершин ОДР. За використання штучних змінних в цільовій функції вводиться штраф М. У задачі максимізації М негативне (М <<0), в задачі мінімізації М позитивне (М>> 0).

Властивість М: При додаванні (вирахуванні) з будь-якої кінцевої величиною , Визначальною будь-яке значення, яке може приймати кожна з змінних вихідної ЗЛП, її значення (змінної М) не змінюється, а саме,

При складанні початкової симплекс-таблиці всі змінні початкового допустимого базису (додаткові і штучні) повинні розташовуватися в останніх m стовпцях перед правою частиною.
Алгоритм отримання оптимального рішення:
1. Перехід від нерівностей до равенствам з урахуванням правил переходу - введення залишкових, надлишкових, штучних змінних і коефіцієнтів штрафу;
2. Визначення числа базисних і небазисних змінних;
3. Отримання - Рядки для заповнення СТ (0. Для цього необхідно цільову функцію перетворити до виду ; Для чого з відповідних рівностей обмежень висловити штучні змінні і підставити в рядок і привести до раціонального увазі;
4. Заповнення СТ (0). Перенесення коефіцієнтів - Рядки і рівностей обмежень у відповідні рядки і стовпці симплекс-таблиці;
5. Дослідження функції на умову оптимальності:
визначення дозволяє стовпця (за знаком і величиною коефіцієнтів небазисних змінних - Рядки);
визначення включається змінної з небазисних змінних;
6. Визначення роздільної рядка за умовою допустимості:
визначення мінімального відношення при розподілі правих частин обмежень на позитивні коефіцієнти дозволяє стовпця;
визначення исключаемой змінної з початкового базису;
7. Визначення дозволяє елемента РЕ;
8. Отримання B (0). Заміна в матриці початкового базису коефіцієнтів исключаемой змінної на коефіцієнти включається змінної; обчислення B (0) за відповідним правилом;
9. Визначення елементів СТ (1) = У (0) СТ (0);
10. Дослідження -Строки СТ (1) на умова оптимальності.
Якщо умова не виконана, то обчислення тривають і необхідно повторити пункти 5-10.
Якщо умова оптимальності виконано, то рішення ЗЛП симплекс-методом закінчено, необхідно виділити оптимальні значення змінних і оптимальне значення цільової функції.
Рішення задачі лінійного програмування симплекс-методом.
Двоїста задача.
Двоїста задача (ДЗ) - це допоміжна задача лінійного програмування, формулируемая за допомогою певних правил безпосередньо з умов прямої задачі. Зацікавленість у визначенні оптимального розв'язання прямої задачі шляхом рішення двоїстої до неї завдання обумовлена ​​тим, що обчислення при вирішенні ДЗ можуть виявитися менш складними, ніж при ПЗ. Трудомісткість обчислень при вирішенні ЗЛП більшою мірою залежить від числа обмежень, а не від кількості змінних. Для переходу до ДЗ необхідно, щоб пряма задача була записана в стандартній канонічній формі. При поданні ПЗ в стандартній формі до складу змінних включаються також надлишкові і залишкові змінні.
Двоїста задача має:
m змінних, відповідних числу обмежень прямої задачі;
n обмежень, відповідних числу змінних прямої задачі.
Двоїста задача виходить шляхом симетричного структурного перетворення умов прямої задачі за такими правилами:
Кожному обмеженню ПЗ відповідає мінлива ДЗ;
Кожній змінній ПЗ відповідає обмеження ДЗ;
Коефіцієнти при в обмеженнях ПЗ стають коефіцієнтами лівій частині відповідного обмеження ДЗ;
Коефіцієнти при в цільовій функції ПЗ стають постійними правій частині обмеження ДЗ;
Постійні обмежень ПЗ стають коефіцієнтами цільової функції ДЗ.
Розглянемо правила складання двоїстої задачі:
Пряма задачаДвойственная завдання


Зупинимося докладніше на визначенні областей допустимих рішень двоїстих змінних при переході від прямої задачі до двоїстої.

Області допустимих рішень для двоїстих змінних

Вид обмежень прямої задачі, а також додаткові і штучні змінні, що утворюють початковий допустимий базис, визначають ОДР для відповідних двоїстих змінних.
1. Розглянемо обмеження (2) прямої задачі:
Область допустимих рішень ДП ( ) Визначається знаками обмежень (8) і (9) двоїстої задачі і знаком обмеження (2) прямої задачі. Для визначення ОДР знайдемо обмеження ДЗ, відповідні залишковим змінним ПЗ. Коефіцієнти цільової функції для залишкових змінних дорівнюють нулю ( ). Т. о., при вирішенні завдання максимізації обмеженням прямої задачі, які мають знак обмеження , Відповідають невід'ємні двоїсті змінні: .
2. Розглянемо обмеження (3) прямої задачі:
.
При введенні штучних змінних в цільову функцію вводяться коефіцієнти штрафу М, тому для задачі максимізації отримаємо:
.
Т. о., При вирішенні завдання максимізації обмеженням прямої задачі, які мають знак рівності, відповідають двоїсті змінні, не обмежені в знаку .
3. Розглянемо обмеження (4) прямої задачі:

У цільовій функції надлишкові змінні мають коефіцієнти, рівні нулю ( ), А штучні змінні коефіцієнти, рівні величині штрафу зі своїм знаком, в результаті для задачі максимізації отримаємо:

Т. о., При вирішенні завдання максимізації обмеженням прямої задачі, які мають знак , Відповідають недодатні двоїсті змінні .
4. Якщо в прямій задачі є змінна, необмежена в знаку, то в двоїстої задачі вийдуть два обмеження, які мають однакові коефіцієнти при двоїстих змінних, але різні знаки обмежень. Для зручності рішення ці обмеження згортають в одне зі знаком рівності (тим самим число обмежень двоїстої задачі зводиться до числа вихідних змінних прямої задачі).
За аналогією можна записати умови двоїстої задачі при рішенні задачі мінімізації. Для зручності користування деякі співвідношення при переході від прямої задачі до двоїстої наведені в таблиці.

Пряма задача		Двоїста задача
Цільова функція	Обмеження	Цільова функція	Обмеження	Змінні
Максимізація		Мінімізація
	=
Мінімізація		Максимізація
	=

У двоїстої задачі змінні можуть бути невід'ємними ( ), Не обмеженими в знаку ( ), Недодатні ( ). При вирішенні ДЗ, як і ПЗ повинні виконуватися умови неотрицательности обмежень і змінних. Для представлення двоїстої задачі в стандартній формі використовуються наступні заміни:
якщо змінна не обмежена в знаку, то ;
якщо , То .
Такі підстановки слід використовувати у всіх обмеженнях, що містять ці змінні, а також у вираженні для цільової функції.
Після приведення ДЗ до стандартного вигляду використовується симплекс - метод. Алгоритм отримання рішення той же, що і для прямої задачі.
II. Практична частина
1. Рішення задачі лінійного програмування графічним методом.
Дана наступне завдання лінійного програмування (ЗЛП).




,
1.1. Всі обмеження завдання .
1.2. Мінлива обмежена в знаку, тому . Мінлива не обмежена в знаку, тому вводимо заміну , Де .
Область допустимих рішень буде обмежуватися I і IV квадрантом.
1.3. Побудова обмежень і градієнта цільової функції :
1.4. Область допустимих рішень - відрізок AB.
1.5. Точка А - оптимальна. Координати т. А:
; ; .
2. Рішення задачі лінійного програмування симплекс-методом.
Пряма задача.
Задачу лінійного програмування для будь-якої вершини в компактній формі можна представити у вигляді:
Для отримання використовуємо алгоритм, наведений в теоретичній частині.
1. Перехід від нерівностей до равенствам за правилами введення додаткових змінних. Вихідну завдання необхідно привести до стандартної форми: введемо заміну по змінній , і додаткові змінні:



,
Отриманий вид ЗЛП не дозволяє сформувати початковий допустимий базис, тому що не можна виділити одиничні орти в другому і третьому равенствах. Для отримання початкового допустимого базису введемо штучні змінні. У результаті отримаємо:



,
2. Загальне число змінних визначимо за формулою: = 3 +2 +2 = 7, де - Число штучних змінних. Число базисних змінних визначається числом обмежень, т. к. , То система має три базисні змінні і небазисних змінні .
3. Отримання - Рядки для СТ (0). Наведемо цільову функцію до виду
.
Отримаємо з (2): , З (3):

4. Формування симплекс - таблиці на першому кроці:
Початковий базис
СТ (0) РС
5. Визначення дозволяє стовпця.
При вирішенні завдання максимізації вибираємо в - Рядку максимально негативний коефіцієнт: - Включається змінна.
6. Визначення роздільної рядки: - Исключаемая змінна.
7. Дозволяє елемент РЕ = 1.
8. Отримання матриці переходу
, Де В (0) - матриця переходу
9. Визначення елементів таблиці СТ (1) = У (0) СТ (0);
10. Дослідження z-рядки СТ (1) на умова оптимальності:
СТ (1)

СТ (2)

СТ (2) - оптимальна, тому що коефіцієнти при НБП .
, , .
3. Рішення задачі лінійного програмування симплекс-методом.
Двоїста задача.
Складемо двоїсту задачу за умовами прямої задачі і визначимо області допустимих рішень ДП:
Пряма задачаДвойственная завдання




(1)
(2)



Отже, отримано: , , .
2. Наведемо запис двоїстої задачі до канонічної форми. На підставі отриманих ОДР двоїстих змінних введемо необхідні підстановки: .
Для зручності рішення звернемо обмеження (1) і (2) в одне зі знаком рівності, а також введемо в обмеження і цільову функцію надлишкові, залишкові і штучні змінні.

(3)
(4)
3. Вирішимо ДЗ симплекс методом:
З (3): висловимо
З (4) виразимо:

СТ (0)

СТ (1)

СТ (2)

	W								ПЧ
W	1	-40 / 7	0	0	0	-12 / 7	-7/3M +4	-M +12 / 7	48 / 7
	0	-1 / 7	1	-1	0	-1 / 7	1 / 3	1 / 7	4 / 7
	0	-10 / 7	0	0	1	4 / 7	-4 / 3	-3 / 7	5 / 7

СТ (2) - оптимальна, тому що коефіцієнти при
, ,

Завдання:
1. Вивчити методи розв'язання задачі лінійного програмування (графічний і симплекс-метод):
2. Для заданого варіанту отримати рішення задачі лінійного програмування:
- Графічним методом;
- Симплекс методом для прямої задачі;
- Симплекс методом для двоїстої задачі.