Решение оптимизационной завдання лінійного программирования

Білоруський державний университет.

інформатики, і радиоэлектроники.

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

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

«До захисту допускаю».

______________Н.В. Батин.

«___"______________2001г.

КУРСОВА РОБОТА з дисципліни «Системний аналіз політики та дослідження операцій» на задану тему: «Рішення оптимизационной завдання лінійного программирования».

Виконав студент грн. 920 603 Журавкин А.В.

Керівник роботи Батин Н.В.

Мінськ, 2001.

ЗМІСТ: ВВЕДЕНИЕ…3 1. Постановка завдання оптимизации…8 2. Побудова аналітичної модели…9 3. Обгрунтування і опис обчислювальної процедуры…11.

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

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

3. Двухэтапный симплекс-метод…12 4. Рішення завдання оптимізації з урахуванням симплекс-таблиц…14.

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

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

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

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

5. Другий етап двухэтапного метода…19 5. Аналіз моделі на чувствительность…22.

1. Статус ресурсов…22.

2. Цінність ресурсов…22.

3. Аналіз на чутливість до змін правих частин ограничений…23.

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 і трьох в комплекті: кожну деталь 1 — по 2 деталі 2 і трьох. Годинна продуктивність верстатів перспективами кожного із деталей приведено в таблиці: | | | |Верстати |Деталі | | | | | | | |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? 0.

Цільова функція з нашого завданню повинна висловлювати кількість комплектів деталей, випущених за зміну, тому сплюсуємо все випущені деталі поділимо п’ять (до комплекту, як згадувалося, входять 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? 0.

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

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

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

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

A11X1 + A12X2 + … + A1nXn = B1;

A21X1 + A22X2 + … + A2nXn = B2;

…

Am1X1 + Am2X2 + … + AmnXn = Bm;

Xj? 0, j=1,…, n і що звертають в максимум лінійну функцію цих переменных:

E = C1X1 + C2X2 + … + CnXn (max.

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

Bj? 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? 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 ?0.

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

Х7 = 8;

Х8 = 8;

Х9 = 0;

Х10 = 0. Тепер потрібно виконати завдання, тобто. знайти оптимальне дозволене рішення. І тому скористаємося двухэтапным симплекс-методом.

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

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

1. Будуємо штучну цільову функцію — суму всіх штучних переменных:

W = X9 + X10 (min.

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

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

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

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

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

— W = 4X1 — X2 — 2X3 + 12X4 — 3X5 — 2X6 (max.

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

5. Складаємо вихідну симплекс-таблицу:

|БП |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.

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

6. Реалізуємо перший етап двухэтапного методу: з допомогою процедур симплексметоду виконуємо максимізацію функції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 комплекту деталей. Інакше кажучи, якщо запас часу роботи токарського верстата збільшити (зменшити) одну годину, кількість вироблених комплектів деталей збільшиться (зменшиться) на 2,5 одиниці, і, аналогічно, якщо збільшити (зменшити) час верстатаавтомата верстата одну годину, кількість комплектів збільшиться (зменшиться) на 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. АНАЛІЗ НА ЧУТЛИВІСТЬ До ЗМІН КОЕФІЦІЄНТІВ ЦЕЛЕВОЙ.

ФУНКЦИИ.

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

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

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

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

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

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

L1*W1 + L2*W2 + … +Ln*Wn? {Bi}, где.

Aij, якщо Aij?0 і Wj може бути дробової, (1).

({Bi}*Aij)/({Bi}-1), якщо 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, — значення змінних, здобутих у оптимальному нецелочисленном рішенні, одержимо 0?0,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? 0 (0,75?0, 0,625?0, 2,25?0), то коефіцієнт при перемінної Х2 розрахуємо за такою формулою (3): L1={0,75}=0,75, коефіцієнти при змінних Х7 і Х9 розрахуємо за такою формулою (1): L3=0,625, L4=2,25. Оскільки коефіцієнт на перетині базисної перемінної Х3 і небазисной перемінної Х8.