2

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Факультет інформаційних технологій і управління

Кафедра інформаційних технологій автоматизованих систем

ДИПЛОМНА РОБОТА

по дисципліні «Системний аналіз і дослідження операцій»

на тему: «Рішення оптимізаційної задачі

лінійного програмування»

Ужгород 2006

ЗМІСТ:

ВВЕДЕННЯ.............................................................................................................3

1. Постановка завдання оптимізації.....................................................................8

2. Побудова аналітичної моделі............................................................................9

3. Обґрунтування і опис обчислювальної процедури.......................................11

3.1. Приведення завдання лінійного програмування до стандартної форми……………………………………………………………………………..11

3.2. Основна ідея симлекс-методу................................................................12

3.3. Двохетапний симплекс-метод................................................................12

4. Рішення задачі оптимізації на основі симплекс-таблиць..............................14

4.1. Приведення завдання до стандартної форми.......................................14

4.2. Визначення початкового допустимого рішення..................................14

4.3. Побудова штучного базису....................................................................15

4.4. Перший етап двохетапного симплекс-метода......................................16

4.5. Другий етап двохетапного методу........................................................19

5. Аналіз моделі на чутливість.............................................................................22

5.1. Статус ресурсів........................................................................................22

5.2. Цінність ресурсів.....................................................................................22

5.3. Аналіз на чутливість до змін правих частин обмежень......................23

5.4. Аналіз на чутливість до змін коефіцієнтів цільовій функції..............25

6. Визначення оптимального цілочисельного рішення.....................................26

6.1. Метод Гоморі для частково цілочисельних завдань...................................26

ВИСНОВОК...........................................................................................................33

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ.......................................................34

УМОВНІ СКОРОЧЕННЯ.....................................................................................35

ДОДАТОК..............................................................................................................36

ВВЕДЕННЯ

В даний час оптимізація знаходить застосування в науці, техніці і в будь-якій іншій області людської діяльності.

Оптимізація - цілеспрямована діяльність, що полягає в отриманні якнайкращих результатів за відповідних умов.

Пошуки оптимальних рішень привели до створення спеціальних математичних методів і вже в 18 столітті були закладені математичні основи оптимізації (варіаційне числення, чисельні методи і др). Проте до другої половини 20 століть методи оптимізації в багатьох областях науки і техніки застосовувалися дуже рідко, оскільки практичне використання математичних методів оптимізації вимагало величезної обчислювальної роботи, яку без ЕОМ реалізувати було украй важко, а у ряді випадків - неможливо.

Постановка завдання оптимізації припускає існування конкуруючих властивостей процесу, наприклад:

кількість продукції - витрата сировини

кількість продукції - якість продукції

Вибір компромиcного варіанту для вказаних властивостей і є процедурою рішення оптимізаційної задачі.

При постановці завдання оптимізації необхідно:

1. Наявність об'єкту оптимізації і мети оптимізації. При цьому формулювання кожного завдання оптимізації повинне вимагати екстремального значення лише однієї величини, тобто одночасно системі не повинно приписуватися два і більш за критерії оптимізації, оскільки практично завжди екстремум одного критерію не відповідає екстремуму іншого. Приведемо приклади.

Типовий приклад неправильної постановки завдання оптимізації:

«Отримати максимальну продуктивність при мінімальній собівартості».

Помилка полягає в тому, що ставиться завдання пошуку оптимальності 2-х величин, що суперечать один одному за своєю суттю.

Правильна постановка завдання могла бути наступна:

а) отримати максимальну продуктивність при заданій собівартості;

б) отримати мінімальну собівартість при заданій продуктивності;

У першому випадку критерій оптимізації - продуктивність а в другому - собівартість.

2. Наявність ресурсів оптимізації, під якими розуміють можливість вибору значень деяких параметрів об'єкту, що оптимізується.

3. Можливість кількісної оцінки величини, що оптимізується, оскільки тільки в цьому випадку можна порівнювати ефекти від вибору тих або інших дій, що управляють.

4. Облік обмежень.

Величина, що зазвичай оптимізується, пов'язана з економічністю роботи даного об'єкту (апарат, цех, завод). Варіант роботи об'єкту, що оптимізується, повинен оцінюватися якоюсь кількісною мірою - критерієм оптимальності.

Критерієм оптимальності називається кількісна оцінка якості об'єкту, що оптимізується.

На підставі вибраного критерію оптимальності складається цільова функція, що є залежністю критерію оптимальності від параметрів, що впливають на її значення. Вид критерію оптимальності або цільової функції визначається конкретним завданням оптимізації.

Таким чином, завдання оптимізації зводиться до знаходження екстремуму цільової функції.

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

Лінійне програмування - один з перших і найбільш детально вивчених розділів математичного програмування. Саме лінійне програмування з'явилося тим розділом, з якого початку розвиватися сама дисципліна «математичне програмування». Термін «програмування» в назві дисципліни нічого спільного з терміном «програмування (тобто складання програм) для ЕОМ» не має, оскільки дисципліна «лінійне програмування» виникла ще до того часу, коли ЕОМ стали широко застосовуватися при рішенні математичних, інженерних, економічних і ін. завдань. Термін «лінійне програмування» виник в результаті неточного перекладу англійського «linear programming». Одне із значень слова «programming» - складання планів, планування. Отже, правильним перекладом «Linear programming» було б не «лінійне програмування», а «лінійне планування», що точніше відображає зміст дисципліни. Проте, термін лінійне програмування, нелінійне програмування і т.д. в наший літературі стали загальноприйнятими.

Отже, лінійне програмування виникло після Другої Світової Війни і став швидко розвиватися, привертаючи увагу математиків, економістів і інженерів завдяки можливості широкого практичного застосування, а так само математичній «стрункості».

Можна сказати, що лінійне програмування застосовне для побудови математичних моделей тих процесів, в основу яких може бути покладена гіпотеза лінійного представлення реального миру: економічних завдань, завдань управління і планування, оптимального розміщення устаткування і ін.

Завданнями лінійного програмування називаються завдання, в яких лінійні як цільова функція, так і обмеження у вигляді рівності і нерівностей. Стисло завдання лінійного програмування можна сформулювати таким чином: знайти вектор значень змінних, що доставляють екстремум лінійної цільової функції при m обмеженнях у вигляді лінійної рівності або нерівностей.

Лінійне програмування є найбільш часто використовуваним методом оптимізації. До завдань лінійного програмування можна віднести завдання:

раціонального використання сировини і матеріалів; завдання оптимізації розкроу;

оптимізації виробничої програми підприємств;

оптимального розміщення і концентрації виробництва;

складання оптимального плану перевезень, роботи транспорту;

управління виробничими запасами;

і багато інших, що належать сфері оптимального планування.

Так, по оцінках американських експертів, близько 75% від загального числа вживаних оптимізаційних методів доводиться на лінійне програмування. Близько чверті машинного часу, витраченого останніми роками на проведення наукових досліджень, була відведена рішенню завдань лінійного програмування і їх численних модифікацій.

Перші постановки завдань лінійного програмування були сформульовані відомим радянським математиком Л.В. Канторовичем, якому за ці роботи була присуджена Нобелівська премія по економіці.

Значний розвиток теорія і алгоритмічний апарат лінійного програмування отримали з винаходом і розповсюдженням ЕОМ і формулюванням американським математиком Дж. Данцингом симплекс-метода.

В даний час лінійне програмування є одним з найбільш споживаних апаратів математичної теорії оптимального ухвалення рішення. Для вирішення завдань лінійного програмування розроблено складне програмное забезпечення, що дає можливість ефективно і надійно вирішувати практичні завдання великих об'ємів. Ці програми і системи забезпечені розвиненими системами підготовки початкових даних, засобами їх аналізу і представлення отриманих результатів.

У розвиток і вдосконалення цих систем вкладена праця і талант багатьох матеметиков, закумульований досвід рішення тисяч завдань. Володіння апаратом лінійного програмування необхідне кожному фахівцеві в області математичного програмування. Лінійне програмування тісно пов'язане з іншими методами математичного програмування (наприклад, нелінійного програмування, де цільова функція нелінійна).

Завдання з нелінійною цільовою функцією і лінійними обмеженнями називають завданнями нелінійного програмування з лінійними обмеженнями. Оптимізаційні завдання такого роду можна класифікувати на основі структурних особливостей нелінійних цільових функцій. Якщо цільова функція Е - квадратична функція, то ми маємо справу із завданням квадратичного програмування; якщо Е - це відношення лінійних функцій, то відповідне завдання носить назву завдання лінійного для дробу програмування, і т.д. Ділення оптимізаційних завдань на ці класи представляє значний інтерес, оскільки специфічні особливості тих або інших завдань грають важливу роль при розробці методів їх рішення.

Сучасні методи лінійного програмування досить надійно вирішують завдання загального вигляду з декількома тисячами обмежень і десятками тисяч змінних. Для вирішення надвеликих завдань використовуються вже, як правило, спеціалізовані методи.

1. ПОСТАНОВКА ЗАВДАННЯ ОПТИМІЗАЦІЇ

Варіант 80.

У цеху є токарний верстат і верстат-автомат. Цех випускає деталі 1,2 і 3 в комплекті: на кожну деталь 1 - по 2 деталі 2 і 3. Годинна продуктивність верстатів по кожній з деталей приведена в таблиці:

Верстати	Деталі
	1	2	3
1.Токарний	5	5	10
2.Автомат	15	15	10

Таблиця 1. Годинна продуктивність верстатів

Скласти програму роботи верстатів, при якій протягом зміни (8 годин) випускатиметься максимальна кількість комплектів деталей.

2. ПОБУДОВА АНАЛІТИЧНОЇ МОДЕЛІ

Складемо аналітичну модель завдання. Для цього спочатку введемо змінні, які потрібно визначити:

X1 - час, який працював токарний верстат над деталями типу 1 протягом робочої зміни;

X2 - час, який працював токарний верстат над деталями типу 2 протягом робочої зміни;

X3 - час, який працював токарний верстат над деталями типу 3 протягом робочої зміни;

X4 - час, який працював верстат-автомат над деталями типу 1 протягом робочої зміни;

X5 - час, який працював верстат-автомат над деталями типу 2 протягом робочої зміни;

X6 - час, який працював верстат-автомат над деталями типу 3 протягом робочої зміни.

Система обмежень складається з двох груп. Перша група встановлює, що кожен з верстатів може працювати не більше 8 годин в зміну.

Обмеження часу роботи токарного верстата:

X1 + X2 + X3 8;

Обмеження часу роботи верстата-автомата:

X4 + X5 + X6 8.

Друга група обмежень направлена на виконання вимоги про комплектацію деталей: на кожну деталь 1 повинно доводитися по 2 деталі 2 і 3. Але перед тим, як вводити це обмеження, визначимо, скільки деталей кожного типу у нас проводитиметься за зміну:

5X1 + 15X4 - буде проведено за зміну деталей типу 1;

5X2 + 15X5 - буде проведено за зміну деталей типу 2;

10X3 + 10X6 - буде проведено за зміну деталей типу 3.

Тепер введемо самі обмеження:

2(5X1 + 15X4)= 5X2 + 15X5;

2(5X1 + 15X4)= 10X3 + 10X6.

Очевидно, що всі змінні в завданні ненегативні (об'єм продукції не може бути негативним):

X1, X2, X3, X4, X5, X6 d 0.

Цільова функція в наший завданню повинна виражати кількість комплектів деталей, що випускаються за зміну, тому складемо всі деталі, що випускаються, і поділимо на 5 (у комплект, як уже згадувалося, входять 1 деталь типу 1 і по 2 деталі типу 2 і 3):

E= (5X1 + 15X4 + 5X2 + 15X5 + 10X3 + 10X6) /5 max

або, якщо спростити цей вираз, то отримаємо:

E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 max

Цільову функцію треба максимізувати.

Таким чином, формальна постановка завдання оптимізації має наступний вигляд:

X1 + X2 + X3 8;

X4 + X5 + X6 8;

2(5X1 + 15X4)= 5X2 + 15X5;

2(5X1 + 15X4)= 10X1 + 10X6;

X1, X2, X3, X4, X5, X6 d 0.

E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 max

3. ОБГРУНТУВАННЯ І ОПИС ОБЧИСЛЮВАЛЬНОЇ ПРОЦЕДУРИ

3.1. ПРИВЕДЕННЯ ЗАВДАННЯ ЛІНІЙНОГО ПРОГРАМУВАННЯ ДО СТАНДАРТНОЇ ФОРМИ

Будь-яке завдання лінійного програмування приводиться до стандартної (канонічною) форми основного завдання лінійного програмування, яке формулюється таким чином: знайти ненегативні значення змінних X1, X2, Xn, що задовольняють обмеженням у вигляді рівності:

A11X1 + A12X2 + . + A1nXn = B1;

A21X1 + A22X2 + . + A2nXn = B2;

Am1X1 + Am2X2 + . + AmnXn = Bm;

Xj d 0, j=1.,n

і що обертають в максимум лінійну функцію цих змінних:

E = C1X1 + C2X2 + . + CnXn max

При цьому також потрібний, щоб праві частини рівності були ненегативні, тобто повинні дотримуватися умови:

Bj G 0, j=1.,n

Приведення до стандартної форми необхідне, оскільки більшість методів рішення завдань лінійного програмування розроблена саме для стандартної форми. Для приведення до стандартної форми завдання лінійного програмування може потрібно виконати наступні дії:

- перейти від мінімізації цільової функції до її максимізації;

- змінити знаки правих частин обмежень;

- перейти від обмежень-нерівностей до рівності;

- позбавитися від змінних, що не мають обмежень на знак.

Для вирішення наший завдання скористаємося симплекс-методом, оскільки цей метод призначений для вирішення завдань лінійного програмування будь-якої розмірності.

3.2. ОСНОВНА ІДЕЯ СИМПЛЕКС-МЕТОДА

Екстремум цільової функції завжди досягається в кутових точках області допустимих рішень. Симплекс-метод, званий також методом послідовного поліпшення плану, реалізує перебір кутових точок області допустимих рішень у напрямі поліпшення значення цільової функції. Основна ідея цього методу наступна. Перш за все, знаходиться яке-небудь допустиме початкове (опорное) рішення, тобто яка-небудь кутова точка області допустимих рішень. Процедура методу дозволяє відповісти на питання, чи є це рішення оптимальним. Якщо "так", то завдання вирішене. Якщо "ні", то виконується перехід до суміжної кутової точки області допустимих рішень, де значення цільової функції поліпшується, тобто до негіршого допустимого рішення. Якщо деяка кутова крапка має декілька суміжних, то обчислювальна процедура методу забезпечує перехід до тієї з них, для якої поліпшення цільової функції буде найбільшим. Процес перебору кутових точок області допустимих рішень повторюється, поки не буде знайдена крапка, якою відповідає екстремум цільової функції Е.

При побудові початкового базису в заданому завданні використовувався метод штучного базису, тому знайдене рішення не є допустимим. В цьому випадку для вирішення завдання необхідно використовувати двохетапний симплекс-метод.

3.3. ДВОХЕТАПНИЙ СИМПЛЕКС-МЕТОД

Завдання за допомогою цього методу вирішується в два етапи: спочатку відшукується початкове допустиме рішення, що не містить штучних змінних, а потім на основі знайденого рішення шукається оптимальне рішення початкової задачі. Основні кроки, реалізації методу наступні.

1. Завдання лінійного програмування зводиться до стандартної форми.

2. Будується штучний базис.

3. Складається штучна цільова функція: сума всіх штучних змінних.

4. Реалізується перший етап двохетапного методу: за допомогою звичайних процедур симплекс-метода виконується мінімізація штучної цільової функції. Якщо її мінімальне значення рівне 0, то відповідне рішення є допустимим рішенням початкової задачі. Очевидно, що при нульовому значенні штучної цільової функції всі штучні змінні також нульові (оскільки штучна цільова функція - їх сума, і всі вони ненегативні). Якщо мінімальне значення штучної цільової функції виявляється відмінним від нуля, це означає, що завдання не має допустимих рішень.

5. Реалізується другий етап двохетапного методу: знайдене на кроці 4 допустиме рішення використовується як початкове рішення початкової задачі для пошуку її оптимального рішення.

4. РІШЕННЯ ЗАДАЧІ ОПТИМІЗАЦІЇ НА ОСНОВІ СИМПЛЕКС-ТАБЛИЦ

4.1. ПРИВЕДЕННЯ ЗАВДАННЯ ДО СТАНДАРТНОЇ ФОРМИ

Для приведення даного завдання до стандартної форми необхідно лише перейти від обмежень - нерівностей до рівності. Для цього введемо додаткові балансові ненегативні змінні. Також для спрощення подальших обчислень розділимо обидві частини обмежень на комплектацію деталей на 5:

X1 + X2 + X3 + X7 = 8;

X4 + X5 + X6 + X8 = 8;

2X1 - X2 + 6X4 - 3X5 = 0;

2X1 - 2X3 + 6X4 - 2X6 =0;

X1, X2, X3, X4, X5, X6, X7, X8 v 0.

E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 max

де Х7, Х8 - залишкові змінні.

Отже, наше початкове завдання ми привели до стандартної форми основного завдання лінійного програмування.

4.2. ВИЗНАЧЕННЯ ПОЧАТКОВОГО ДОПУСТИМОГО РІШЕННЯ

Для завдання, представленого в стандартній формі, кількість змінних звичайна більше, ніж кількість обмежень. Тому для знаходження початкового рішення задачі потрібно виразити m змінних (тобто кількість змінних, рівна кількості рівнянь) через решту n-m змінних, прийняти ці n-m змінних рівними нулю і, таким чином, знайти значення m змінних (у заданому завданні m=4 і n=8). Змінні, значення яких приймаються рівними нулю, називаються небазисними, а решта m змінних - базисними. Значення базисних змінних ненегативні (деякі з них можуть виявитися рівними нулю). Кількість базисних змінних завжди рівна кількості обмежень. Знайдене таким чином рішення називається початковим допустимим базисним рішенням. Воно відповідає всім обмеженням.

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

Отже, для знаходження початкового допустимого рішення необхідно, щоб в кожне з рівнянь входила змінна з коефіцієнтом 1 і не входила в інші рівняння (базисна змінна). У нашому випадку ми маємо тільки 2 базисних змінної (X7 і X8), не вистачає ще двох базисних змінних. Їх можна створити за допомогою спеціального способу, який називається побудовою штучного базису.

4.3. ПОБУДОВА ШТУЧНОГО БАЗИСУ

Методи штучного базису призначені для побудови початкового базису (тобто для отримання початкового рішення) у випадках, коли його побудова безпосередньо на основі стандартної форми неможлива. При використанні штучного базису початкове рішення виявляється неприпустимим; від нього по певних алгоритмах виконується перехід до початкового допустимого рішення.

Для того, щоб побудувати штучний базис, необхідно в кожне рівняння стандартної форми, що не містить базисних змінних (тобто отримане з обмеження-рівності або "не менше"), додати по одній штучній змінній. У нашому випадку це:

2X1 - X2 + 6X4 - 3X5 + Х9 = 0;

2X1 - 2X3 + 6X4 - 2X6 + Х10 =0.

де Х9 і Х10 - штучні змінні, що не мають ніякого фізичного сенсу, причому Х9, Х10 d0.

Після побудови штучного базису, надавши нульові значення всім змінним, окрім базисних, отримаємо початковий базис: Х7, Х8, Х9, Х10 . Всього в базисі є чотири змінні і їх значення рівні правим частинам обмежень, т.е.:

Х7 = 8;

Х8 = 8;

Х9 = 0;

Х10 = 0.

Тепер необхідно вирішити цю задачу, тобто знайти оптимальне допустиме рішення. Для цього скористаємося двохетапним симплекс-методом.

4.4. ПЕРШИЙ ЕТАП ДВОХЕТАПНОГО СИМПЛЕКС-МЕТОДА

Отже, на першому етапі двохетапного методу відшукується початкове допустиме рішення. Для цього виконаємо наступні дії:

Будуємо штучну цільову функцію - суму всіх штучних

змінних:

W = X9 + X10 min

Оскільки цільова функція повинна бути виражена тільки через небазисних

змінні, то виражаємо штучні змінні X9 і X10 через небазисні змінні, а потім, спростивши отриманий вираз, переписуємо штучну цільову функцію:

X9 = - 2X1 + X2 - 6X4 + 3X5;

X10 = - 2X1 + 2X3 - 6X4 + 2X6.

W = - 4X1 + X2 + 2X3 - 12X4 + 3X5 + 2X6 min

Для приведення до стандартної форми направимо штучну цільову

функцію на максимум, для цього помножимо обидві її частини на -1:

-W = 4X1 - X2 - 2X3 + 12X4 - 3X5 - 2X6 max

Визначаємо початкове, неприпустиме рішення. Базис складається з чотирьох

змінних, з них дві штучні, остальные дві - залишкові. Базисні змінні приймають значення, рівні обмеженням завдання. Решту змінних вважаємо рівними нулю. В цьому випадку цільова функція Е приймає значення 0, штучна цільова функція - W також приймає значення 0.

Складаємо результатну симплекс-таблицю:

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	БР
E	-1	-1	-2	-3	-3	-2	0	0	0	0	0
-W	-4	1	2	-12	3	2	0	0	0	0	0
X7	1	1	1	0	0	0	1	0	0	0	8
X8	0	0	0	1	1	1	0	1	0	0	8
X9	2	-1	0	6	-3	0	0	0	1	0	0
X10	2	0	-2	6	0	-2	0	0	0	1	0

Таблиця 2. Симплекс-таблиця №1.

Отже, в першому стовпці таблиці вказані базисні змінні, в останньому стовпці - їх значення, а так само значення цільовою і штучною цільовою функцій. У заголовку таблиці перераховуються всі використовувані змінні. У рядках таблиці указуються коефіцієнти обмежень завдання.

Реалізуємо перший етап двохетапного методу: за допомогою процедур симплекс-методу виконуємо максимізацію функції -W. При цьому змінні, що включаються в базис, вибираються по W-рядку (тобто на кожному циклі в базис включається змінна, якою відповідає максимальний по модулю негативний елемент в W-рядку; стовпець, відповідний цією змінною, стає таким, що веде). У нашому випадку це стовпець X4, оскільки коефіцієнт при цій змінній в W-рядку рівний -12. Провідний рядок визначаємо таким чином: розраховуємо так звані сімплексні відносини, тобто відносини поточних значень базисних змінних до позитивних коефіцієнтів провідного стовпця, відповідним даним базисним змінним. Потім беремо мінімальне з цих відносин і по тому, якому рядку воно відповідає, визначаємо провідний рядок. У нас є три таких відносини: по змінній Х8 (8/1=8), Х9 (0/6=0) і Х10 (0/6=0). Вийшли два мінімальні значення, значить, візьмемо будь-яке з них, наприклад по змінній Х9. Після знаходимо провідний елемент, він розташований на перетині провідного рядка і провідного стовпця (у нашому випадку він рівний 6). Потім визначаємо змінні, які виключатимемо з базису і включатимемо в нього. Змінну, якою відповідає провідний стовпець, включатимемо в базис замість змінній, якою відповідає провідний рядок. Далі всі перетворення виконуємо по звичайних формулах симплекс-метода або за "правилом прямокутника". Перетворенням піддається вся симплекс-таблиця, включаючи E-рядок, W-рядок і стовпець рішень. Отримуємо нову симплекс-таблицю:

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	БР
E	0	-1,5	-2	0	-4,5	-2	0	0	0,5	0	0
-W	0	-1	2	0	-3	2	0	0	2	0	0
X7	1	1	1	0	0	0	1	0	0	0	8
X8	-0,33	0,17	0	0	1,5	1	0	1	-0,17	0	8
X4	0,33	-0,17	0	1	-0,5	0	0	0	0,17	0	0
X10	0	1	-2	0	3	-2	0	0	-1	1	0

Таблиця 3. Симплекс-таблиця №2.

Ми отримали нове рішення (Х7,Х8,Х4,Х10)=(8,8,0,0). Це рішення неприпустимо, оскільки в базисі міститься штучна змінна Х10. Виполім чергову ітерацію. По рядку - W для включення в базис вибираємо змінну X5 (оскільки -3 - максимальне по модулю негативне число). Стовпець X5 стає таким, що веде. По мінімальному сімплексному відношенню ( 8/1,5=5,33; 0/3=0) для виключення з базису вибираємо змінну Х10. Провідний елемент рівний 3. Після проведених пересчетов отримуємо нову симплекс-таблицю:

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	БР
E	0	0	-5	0	0	-5	0	0	-1	1,5	0
-W	0	0	0	0	0	0	0	0	1	1	0
X7	1	1	1	0	0	0	1	0	0	0	8
X8	-0,33	-0,33	1	0	0	2	0	1	0,33	-0,5	8
X4	0,33	0	-0,33	1	0	-0.33	0	0	0	0,17	0
X5	0	0,33	-0,67	0	1	-0,67	0	0	-0,33	0,33	0

Таблиця 4. Симплекс-таблиця №3.

4.5. ДРУГИЙ ЕТАП ДВОХЕТАПНОГО СИМЛЕКС-МЕТОДУ

Отже, як видно з Таблиці 4, всі штучні змінні вийшли з базису, штучна цільова функція обнулилася - значить, перший етап двохетапного симплекс-метода закінчений, знайдено початкове допустиме рішення: (Х1,X2,X3,X4,X5,X6) = (0,0,0,0,0,0), цільова функція Е=0. Тепер переходимо до реалізації другого етапу: викреслюємо з таблиці рядок штучної цільової функції і стовпці штучних змінних; над новою таблицею виконуємо звичайні процедури симплекс-метода, а саме: провідний стовпець визначається також, як і для першого етапу двохетапного симплекс-метода, єдина відмінність полягає в тому, що максимальний по модулю негативний коефіцієнт знаходимо по Е-рядку цільової функції. Розрахунок ведемо до тих пір, поки в Е-рядку не залишиться негативних коефіцієнтів:

БП	X1	X2	X3	X4	X5	X6	X7	X8	БР
E	0	0	-5	0	0	-5	0	0	0
X7	1	1	1	0	0	0	1	0	8
X8	-0,33	-0,33	1	0	0	2	0	1	8
X4	0,33	0	-0,33	1	0	-0,33	0	0	0
X5	0	0,33	-0,67	0	1	-0,67	0	0	0

Таблиця 5. Симплекс-таблиця №4.

Наше початкове допустиме рішення не є оптимальним, оскільки в Е-рядку містяться негативні коефіцієнти. Визначимо по Е-рядку нову змінну для включення в базис. Це змінна X3, оскільки -5 - максимальне по модулю негативне число (коефіцієнт Е-рядка при змінній X6 також рівний -5, тому вибрали будь-яку з цих змінних, наприклад X3). Стовпець X3 стає таким, що веде. По мінімальному сімплексному відношенню ( 8/1=8; 8/1=8) для виключення з базису вибираємо змінну Х7 (сімплексне відношення при змінній X8 також рівне 8, тому вибрали будь-яку з цих змінних). Провідний елемент рівний 1. Після проведених пересчетов отримуємо нову симплекс-таблицю:

БП	X1	X2	X3	X4	X5	X6	X7	X8	БР
E	5	5	0	0	0	-5	5	0	40
X3	1	1	1	0	0	0	1	0	8
X8	-1,33	-1,33	0	0	0	2	-1	1	0
X4	0,67	0,33	0	1	0	-0,33	0,33	0	2,67
X5	0,67	1	0	0	1	-0,67	0,67	0	5,33

Таблиця 6. Симплекс-таблиця №5.

Отже, як видно з таблиці, деякі з шуканих змінних, а саме Х3, Х4 і Х5, почали рости, що привело і до зростання значення цільової функції - з нульового значення вона прийняла значення 40. Це можна пояснити тим, що з точки початкового допустимого рішення ми перейшли до сусідньої кутової точки області допустимих рішень, причому в цій сусідній крапці зростання цільової функції максимальне. Проте в Е-рядку є ще негативний коефіцієнт, тому продовжимо розрахунки.

Визначимо по Е-рядку нову змінну для включення в базис. Це змінна X6, оскільки -5 - максимальне по модулю негативне число. Стовпець X6 стає таким, що веде. По мінімальному сімплексному відношенню ( 0/2=0) для виключення з базису вибираємо змінну Х8. Отримуємо нову симплекс-таблицю:

БП	X1	X2	X3	X4	X5	X6	X7	X8	БР
E	1,67	1,67	0	0	0	0	2,5	2,5	40
X3	1	1	1	0	0	0	1	0	8
X6	-0,67	-0,67	0	0	0	1	-0,5	0,5	0
X4	0,44	0,11	0	1	0	0	0,17	0,17	2,67
X5	0,22	0,55	0	0	1	0	0,33	0,33	5,33

Таблиця 7. Симплекс-таблиця №6.

Оскільки всі коефіцієнти E-рядка таблиці 7 позитивних, то оптимальне рішення знайдене. Оптимальний план полягає в тому, щоб токарний верстат працював над деталями типу 3 8 годин за зміну, тобто всю робочу зміну, і не працював над деталями типу 1 і 2 взагалі. Верстат-автомат повинен працювати за зміну 2,67 години над деталями типу 1 і 5,33 години над деталями типу 2 і не повинен працювати над деталями типу 3. При цьому за зміну випускатиметься максимально можлива кількість комплектів деталей, а саме 40 комплектів. Жоден з верстатів не простоюватиме.

5. АНАЛІЗ МОДЕЛІ НА ЧУТЛИВІСТЬ

У остаточній симплекс-таблице, що містить оптимальне рішення, міститься не тільки само оптимальне рішення, але і інша інформація. На основі останньої симплекс-таблицы вирішуються завдання аналізу на чутливість - визначення впливу змін в початкових даних завдання на оптимальне рішення. Інтерпретація симплекс-таблицы і аналіз на чутливість повністю залежать від змістовного сенсу конкретного завдання. У нашому випадку ми маємо справу із завданням об розподіли ресурсів, а саме ресурсів часу.

5.1. СТАТУС РЕСУРСІВ

По статусу ресурси діляться на дефіцитних і недефіцитних. Якщо деякий ресурс при реалізації оптимального плану витрачається повністю, він називається дефіцитним, якщо не повністю - недефіцитним.

Статус ресурсів визначається по значеннях залишкових змінних Х7 і Х8, введених в початкову систему обмежень для приведення її до стандартної форми. Ці змінні означають залишки ресурсів при реалізації оптимального плану. Жодна із залишкових змінних не входить в оптимальне рішення, тобто їх значення рівні нулю. Це означає, що токарний верстат і верстат-автомат використовувалися весь виділений для їх роботи час, тобто запаси часу роботи верстатів є дефіцитними ресурсами. Збільшення запасів дефіцитних ресурсів дозволяє збільшити значення цільової функції, а зниження цих запасів приводить до зменшення цільової функції.

5.2. ЦІННІСТЬ РЕСУРСІВ

Цінність ресурсу - це величина збільшення значення цільової функції при збільшенні запасів даного ресурсу на одиницю (або відповідно величина зменшення цільової функції при зниженні запасу ресурсу). Інша назва цієї величини - тіньова (прихована) ціна. У симплекс-таблице, відповідною оптимальному рішенню, тіньові ціни містяться в E-рядку і є коефіцієнтами при залишкових змінних, відповідним залишкам ресурсів. Таким чином, цінність часу роботи токарного верстата і верстата-автомата відповідно рівна по 2,5 комплекту деталей. Іншими словами, якщо запас часу роботи токарного верстата збільшити (зменшити) на 1 годину, то кількість вироблюваних комплектів деталей збільшиться (зменшиться) на 2,5 одиниць, і, аналогічно, якщо збільшити (зменшити) час роботи верстата-автомата верстата на 1 годину, то кількість комплектів збільшиться (зменшиться) на 2,5 комплекту.

5.3. АНАЛІЗ НА ЧУТЛИВІСТЬ ДО ЗМІН ПРАВИХ ЧАСТИН ОБМЕЖЕНЬ

Для аналізу рішення на чутливість до зміни запасів часу роботи верстатів (без зміни інших початкових даних завдання) використовуються коефіцієнти із стовпців залишкових змінних Х7 і Х8 (відповідно для токарного верстата і верстата-автомата) в останній симплекс-таблице. Наприклад, якщо запас часу роботи токарного верстата змінився на d годинника і став рівний 8+d годинника, то нове оптимальне рішення знаходиться по наступних формулах:

Х3 = 8 + 1*d

X6 = 0 - 0,5*d

X4 = 2,67 + 0,17*d

X5 = 5,33 + 0,33*d

E = 40 + 2,5*d

При складанні цих формул використовували коефіцієнти із стовпця залишкової змінної Х7 в останній симплекс-таблице. По змістовному сенсу ці формули означають зміну часу роботи токарного верстата або верстата-автомата над кожною з деталей в добу при зміні запасу дефіцитного ресурсу. Формула E = 40 + 2,5*d означає зміну кількості вироблюваних комплектів деталей в добу. Наприклад, якщо час роботи токарного верстата стане не 8, а 6 годин на добу, тобто зменшиться на 2 години (d=-2), то базисні змінні, а також цільова функція приймуть наступні значення:

Х3 = 6; Х6 = 1; Х4 = 2,33; Х5 = 4,67; Е = 35.

Решта всіх змінних рівна нулю (вони не є базисними).

Як видно, із-за зменшення запасу часу роботи токарного верстата зменшився час роботи цього верстата над деталями типу 3, але разом з тим збільшився час роботи верстата-автомата над цими ж деталями. Оскільки верстат-автомат став працювати за зміну 1 година над деталями третього типу, то він зменшив свій час роботи над деталями типу 1 і 2 (раніше він віддавав весь свій час на обробку тільки цих деталей). І, очевидно, що якщо час роботи токарного верстата зменшився, то зменшиться і кількість комплектів деталей, вироблюваних в добу.

Таким чином, для дослідження впливу зміни запасу ресурсу на оптимальне рішення немає необхідності вирішувати задачу наново (з новим обмеженням). Для знаходження оптимальне рішення досить по остаточній симплекс-таблице початкового завдання скласти рівняння і підставити в них величину зміни запасу ресурсу (значення d).

Зміна запасів ресурсів (тобто правих частин обмежень) може привести до неприпустимості оптимального базису, знайденого для початкового завдання. Оскільки на всі змінні, використовувані в завданні, накладається вимога позитивності, допустимий діапазон зміни запасу ресурсу (тобто діапазон допустимих значень d) знаходять з системи нерівностей. Таким чином, допустимий діапазон зміни запасу часу роботи токарного верстата, при якому склад змінних в базисі оптимального рішення не змінюється, знаходиться з умови:

Х3 = 8 + 1*d > 0

Х6 = 0 - 0,5*d > 0

Х4 = 2,67 + 0,17*d > 0

Х5 = 5,33 + 0,33*d > 0

Вирішивши дану систему нерівностей, отримаємо, що -8 < d < 0. Таким чином, базис оптимального рішення складатиметься із змінних (Х3,Х6,Х4,Х5), якщо запас часу роботи токарного верстата знаходитиметься в діапазоні від 0 до 8 годин. Вихід значення d за межі цього діапазону приведе до неприпустимості знайденого нами оптимального рішення, оскільки мінімум одна з базисних змінних виявиться негативною, і для того, щоб знайти оптимальне рішення, нам доведеться вирішувати задачу наново.

Аналогічно виконується аналіз на чутливість до зміни запасу часу роботи верстата-автомата.

5.4. АНАЛІЗ НА ЧУТЛИВІСТЬ ДО ЗМІН КОЕФІЦІЄНТІВ ЦІЛЬОВІЙ ФУНКЦІЇ

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

6. ВИЗНАЧЕННЯ ОПТИМАЛЬНОГО ЦІЛОЧИСЕЛЬНОГО РІШЕННЯ

Дане завдання за своїм змістом є частково цілочисельним. Змінні X1, X2, X3, X4, X5, X6,обозначающие час роботи певного верстата над деталями певного типу, повинні приймати цілі значення. В той же час, змінні Х7, Х8, що позначають час простою відповідно токарного верстата і верстата-автомата, можуть приймати дробові значення. Для пошуку оптимального цілочисельного рішення скористаємося методом Гоморі для частково цілочисельних завдань.

6.1. МЕТОД ГОМОРИ ДЛЯ ЧАСТКОВО ЦІЛОЧИСЕЛЬНИХ ЗАВДАНЬ

Метод Гоморі для знаходження цілочисельного рішення відноситься до великої групи методів, званих методами відсікань. Ці методи засновані на введенні в завдання додаткових обмежень, що дозволяють врахувати вимогу цілочисельності. Основна ідея методів відсікань полягає в тому, що на отримане оптимальне нецілочисельне рішення накладається додаткове обмеження, яке робить це рішення неприпустимим, але і не відсікає жодного цілочисельного рішення від області допустимих рішень.

Обмеження складаються по фінальній симплекс-таблице, в якій отримано оптимальне нецілочисельне рішення. При цьому на первинну систему обмежень накладається нове обмеження по наступній формулі:

L1*W1 + L2*W2 + . +Ln*Wn e {Bi}, де

Aij, якщо Aijf0 і Wj може бути дробом (1)

({Bi}*Aij)/({Bi}-1), якщо Aij<0 і Wj може бути дробом (2)

Lj = {Aij}, якщо і Wi повинна бути цілою (3)

Bi}*(1-{Aij})/(1-{Bi}), якщо {Aij}>{Bi} і Wi повинна бути цілою (4)

j=1.,n

де Wn - небазисна змінна;

Bi - базисна змінна, що має максимальну дробову частину ( дробова частина числа - це різниця між цим числом і максимальним цілим числом, що не перевершує його);

Aij - коефіцієнт, що стоїть на перетині рядка i-ой базисної змінної і стовпця j-ой небазисної змінної;

Далі отримане обмеження приводиться до стандартного вигляду:

-L1*W1 - L2*W2 - . -Ln*Wn + Sr = -{Bi}

де r - номер ітерації алгоритму.

Тут Sr - ненегативна залишкова змінна, що не має ніякого змістовного сенсу; у оптимальному цілочисельному рішенні ця змінна виявляється рівною нулю.

У нашому випадку змінна, що має максимальну дробову частину, - це Х4 ({2,67}=0,67), вона повинна бути цілою, змінні Х7 і Х8 можуть бути дробами, змінні Х1 і Х2 повинні бути цілими, тому, згідно вище приведеній формулі, складемо нове додаткове обмеження. Оскільки всі коефіцієнти на перетинах базисної змінної Х4 і небазисних змінних Х1, Х2, Х7, Х8 і 0 (0,44і0, 0,11і0, 0,17і0), то коефіцієнти при змінних Х1 і Х2 розрахували по формулі (3): L1={0,44}=0,44, L2={0,11}=0,11, а коефіцієнти при змінних Х7 і Х8 розрахували по формулі (1): L3=0,17, L4=0,17. {В4}={Х4} = {2,67} = 0,67. Обмеження матиме вигляд:

0,44Х1 + 0,11Х2 + 0,17Х7 + 0,17Х8 з 0,67

Можна переконатися, що це обмеження зробило наше оптимальне рішення неприпустимим ( якщо підставити Х1=0, Х2=0, Х7=0, Х8=0, - значення змінних, отриманих в оптимальному нецілочисельному рішенні, то отримаємо 0e0,67 - невірно).

Привівши обмеження до стандартного вигляду, маємо:

-0,44Х1 - 0,11Х2 - 0,17Х7 - 0,17Х8 + Х9 = -0,67

Додамо до наший фінальній симлекс-таблиці рядок і стовпець, відповідні побудованому обмеженню і новій базисній змінній Х9:

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	БР
E	1,67	1,67	0	0	0	0	2,5	2,5	0	40
X3	1	1	1	0	0	0	1	0	0	8
X6	-0,67	-0,67	0	0	0	1	-0,5	0,5	0	0
X4	0,44	0,11	0	1	0	0	0,17	0,17	0	2,67
Х5	0,22	0,55	0	0	1	0	0,33	0,33	0	5,33
X9	-0,44	-0,11	0	0	0	0	-0,17	-0,17	1	-0,67

Таблиця 8. Симплекс-таблиця №7.

Як видно, отримана симплекс-таблиця містить неприпустиме рішення (змінна Х9 має негативне значення). Проведемо подальший перерахунок таблиці, причому провідний рядок визначаємо максимальним по модулю негативним елементом стовпця рішень, а провідний стовпець - мінімальним по модулю відношенням елементу Е-рядка до негативних елементів провідного рядка. Перерахунок симплекс-таблицы здійснюється на основі стандартних процедур симплекс-метода.

Отже, змінна, що виключається з базису, - це X9, оскільки її значення -0,67 - це максимальний по модулю негативний елемент стовпця рішень. У базис включаємо змінну X1, оскільки |1,67/(-0,44)|=3,8, |1,67/(-0,11)|=15,2, |2,5/(-0,17)|=14,7, 3,8 - мінімальне по модулю відношення елементу Е-рядка до негативних елементів провідного рядка. Провідний елемент рівний -0,44. Отримаємо нову симплекс-таблицю:

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	БР
E	0	1,25	0	0	0	0	1,875	1,875	3,75	37,5
X3	0	0,75	1	0	0	0	0,625	-0,375	2,25	6,5
X6	0	-0,5	0	0	0	1	-0,25	0,75	-1,5	1
X4	0	0	0	1	0	0	0	0	1	2
Х5	0	0,5	0	0	1	0	0,25	0,25	0,5	5
X1	1	0,25	0	0	0	0	0,375	0,375	-2,25	1,5

Таблиця 9. Симплекс-таблиця №8.

Всі значення базисних змінних стали ненегативними, це означає зупинку обчислювального процесу на даній ітерації і аналіз отриманих результатів. Як видно з таблиці, до базису увійшла нова змінна Х1, змінні Х3, Х4 і Х5 зменшили своє значення, а змінна Х6 збільшилася. Значення цільової функції зменшилося і стало рівне 37,5, що пояснюється тим, що оптимальне нецілочисельне рішення було відсічене нашим додатковим обмеженням, і для пошуку оптимального цілочисельного рішення ми пішли углиб області допустимих рішень, де значення цільової функції менше оптимального. Наше рішення все ще нецілочисельне, тому складемо нове обмеження.

Змінна, що має максимальну дробову частину, - це Х3 ({6,5}=0,5) (Х1 має таку ж дробову частину, тому вибрали будь-яку з них, наприклад, Х3), вона повинна бути цілою, змінні Х7, Х8 і Х9 можуть бути дробами, змінна Х2 повинна бути цілою, тому, згідно формулі, складемо нове додаткове обмеження. Оскільки коефіцієнти на перетинах базисної змінної Х3 і небазисних змінних Х2, Х7, Х9 i 0 (0,75i0, 0,625i0, 2,25i0), то коефіцієнт при змінною Х2 розрахуємо по формулі (3): L1={0,75}=0,75, коефіцієнти при змінних Х7 і Х9 розрахуємо по формулі (1): L3=0,625, L4=2,25. Оскільки коефіцієнт на перетині базисної змінної Х3 і небазисною змінною Х8<0, то коефіцієнт при змінною Х8 розрахуємо по формулі (2): L2=({6,5}*(-0,375))/({6,5}-1)=0,375. {В3}={Х3} = {6,5} = 0,5. Обмеження матиме вигляд:

0,25Х2 + 0,625Х7 + 0,375Х8 + 2,25Х9 d 0,5

Або, після приведення до стандартного вигляду, отримаємо:

-0,25Х2 - 0,625Х7 - 0,375Х8 - 2,25Х9 + Х10 = -0,5

Додамо це обмеження до наший попередньою симплекс-таблице:

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	БР
E	0	1,25	0	0	0	0	1,875	1,875	3,75	0	37,5
Х3	0	0,75	1	0	0	0	0,625	-0,375	2,25	0	6,5
X6	0	-0,5	0	0	0	1	-0,25	0,75	-1,5	0	1
X4	0	0	0	1	0	0	0	0	1	0	2
X5	1	0,5	0	0	1	0	0,2	0,25	0,5	0	5
Х1	1	0,25	0	0	0	0	0,375	0,375	-2,25	0	1,5
X10	0	-0,25	0	0	0	0	-0,375	-0,375	-2,25	1	-0,5

Таблиця 10. Симплекс-таблиця №9.

Змінна, що виключається з базису, - це X10, оскільки її значення -0,5 - це максимальний по модулю негативний елемент стовпця рішень. У базис включаємо змінну X9, оскільки |3,75/(-2,25)|=1,67, |1,25/(-0,25)|=5, |1,875/(-0,375)|=5, 1,67 - мінімальне по модулю відношення елементу Е-рядка до негативних елементів провідного рядка. Провідний елемент рівний -2,25. Отримаємо нову симплекс-таблицю:

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	БР
E	0	0,83	0	0	0	0	1,25	1,25	0	1,67	36,67
Х3	0	0,5	1	0	0	0	0,25	-0,75	0	1	6
X6	0	-0,33	0	0	0	1	0	1	0	-0,67	1,33
X4	0	0,111	0	1	0	0	-0,17	-0,17	0	0,44	1,78
X5	0	0,444	0	0	1	0	0,17	0,17	0	0,22	4,89
Х1	1	0,5	0	0	0	0	0,75	0,75	0	-1	2
X9	0	0,11	0	0	0	0	0,17	0,17	1	-0,44	0,22

Таблиця 11. Симплекс-таблиця №10.

Рішення все ще не цілочисельне, тому переходиться до наступної ітерації. Змінна, що має максимальну дробову частину, - це Х5 ({4,89}=0,89), вона повинна бути цілою, змінні Х7, Х8 і Х10 можуть бути дробами, змінна Х2 повинна бути цілою, тому, згідно формулі, складемо нове додаткове обмеження. Оскільки коефіцієнти на перетинах базисної змінної Х5 і небазисних змінних Х2, X7, X8, Х10h0 (0,44i0, 0,17i0, 0,22i0), то коефіцієнт при змінною Х2 розрахуємо по формулі (3): L1={0,44}=0,44, коефіцієнти при змінних Х7, Х9 і Х10 розрахуємо по формулі (1): L2=0,17, L3=0,17, L4=0,22. {В5}={Х5} = {4,89} = 0,89. Обмеження матиме вигляд:

0,44Х2 + 0,17Х7 + 0,17Х8 + 0,22Х10 d 0,89

Або, після приведення до стандартного вигляду, отримаємо:

-0,44Х2 - 0,17Х7 - 0,17Х8 - 0,22Х10 + Х11 = -0,89

Додамо це обмеження до наший попередньою симплекс-таблице:

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	Х11	БР
E	0	0,83	0	0	0	0	1,25	1,25	0	1,67	0	36,67
Х3	0	0,5	1	0	0	0	0,25	-0,75	0	1	0	6
X6	0	-0,3	0	0	0	1	0	1	0	-0,67	0	1,33
X4	0	0,11	0	1	0	0	-0,17	-0,17	0	0,44	0	1,78
X5	0	0,44	0	0	1	0	0,17	0,17	0	0,22	0	4,89
Х1	1	0,5	0	0	0	0	0,75	0,75	0	-1	0	2
Х9	0	0,11	0	0	0	0	0,17	0,17	1	-0,44	0	2
X11	0	-0,44	0	0	0	0	-0,17	-0,17	0	-0,22	1	-0,89

Таблиця 12. Симплекс-таблиця №11.

Змінна, що виключається з базису, - це X11, оскільки її значення -0,89 - це максимальний по модулю негативний елемент стовпця рішень. У базис включаємо змінну X2, оскільки |0,83/(-0,44)|=1,9, |1,25/(-0,17)|=7,4, |1,67/(-0,22)|=7,6, 1,9 - мінімальне по модулю відношення елементу Е-рядка до негативних елементів провідного рядка. Провідний елемент рівний -0,44. Після пересчетов отримаємо отримаємо нову симплекс-таблицю:

БП	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	Х11	БР
E	0	0	0	0	0	0	0,938	0,94	0	1,25	1,89	35
Х3	0	0	1	0	0	0	0,063	-0,938	0	0,75	1,125	5
X6	0	0	0	0	0	1	0,125	1,125	0	-0,5	-0,75	2
X4	0	0	0	1	0	0	-0,125	-0,125	0	0,5	-0,25	2
X5	0	0	0	0	1	0	0	0	0	0	1	4
Х1	1	0	0	0	0	0	0,563	0,563	0	-1,25	1,125	1
Х9	0	0	0	0	0	0	0,125	0,125	1	-0,5	0,25	0
X2	0	1	0	0	0	0	0,375	0,375	0	0,5	-2,25	2

Таблиця 13. Симплекс-таблиця №12.

Стовпець рішень не містить негативних елементів, всі змінні X1, X2, X3, X4, X5, X6 прийняли цілочисельні значення, значить, оптимальне цілочисельне рішення знайдене, воно рівне: (X1,X2,X3,X4,X5,X6)=(1,2,5,2,4,2), цільова функція при цьому приймає максимальне значення: Е=35.

ВИСНОВОК

Після проведених обчислень, вирішивши задачу оптимізації, ми отримали наступні результати: оптимальний план роботи верстатів полягає в тому, щоб токарний верстат працював 1 година над деталями типу 1, 2 години над деталями типу 2 і 5 годин над деталями типу 3 за зміну; верстат-автомат повинен працювати 2 години над деталями типу 1, 4 години над деталями типу 2 і 2 години над деталями типу 3 за зміну. При цьому кількість комплектів деталей, що випускаються цехом, буде максимальна і рівна 35.

В результаті проведеного аналізу на чутливість до зміни запасу часу роботи токарного верстата отримали, що якщо запас часу роботи цього верстата знаходитиметься в межах від 0 до 8 годин, то базис оптимального рішення залишиться незмінним, тобто складатиметься із змінних (Х3,Х6,Х4,Х5).

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1. Смородинский С.С., Батин Н.В. Методи і алгоритми для вирішення оптимізаційних завдань лінійного програмування. Ч.1. - Мн.: БГУИР, 1995.

2. Смородинский С.С., Батин Н.В. Методи і алгоритми для вирішення оптимізаційних завдань лінійного програмування. Ч.2. - Мн.: БГУИР, 1996.

3. Смородинский С.С., Батин Н.В. Аналіз і оптимізація систем на основі аналітичних моделей. - Мн.: БГУИР, 1997.

4. Дегтярев Ю.И. Дослідження операцій. - М.: Вища школа, 1986.

УМОВНІ СКОРОЧЕННЯ

БР - базисне рішення

БП - базисна змінна

Додаток.

Умова завдання.

+-----------------------------------------------------------------------+

| X1 | X2 | X3 | X4 | X5 | X6 |Вид огр.|Значение|

+--------+--------+--------+--------+--------+--------+--------+--------|

| -1.00| -1.00| -2.00| -3.00| -3.00| -2.00| E | |

+--------+--------+--------+--------+--------+--------+--------+--------|

| 2.00| -1.00| 0.00| 6.00| -3.00| 0.00| == | 0.00|

| 2.00| 0.00| -2.00| 6.00| 0.00| -2.00| == | 0.00|

| 1.00| 1.00| 1.00| 0.00| 0.00| 0.00| <= | 8.00|

| 0.00| 0.00| 0.00| 1.00| 1.00| 1.00| <= | 8.00|

+-----------------------------------------------------------------------+

Виведення проміжних результатів оптимізації.

+----------------------------------------------------------------------------------------------------------+

| N| БП | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 |Баз.Реш.|

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+---

| 1| E | -1.00| -1.00| -2.00| -3.00| -3.00| -2.00| 0.00| 0.00| 0.00| 0.00| 0.00|

| +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+---

| | -W | -4.00| 1.00| 2.00| -12.00| 3.00| 2.00| 0.00| 0.00| 0.00| 0.00| 0.00|

| +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--

| | X9 | 2.00| -1.00| 0.00| 6.00| -3.00| 0.00| 0.00| 0.00| 1.00| 0.00| 0.00|

| | X10| 2.00| 0.00| -2.00| 6.00| 0.00| -2.00| 0.00| 0.00| 0.00| 1.00| 0.00|

| | X7 | 1.00| 1.00| 1.00| 0.00| 0.00| 0.00| 1.00| 0.00| 0.00| 0.00| 8.00|

| | X8 | 0.00| 0.00| 0.00| 1.00| 1.00| 1.00| 0.00| 1.00| 0.00| 0.00| 8.00|

+----------------------------------------------------------------------------------------------------------+

Провідний елемент знаходиться в 4 стовпці і 1 рядку.

Виведення проміжних результатів оптимізації.

+----------------------------------------------------------------------------------------------------------+

| N| БП | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 |Баз.Реш.|

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--

| 2| E | 0.00| -1.50| -2.00| 0.00| -4.50| -2.00| 0.00| 0.00| 0.50| 0.00| 0.00|

| +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+-

| | -W | 0.00| -1.00| 2.00| 0.00| -3.00| 2.00| 0.00| 0.00| 2.00| 0.00| 0.00|

| +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

| | X4 | 0.33| -0.17| 0.00| 1.00| -0.50| 0.00| 0.00| 0.00| 0.17| 0.00| 0.00|

| | X10| 0.00| 1.00| -2.00| 0.00| 3.00| -2.00| 0.00| 0.00| -1.00| 1.00| 0.00|

| | X7 | 1.00| 1.00| 1.00| 0.00| 0.00| 0.00| 1.00| 0.00| 0.00| 0.00| 8.00|

| | X8 | -0.33| 0.17| 0.00| 0.00| 1.50| 1.00| 0.00| 1.00| -0.17| 0.00| 8.00|

+----------------------------------------------------------------------------------------------------------+

Провідний елемент знаходиться в 5 стовпці і 2 рядку.

Виведення проміжних результатів оптимізації.

+----------------------------------------------------------------------------------------------------------+

| N| БП | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 |Баз.Реш.|

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--

| 3| E | 0.00| 0.00| -5.00| 0.00| 0.00| -5.00| 0.00| 0.00| -1.00| 1.50| 0.00|

| +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

| | -W | 0.00| 0.00| 0.00| 0.00| 0.00| 0.00| 0.00| 0.00| 1.00| 1.00| 0.00|

| +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

| | X4 | 0.33| 0.00| -0.33| 1.00| 0.00| -0.33| 0.00| 0.00| 0.00| 0.17| 0.00|

| | X5 | 0.00| 0.33| -0.67| 0.00| 1.00| -0.67| 0.00| 0.00| -0.33| 0.33| 0.00|

| | X7 | 1.00| 1.00| 1.00| 0.00| 0.00| 0.00| 1.00| 0.00| 0.00| 0.00| 8.00|

| | X8 | -0.33| -0.33| 1.00| 0.00| 0.00| 2.00| 0.00| 1.00| 0.33| -0.50| 8.00|

+----------------------------------------------------------------------------------------------------------+

Виведення проміжних результатів оптимізації.

+----------------------------------------------------------------------------------------+

| N| БП | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 |Баз.Реш.|

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+---

| 3| E | 0.00| 0.00| -5.00| 0.00| 0.00| -5.00| 0.00| 0.00| 0.00|

| +----+--------+--------+--------+--------+--------+--------+--------+--------+-

| | X4 | 0.33| 0.00| -0.33| 1.00| 0.00| -0.33| 0.00| 0.00| 0.00|

| | X5 | 0.00| 0.33| -0.67| 0.00| 1.00| -0.67| 0.00| 0.00| 0.00|

| | X7 | 1.00| 1.00| 1.00| 0.00| 0.00| 0.00| 1.00| 0.00| 8.00|

| | X8 | -0.33| -0.33| 1.00| 0.00| 0.00| 2.00| 0.00| 1.00| 8.00|

+----------------------------------------------------------------------------------------+

Провідний елемент знаходиться в 3 стовпці і 3 рядку.