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

Размещено на http://allbest.ru

Завдання 1

Фірмою «Супертранзистор» випускаються радіоприймачі трьох різних моделей: А, В і С. Кожен виріб вказаних моделей приносить прибуток в розмірі 8, 15 і 25 грн. відповідно, кожна модель характеризується певним чином, необхідним для виготовлення відповідних деталей, збирання виробу і його установок. З розрахунку на 10 приймачів А потрібно 3 год для виготовлення деталей, 4 год на збирання та 1 год на установку. Відповідні показники з розрахунку на 10 приймачів моделі В дорівнюють 3, 5 і 1,5 год, а на 10 приймачів моделі С - 5, 8 і 3 год.

У плановому поточному періоді фірма може витратити на виробництво деталей 150 год, на збирання 200 год і установку 60 год.

За початковими даними згідно з варіантом завдань:

побудувати математичну модель;

записати модель подвійної задачі;

розв'язати початкову задачу симплекс-методом;

знайти розв'язання подвійної задачі;

визначити дефіцитні ресурси;

визначити види нерентабельної продукції;

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

Рішення

Побудова математичної моделі. Нехай -- план виробництва -ої моделі радіоприймача, .

Вихідні дані задачі можна представити у вигляді наступної таблиці:

Операції	Модель радіоприймача	Фонд робочого часу (год)
	А	В	С
Виготовлення деталей	0,3	0,3	0,5	150
Збирання	0,4	0,5	0,8	200
Установка	0,1	0,15	0,3	60
Прибуток з одиниці продукції	8	15	25

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

на виготовлення деталей ;

на збирання ;

на установку ;

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

.

Отже, математична модель поставленої задачі має такий вигляд:

;

Математична модель подвійної задачі.

Розв'язування початкової задачі симплекс-методом.

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

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

Канонічну систему обмежень задачі запишемо у векторній формі:

Де

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

Згідно з визначеними векторна форма запису системи обмежень задач матиме вигляд

.

Оскільки додатні коефіцієнти х4 ,х5 та , відповідають лінійно незалежним векторам, то за означенням

є опорним планом задачі і для цього початкового плану

.

Складемо симплексну таблицю:

№ п/п	Базис		План	8	15	25	0	0	0
1		0	150	0,3	0,3	0,5	1	0	0	300
		0	200	0,4	0,5	0,8	0	1	0	250
		0	600	0,1	0,15	0,3	0	0	1	2000 min
Zj - Cj ? 0	0	-8	-15	-25	0	0	0
№ п/п	Базис		План	7	6	5	4	0	0
2		0	25	1/20	-1/80	0	1	-5/8	0
		25	250	Ѕ	5/8	1	0	5/4	0
		0	525	-1/20	-3/80	0	0	-3/8	1
Zj - Cj ? 0	6250	9/2	5/8	0	0	125/4	0

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

Або

Х * = (0; 0; 250; 25; 0; 525);

.

Розв'язування подвійної задачі

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

min F = max Z = 6250.

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

Отже,

min F = 150 0 + 200 31,25 + 600 0 = 6250.

Дефіцитність ресурсів

Статус ресурсів прямої задачі можна визначити трьома способами. Перший -- підстановкою Х * у систему обмежень прямої задачі. Якщо обмеження виконується як рівняння, то відповідний ресурс дефіцитний, у противному разі -- недефіцитний.

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

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

у1 = 0 (ресурс 1 недефіцитний);

у2 = 31,25 (ресурс 2 дефіцитний);

у3 = 0 (ресурс 3 недефіцитний).

Види нерентабельної продукції

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

Підставимо Y * у систему обмежень двоїстої задачі. Якщо вартість ресурсів на одиницю продукції (ліва частина) перевищує ціну цієї продукції (права частина), то виробництво такої продукції для підприємства недоцільне. Якщо ж співвідношення виконується як рівняння, то продукція рентабельна.

Аналіз на чутливість величини прибутку при зміні ресурсів

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

Приріст (зміну) запасу ресурсу 2 позначимо b2. Тоді, якщо , то новий оптимальний план

Х* = (0; 0; 250 + 5/4b2; 25 - 5/8b2; 0; 525 - 3/8b2).

Єдина вимога, яку можна поставити до можливих нових оптимальних значень, -- це умова невід'ємності, тобто

.

Це означає, що коли запас ресурсу 2 збільшиться на 40 ум. од. або зменшиться на 200 ум. од., то оптимальною двоїстою оцінкою ресурсу 2 залишиться у2 = 125/4. Отже, запас ресурсу 2 може змінюватись у межах

,

.

Згідно з цим максимально можливий дохід підприємства перебуватиме в межах

,

.

Завдання 2

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

	1	2	3	4	5
1	10/5	-	12/6	13/6	11/5	1400
2	14/7	16/8	-	15/6	14/7	2000
3	8/6	-	11/5	14/7	8/6	1500
4	11/5	14/7	18/9	-	19/8	2200
	120	100	170	230	120

,

Оптимальний план: ; ; ; ; ; ; .

За початковими даними згідно з варіантом завдань:

побудувати математичну модель;

розписати план розподілу виробів по видах обладнання згідно з оптимальним планом;

визначити сумарну собівартість виготовлення всіх виробів;

визначити коефіцієнт завантаження кожного типу обладнання;

визначити оптимальний парк обладнання для виконання програми підприємства;

скласти список невживаного обладнання.

Розв'язування

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

Визначимо через - кількість - ого виду виробів, що виготовляються на

-му виді обладнання. Мета задачі - мінімізація сумарної вартості. Цільова функція

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

Оскільки вся програма повинна бути виконана, то незалежно від того, на якому виді обладнання виготовляються вироби, їх повинно бути виготувано стільки, скільки необхідно згідно з програмою.

Таким чином:

і звичайна вимога невід'ємності шуканих величин .

Оптимальне рішення задачі таке. Значення цільової функції задачі . Розподіл видів по видах обладнання: ; ; ; ; ; ; .

На першому виді обладнання виготовляються вироби третього та четвертого типів в обсязі 14 од. і 219,3 од. відповідно.

На другому виді обладнання виготовляється вироби четвертого типу в обсязі 10,7 од.

На третьому - виготовляється третій тип виробів в обсязі 156 і п'ятий тип виробів в обсязі 120 од.

На четвертому виді обладнання виготовляється перший тип виробів в обсязі 120, другий тип в обсязі 100 од.

Перший тип обладнання працює 1399,8 верстато-год;

другий вид обладнання працює 64,2 верстато-год;

третій вид обладнання працює 1500 верстато-год;

четвертий вид обладнання працює 1300 верстато-год.

Коефіцієнти завантаження обладнання такі:

; ; ; .

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

Визначимо оптимальну кількість верстатів для виконання програми. Нехай фонд корисного часу одного верстата становить 100 верстато-год для будь-якого виду обладнання.

Тоді

; ; ; .

Завдання 3

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

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

	1	2	3	4	5
1	11	2	3	5	1	270
2	5	6	3	4	3	420
3	7	9	2	6	9	160
4	1	7	4	1	3	130
	100	120	80	300	150	980

За початковими даними згідно з варіантом завдань:

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

привести до канонічного вигляду;

визначити опорний план будь-яким методом;

визначити оптимальний план методом потенціалів.

Використовуючи результати розв'язання транспортної задачі, визначити:

дійсні пункти виробництва;

дійсні обсяги виробництва;

план перевезень продукції з вказівкою прикріплення споживачів до постачальників і об'ємів перевезень;

вартість усіх перевезень.

Розв'язування

Побудова математичної моделі. Нехай хij -- кількість одиниць однорідного продукту, яку перевозять з і-го пункту виробництва до j-го споживача (; ). Тоді економіко-математична модель поставленої задачі має такий вигляд:

Z = 11x11 + 2x12 + 3x13 + 5x14 + x15 + 5x21 + 6x22 + 3x23 + 4x24 + 3x25

+ 7x31 + 9x32 + 2x33 + 6x34 + 9x35 + x41 + 7x42 + 4x43 + x44 + 3x45 min,

за обмежень

Знак «?» у перших п'ятьох обмеженнях задачі пояснюється тим, що за умовою транспортна задача є відкритою:

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

Щоб визначити оптимальний план поставленої задачі, її необхідно збалансувати, тобто звести до закритого типу. Це виконується шляхом уведення додаткового, умовного споживача B6 із попитом B5 = 980 - 750 = 230 од. Вартість перевезення одиниці продукції до умовного споживача дорівнює нулю.

Перший опорний план транспортної задачі побудуємо методом мінімального елемента.

		11	2 120	3	5	1 150	0 0	270
		5	6	3	4 270	3	0 150	420
		7	9	2 80	6	9	0 80	160
		1 100	7	4	1 30	3	0	130
	100	120	80	300	150	230	980

Умова оптимальності для цього опорного плану виконується, і тому можна записати:

;

Zmin = 2 120 + 1 150 + 3 0 + 4 270 + 0 150 + 2 80 + 0 80 + 1 100 + 1 30 = 1760 ум. од.

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

Загальна вартість усіх перевезень буде становитиме 1760 ум. од.

Завдання 4

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

	1	2	3	4
1		1	3	2	10
2	2		5	3	12
3	5	4		6	8
4	8	7	4		14

За початковими даними згідно з варіантом завдань:

побудувати математичну модель як модель задачі про комівояжера;

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

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

записати оптимальну послідовність запуску деталей.

модель прибуток задача комівояжер

Розв'язування

Математична модель задачі:

, ,

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



	1	2	3	4	Мінімальний елемент
1		1	3	2	1
2	2		5	3	2
3	5	4		6	4
4	8	7	4		4

- мінімальні відстані в кожному рядку

Сформуємо матрицю

		1	2	3	4
	1		0	2	1
=	2	0		3	1
	3	1	0		2
	4	4	3	0

- мінімальні відстані в кожному стовпчику

Сформуємо матрицю .

		1	2	3	4
	1		0	2	0
=	2	0		3	0
	3	1	0		1
	4	4	3	0

- оцінка множини варіантів

Довжина дороги об'їзду не може бути меншою ніж 14 одиниць.

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

.

Максимальну оцінку має пара (4,3). Оцінка .

Викреслимо четвертий рядок і третій стовпець. Заборонимо переїзд із 3 в 4.

Отримаємо матрицю.

	1	2	4
1		0	0
2	0		0
3	1	0

- мінімальні відстані в кожному рядку

Сформуємо матрицю

		1	2	4
	1		0	0
=	2	0		0
	3	0	0

Виберемо підмножину для подальшого гілкування. Порівнюємо оцінки і , тобто порівнюємо 13 і 14. Виберемо підмножину . Вершині відповідає остання матриця , оскільки всі .

Оцінимо знову всі нульові елементи: .

.

Можна обирати будь-яку пару для продовження.

Виберемо пару (1,2). .

Викреслимо перший рядок і другий стовпець. Заборонимо переїзд із 2 в 1.

Сформуємо матрицю

	1	4
2	0	0
3	0

- мінімальні відстані в кожному рядку

Сформуємо матрицю

		1	4
=	2	0	0
	3	0

.

Очевидні переїзди (2,4) і (3,1).

Довжина дороги 13. Цикл переїзду .

Перевіримо довжину дороги, виходячи з початкової матриці переїздів.

.

Отже, загальний час на переобладнання 13 часових одиниць.

Рис.1 - Дерево розв'язання

Загальний час на переобладнання та виконання операцій h=10+12+8+14=44.

Размещено на http://allbest.ru

Рис. 2. - Оптимальна послідовність обробки деталей.

Размещено на Allbest.ru

...