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

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

С=

Попередній етап:

1) знаходимо максимальні значення в кожному стовпчику, а саме: 8,10,6,4,6. Віднімаємо від них елементи відповідного стовпчика;

2) з кожного рядка одержаної матриці віднімаємо мінімальний елемент цього рядка.

min

С=

max

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

С=

Ітерація 1

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

С=

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

Ітерація 2.

Серед невикреслених елементів матриці знаходимо найменше значення і віднімаємо це значення від не викреслених елементів і додаємо це значення до елементів, які стоять на перехресті ліній. Найменше значення даної матриці – 2.

С= ітерація 2

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

В даній матриці всі рядки і стовпці мають по одному нулю з зірочкою. Процес вирішення задачі закінчено.

В результаті вирішення задачі ми можемо зробити висновок про те, що для досягнення максимальної ефективності (найбільшої продуктивності), оптимальним варіантом призначення працівників на виконання певного виду роботи буде наступний: х₁₂=х₂₅=х₃₁=х₄₃=х₅₄=1, всі інші х_ij=0. Тобто перший виконавець призначається на виконання другого виду роботи, другий – для п’ятого виду роботи, третій – для першого виду роботи, четвертий – для третього виду роботи, а п’ятий – для четвертого виду роботи. Сумарна продуктивність складає 8+6+8+4+4=30 умовних одиниць.

Лабораторна робота №9

Тема: логістика запасів

Мета вирішення задачі. Визначити тип логістичної системи управління запасами та розрахувати параметри заданої системи управління.

Постановка задачі. Річна потреба потреба в матеріалах становить N-кількість штук. Кількість робочих днів за період, що розглядається – Т днів. Оптимальний розмір замовлення – n штук. Час поставки становить t днів, можлива затримка – t^*. Визначити параметри заданої системи управління запасами та змоделювати графічно роботу такої системи.

Вихідні дані:

N	n	T	t	t*

 

Тип системи: з фіксованим інтервалом часу між замовленнями

Режим роботи системи: МЗ-БЗ-БЗ-БЗ

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

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

РЗ=МБР – ПЗ+ОС

де РЗ – розмір замовлення;

МБЗ – максимально бажаний рівень запасу;

ПЗ – поточний запас, шт;

ОС – очікуване споживання за час постачання, шт.

Інтервал часу між замовленнями визначається:

І= Т*ОРЗ/N (1.1)

І- інтервал часу між замовленнями, дні

Т- кількість робочих днів за період, що розглядається, дні

ОРЗ- оптимальний розмір замовлення, шт.

N- потреба, шт..

 

1. Визначаємо параметри системи:

Табл.2.1

	№	Показник	Порядок розрахунку
	Потреба, шт.
	Інтервал між замовленнями, дні	Формула 1.1
	Час постачання, дні
	Можлива затримка в постачанні, дні
	Очікуване добове споживання, шт./доба*	[1]/[число роб.днів.]
	Очікуване споживання за час доставки, шт.	[3]*[5]
	Максимальне споживання за час постачання, шт.	([3]+[4])*[5]
	Гарантійний запас, шт.	[7]-[6]
	Максимально бажаний запас, шт.	[8]+[2]*[5]

 

Розрахунок параметрів системи управління запасами з фіксованим інтервалом між замовленнями:

Табл.2.2

№	Показник	Порядок розрахунку
	Потреба, шт.
	Інтервал між замовленнями, дні
	Час постачання, дні
	Можлива затримка в постачанні, дні
	Очікуване добове споживання, шт./доба*
	Очікуване споживання за час доставки, шт.
	Максимальне споживання за час постачання, шт.
	Гарантійний запас, шт.
	Максимально бажаний запас, шт.

 

3. Моделюємо графічно роботу даної системи управління запасами (див. рис. 5.9 та Анікіна «Практикум з логістики», с.152-166)

 

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

 

Лабораторна робота №10

Тема: задача про комівояжера.

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

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

Завдання до виконання

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

1. Розрахунок нижньої межі (оцінки).

2. Утворення підмножин (тобто гілкування).

3. Перерахунок оцінок.

4. Знаходження рішення.

5. Визначення ознаки оптимальності.

6. Оцінка точності наближеного рішення.

Необхідно мінімізувати вираз:

При цьому введені такі обмеження:

j=1,2…n;

i=1,2…n;

,

–довільні значення.

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

Розв’язання задачі.

Вихідна матриця має наступний вигляд:

n
	–
		–
			–
				–
					–
						–

 

1. Виконуємо редукцію рядків А_і , найменше значення в рядку та редукцію колонок B_j,найменше значення колонок. Отримуємо матрицю наступного вигляду:

 

 

n							Ai
	–
		–
			–
				–
					–
						–
Bj

 

 

2. Розраховуємо найнижчу можливу межу функції мети.

F min=Σ Ai +Σ Bi= 12+ 6+15+15+12+3+6+3+12+15+9+12=120

Отже, шукана найкоротша відстань F₀ має бути меншою або дорівнювати F_min.

3. На наступному етапі визначаємо штрафи рядків і колонок. Штраф рядку а_і буде дорівнювати мінімальному значенню оцінки і -рядку після першого нуля. Аналогічно знаходимо штрафи колонок b_j – мінімальне значення в колонках після 0.

n							ai
	–
		–
			–
				–
					–
						–
bj

4. Знаходимо значення вторинного штрафу у клітинках, які містять 0. Ф_ij=a_i+b_j. З цих значень вишукуємо максимальне значення Ф_ij.

 

 

n				4			ai
	-				018
	018	-
3		018	-	024	015
	012		015	-
		015	015		-	018
		015				-
bj

Ф₃₄ =24 – вказує на те,що в маршрут комівояжера треба ввести клітинку (3-4)­ – це є базова клітинка, з якої починається процес гілкування у розрахунках і котра вилучається з подальших обчислень.

5. Вилучивши 3 рядок та 4 колонку,залишається матриця 5×5. Знову визначаємо штрафи рядків і колонок а_і та b_j та знаходимо вторинні штрафи.

n						ai
1	-	021		018
	018	-
	012		-
		015	015	-
		015			-
Bj

Ф₂₁ =21 – вказує на те,що в маршрут комівояжера треба ввести клітинку (2-1)­.

6. Вилучивши 2 рядок та 1 колонку,залишається матриця 4×4. Аналогічно пунктам 3,4 проводимо обчислення та отримуємо наступну матрицю.

n					ai
	-
	012	-
5		015	-	021
				-
bj

Ф₅₆ =21 – вказує на те,що в маршрут комівояжера треба ввести клітинку (5-6)­.

7. Вилучаємо 5 рядок та 4 колонку, вже залишається матриця 3×3.

Знову повторюємо пункти 3,4, проводимо обчислення та отримуємо наступну матрицю.

n				ai
	-
	018	-
			-	-
Bj

 

 

 

Ф₄₁=18 – вказує на те,що в маршрут комівояжера треба ввести клітинку (4-1)­.

8. Вилучаємо 1 рядок та 3 колонку і залишається кінцева матриця 2×2.

n			ai
	-
		-
bj

З цієї матриці ми вилучаємо останні дві незаборонені клітинки (3-6) та (2-5).

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

(1-2) – (2-5) – (5-6) – (6-3) – (3-4) – (4-1)

10. Знаходимо мінімальний шлях F₀, який дорівнює сумі відстаней, що вказані у вихідній матриці у тих клітинках,що є оптимальним шляхом.

n
	–
		–
			–
				–
					–
						–

 

Отже, F₀=15+12+12+15+18+12=84. Знайдене F₀< , розрахованому вище.