Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Варіант 30




Варіант 28

Варіант 26

Варіант 24

Варіант 22

Варіант 20

Варіант 18

Варіант 16

Варіант 14

 

Речовина Кількість од. речовини, що міститься в 1 кг сировини кожного виду Мінімальний вміст речовини, од.
I II
А      
В      
С -    
Ціна 1 кг сировини, грош. од.      

 

 

 

Речовина Кількість од. речовини, що міститься в 1 кг сировини кожного виду Мінімальний вміст речовини, од.
I II
А      
В   -  
С      
Ціна 1 кг сировини, грош. од.      

 

 

 

Речовина Кількість од. речовини, що міститься в 1 кг сировини кожного виду Мінімальний вміст речовини, од.
I II
А      
В   -  
С      
Ціна 1 кг сировини, грош. од.      

 

 

 

Речовина Кількість од. речовини, що міститься в 1 кг сировини кожного виду Мінімальний вміст речовини, од.
I II
А      
В -    
С      
Ціна 1 кг сировини, грош. од.      

 

 

 

Речовина Кількість од. речовини, що міститься в 1 кг сировини кожного виду Мінімальний вміст речовини, од.
I II
А -    
В      
С      
Ціна 1 кг сировини, грош. од.      

 

 

 

Речовина Кількість од. речовини, що міститься в 1 кг сировини кожного виду Мінімальний вміст речовини, од.
I II
А -    
В      
С      
Ціна 1 кг сировини, грош. од.      

 

 

 

Речовина Кількість од. речовини, що міститься в 1 кг сировини кожного виду Мінімальний вміст речовини, од.
I II
А      
В   -  
С      
Ціна 1 кг сировини, грош. од.      

 

 

 

Речовина Кількість од. речовини, що міститься в 1 кг сировини кожного виду Мінімальний вміст речовини, од.
I II
А -    
В      
С      
Ціна 1 кг сировини, грош. од.      

 

 

 

Речовина Кількість од. речовини, що міститься в 1 кг сировини кожного виду Мінімальний вміст речовини, од.
I II
А      
В      
С   -  
Ціна 1 кг сировини, грош. од.      

 

1.3 Контрольні питання

1. Канонічна форма задачі лінійного програмування?

2. Дайте визначення поняттям: провідний стовпець, провідний рядок і провідний елемент?

3. Що таке базисні і небазисні змінні?

4. Алгоритм симплекс-методу?

5. Сформулюйте умову оптимальності симплекс-методу?

6. Сформулюйте умову допустимості симплекс-методу?

7. У чому полягає метод Гауса-Жордана?

8. Коли вводять штучні змінні?

9. Коли у вираз цільовій функції вводять штраф М?

10. Яку функцію виконують додаткові залишкові змінні?

11. Як на другому етапі двохетапного методу формулюється вихідне завдання?

12. Які обмеження записуються на другому етапі двохетапного методу?

 


ЛАБОРАТОРНА РОБОТА № 2
ДВОЇСТИЙ СИМПЛЕКС-МЕТОД І АНАЛІЗ ЧУТЛИВОСТІ

 

2.1 Теоретичні зведення

2.1.1 Двоїстий симплекс-метод

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

Для того, щоб існувало початкове оптимальне ("супероптимальне") і неприпустиме рішення, необхідне виконання двох умов.

1. Цільова функція повинна задовольняти умові оптимальності звичайного симплекс-методу.

2. Всі обмеження повинні бути нерівностями типу "≤".

Другу умову можна задовольнити простим множенням на -1 нерівностей типу "≥". Якщо є обмеження у вигляді рівності, то ці рівності замінюються на дві нерівності. Наприклад, рівність еквівалентна двом нерівностям

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

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

Змінна, що вводиться в базис визначається як змінна, на якій досягається наступний мінімум:

(2.1)

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

2.1.2 Узагальнений симплекс-метод

У прямому симплекс-методі початкове рішення припустиме, але не оптимально. У двоїстому симплекс-методі дане рішення оптимально (точніше, "супероптимально"), але не допустимо. Об'єднавши ці два методи можна розпочати вирішення задачі ЛП з неоптимального і неприпустимого рішення.

Рішення задачі ЛП узагальненими симплекс-методом відбувається в два етапи. На першому етапі необхідно позбутися від неприпустимості рішення за допомогою двоїстого симплекс методу. У результаті ми прийдемо в будь-яку точку області допустимих рішень. Далі можна використовувати прямий симплекс-метод для отримання оптимального рішення.

2.1.3 Аналіз чутливості

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

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

У загальному випадку зміна коефіцієнтів вихідної задачі може призвести до однієї з наступних чотирьох ситуацій:

- поточне базисне рішення залишається оптимальним і допустимим;

- поточне рішення стає неприпустимим;

- поточне рішення стає неоптимальним;

- поточне рішення стає неоптимальним і неприпустимим.

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

Зміна правих частин обмежень вихідної задачі вимагає повторних обчислень правих частин обмежень у симплекс-таблиці, для чого використовується формула:

(2.2)

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

1. Нове обмеження є надлишковим. Це означає, що нове обмеження виконується при поточному оптимальному рішенні.

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

 

Зміни, що впливають на оптимальність рішення. Змінити оптимальність поточного рішення можуть два чинники.

1. Зміна коефіцієнтів цільової функції.

2. Додавання до моделі нового виду виробничої діяльності (тобто. додавання нової змінної).

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

Обчислювальна процедура полягає в наступному.

1. Обчислюються значення двоїстих змінних. Для цього можна використовувати один з двох методів:

Метод 1

(2.3)

Елементи у вектор-рядку вихідних коефіцієнтів цільової функції повинні бути перераховані в такому порядку, в якому базисні змінні перераховані в базисному стовпці симплекс-таблиці.

Метод 2

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

(2.4)

 

2. На основі значень двоїстих змінних обчислюються коефіцієнти z-рядка.

Обчислення значень z-рядка відбувається за наступною формулою:

(2.5)

При цьому можливі два варіанти:

1. Якщо для нового z-рядка умова оптимальності виконується, поточне рішення залишається оптимальним, але значення цільової функції може змінитися.

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

Для обчислення значень двоїстих змінних може застосовуватися один з двох методів.

2.2 Завдання на виконання лабораторної роботи

1. Вирішити завдання двоїстим симплекс методом.

2. Провести аналіз чутливості отриманого оптимального рішення.

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

2.2. Знайти інтервал допустимих змін для коефіцієнтів при змінних в цільовій функції.

Таблиця 2.1 Варіанти завдань
№ варіанту Модель
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

 

2.3 Контрольні питання

1. Сформулюйте поняття прямої й двійкової задач лінійного програмування?

2. Яке співвідношення прямої й двійкової задач лінійного програмування?

3. Які необхідні умови, щоб існувало початкове оптимальне ("супероптимальне") і неприпустиме рішення?

4. Яка змінна вибирається в якості виключаємої?

5. Що називається аналізом чутливості й коли він виконується?

6. Які зміни впливають на допустимість рішення?

7. Які зміни впливають на оптимальність рішення?

8. На що впливає зміна коефіцієнтів цільової функції?

 


ЛАБОРАТОРНА РОБОТА № 3
ТРАНСПОРТНА ЗАДАЧА ЛІНІЙНОГО ПРОГРАМУВАННЯ

3.1 Теоретичні зведення

3.1.1 Транспортні задачі

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

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

3.1.2 Математична постановка транспортної задачі

У загальному вигляді завдання можна представити таким чином: у m пунктах виробництва A1, A2,..., Am є однорідний вантаж у кількості відповідно a1, a2,..., am. Цей вантаж потрібно доставити в n пунктів призначення B1, B2,..., Bn у кількості відповідно b1, b2,..., bn. Вартість перевезення одиниці вантажу (тариф) з пункту Ai в пункт Bj дорівнює cij.

Потрібно скласти план перевезень, що дозволяє вивести всі вантажі і має мінімальну вартість.

Позначимо через xij кількість вантажу, що перевозиться з пункту Ai, в пункт Bj. Запишемо умови задачі у транспортну таблицю, яку будемо використовувати для знаходження рішення.

Таблиця 3.1 Транспортна таблиця

Bi Ai B1 B2 Bj Bn
b1 b2 bi bn
A1 a1 c11 x11 c12 x12 с1j x1j c1n x1n
A2 a2 c21 x21 c22 x22 c2j x2j c2n x2n
Ai ai ci1 xi1 ci2 xi2 cij xij cin xin
Am am cm1 xm1 cm2 xm2 cmj xmj ... cmn xmn

 

Математична модель транспортної задачі має вигляд:

(3.1)

при обмеженнях:

(3.2)

 

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

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

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

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

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

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

3.1.3 Методи знаходження опорного плану

Метод північно-західного кута (діагональний)

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

1. Змінній присвоюється максимальне значення, що допускається обмеженнями на попит і пропозицію.

2. Викреслюється рядок (або стовпець) з повністю реалізованою пропозицією (з задоволеним попитом). Це означає, що у викресленому рядку (стовпці) ми не будемо присвоювати значення іншим змінним (крім змінної, визначеної на першому етапі).

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

 




Поделиться с друзьями:


Дата добавления: 2014-11-29; Просмотров: 303; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.073 сек.