Типове розв’язання Т.З

Є три постачальники і чотири споживачі однорідного продукту. Потужності постачальників і попити споживачів, а також витрати на перевезення одиниці вантажу для кожної пари «постачальник-споживач» зведені в таблицю 3 постачань.

Таблиця 3

	Споживачі	Потужність постачальників ai
B1	B2	B3	B4
Постачальники	A1
A2
A3
Попит bj

Задача у наступному: знайти об'єми перевезень для кожної пари «постачальник-споживач» так, щоб:

1) потужності всіх постачальників були реалізовані;

2) попити всіх споживачів були задоволені;

3) сумарні витрати на перевезення були мінімальні.

Поставлено збалансовану транспортну задачу, оскільки сумарний попит дорівнює сумарній потужності постачальників ® 280.

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

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

					ai
bj

Знаходимо в таблиці клітинки з найменшим тарифом. Таких клітин дві- (1;1) і (2;1) із тарифом, що дорівнює 1. Порівнюємо максимально можливі постачання для цих клітинок: для клітинки (1;1) x₁₁=min{60,20}=20, для клітинки (2;1) x₂₁=min{120,20}=20. Оскільки їх значення збігаються, то максимально можливе постачання записуємо в будь-яку з них. Наприклад, записуємо постачання, що дорівнює 20 од. у клітинку (2;1). У результаті попит першого споживача задоволений і перший стовпець таблиці постачань випадає з наступного розгляду, а виробничу потужність для другого рядка зменшуємо на 20 од. Аналогічним способом продовжуємо заповнювати невикреслені клітинки таблиці. У останній клітинці попит і пропозиція повинні збігтися, оскільки розглядається збалансована задача. Слід зазначити, що в таблиці повинна бути заповнена n+m-1 клітинка перевезень

(де n - число постачальників, m- число споживачів).

Наприклад, для розглянутої задачі повинно бути заповнено 3+4-1=6 клітин. Остаточно одержуємо початковий опорний план перевезень.

Тепер скористаємося методом потенціалів. Для цього кожному стовпцю припишемо потенціал v_j, а кожному рядку - потенціал u_i. Для кожної заповненої клітини складемо лінійне рівняння за правилом u_i+v_j=c_ij, де c_ij - тариф відповідного перевезення. Потім розв’яжемо систему 6-ти рівнянь.

					ai
V1	V2	V3	V4
	U1
	U2
	U3
bj

Оскільки в рівняннях буде 7 невідомих (3 потенціали u і 4 потенціали v), то довільний потенціал можна дорівняти до нуля.

Тепер для кожної незаповненої клітинки необхідно знайти оцінку Dij= ui+vj-cij. Якщо всі оцінки будуть негативними або нульовими, то початковий опорний план є оптимальним.

D₁₁=-1+3-1=2; D₁₃=-1+7-5=1; D₁₄=-1+4-3=0; D₂₂=-2+3-6=-5; D₂₃=-2+7-5=0; D₃₁=0+3-6= -3. Оцінки D₁₁ і D₁₃ позитивні, отже, отримане початкове опорне розв’язання не оптимальне. З оцінок вибираємо найбільшу - D₁₁, отже, у клітинку (1;1) будемо заносити ненульове перевезення. Заносимо в клітинку (1;1) знак «+» і будуємо ланцюг потенціалів, що може проходити тільки по заповнених клітинках, із чергуванням знаків «+» і «-» і повертається у вихідну незаповнену клітину.

					ai
V1	V2	V3	V4
	U1
+		-
	U2
-						+
	U3
		+				-
bj

Перевіряємо отриманий опорний план на оптимальність. D13=1; D14=-1; D22= -4; D23=1; D31= -4; D34= -1

Cеред клітинок, позначених мінусом, вибираємо ту, що містить найменше перевезення. У подальших обчисленнях ця клітинка буде вважатися незаповненою. Далі вміст вибраної клітинки додаємо до вмісту клітинок, що позначені «+», і віднімаємо з клітинок, що позначені «-».У таблиці повинна виявитися, як і раніше, n+m-1 заповнена клітинка.

			3	4	ai
V1	V2	V3	V4
	U1
		-		+
	U2
	U3
		+		-
bj

Перевіряємо отриманий опорний план на оптимальність. D14= -1; D22= -4; D23= 0; D31= -4; D33= -1; D34= -1

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

					ai
V1	V2	V3	V4
	U1
	U2
	U3
bj

Оскільки серед оцінок немає позитивних, можна сказати, що отриманий опорний план є оптимальним, але не єдиним (D₂₃= 0).

У підсумку підприємствам можна запропонувати наступний план перевезень:

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

ден. ед.

Питання по темі

1. Постановка транспортної задачі (Т.3.).

2. Математична модель Т.3.

3. Умова збалансованості Т.3.

4. Зв'язок Т.3. с задачею лінійного програмування (З.Л.П.)

5. Визначення розв’язання (плану) Т.3.

6. Умова можливості розв'язання Т.3.

7. Визначення опорного плану Т.3.

8. Вродженість і невиродженість опорного плану.

9. Зв'язок виродженості й невиродженості опорного плана Т.3. сіз заповнюванням таблиці Т.3.

10. Визначення циклу в таблиці Т.3.

11. Зв'язок опорного плану Т.3. з циклічністю.

12. Метод північно-західного кута для визначення початкового опорного плану.

13. Метод мінімального елемента.

14. Метод фогеля.

15. Суть методу потенціалів.

16. Вимоги до опорності плану при застосуванні методу потенціалів.

Завдання для контрольних і самостійних робіт

Є три постачальники і чотири споживачі однорідного продукту. Потужності постачальників і попити споживачів, а також витрати на перевезення одиниці вантажу для кожної пари «постачальник-споживач» зведені в таблицю 4 постачань.

Задача у наступному: знайти об'єми перевезень для кожної пари «постачальник-споживач» так, щоб:

1) потужності всіх постачальників були реалізовані;

2) попити всіх споживачів були задоволені;

3) сумарні витрати на перевезення були мінімальні.

Дані для розв’язання транспортной задачі.

Таблиця 4

1 a:={200, 270, 130} b:={120, 80, 240, 160}	16 a:={25, 25, 50} b:={15, 15, 40, 30}
2 a:={110, 190, 90} b:={80, 60, 170, 80}	17 a:={40, 27, 23} b:={30, 25, 15, 20}
3 a:={160, 140, 60} b:={80, 80, 60, 140}	18 a:={15, 58, 35} b:={30, 23, 35, 20}
4 a:={115, 145, 100} b:={70, 220, 40, 30}	19 a:={90, 60, 90} b:={24, 40, 80, 96}
5 a:={180, 100, 120} b:={110, 90, 120, 80}	20 a:={16, 28, 30} b:={22, 18, 13, 21}
6 a:={100, 150, 50} b:={75, 80, 60, 85}	21 a:={30, 25, 50} b:={15, 15, 45, 30}
7 a:={45, 85, 20} b:={40, 30, 30, 50}	22 a:={50, 27, 23} b:={35, 30, 15, 20}
8 a:={50, 40, 20} b:={33, 22, 39, 16}	23 a:={25, 58, 35} b:={40, 23, 35, 20}
9 a:={35, 85, 60} b:={20, 60, 55, 45}	24 a:={85, 55, 90} b:={24, 40, 80, 86}
10 a:={16, 24, 30} b:={32, 14, 14, 10}	25 a:={20, 28, 30} b:={22, 18, 17, 21}
11 a:={180, 60, 80} b:={120, 40, 80, 80}	26 a:={100, 270, 130} b:={120, 80, 240, 60}
12 a:={80, 90, 70} b:={80, 50, 70, 40}	27 a:={110, 90, 60} b:={80, 60, 70, 50}
13 a:={75, 200, 220} b:={180, 120, 90, 105}	28 a:={150, 140, 60} b:={70, 80, 60, 140}
14 a:={130, 80, 160} b:={70, 60, 120, 120}	29 a:={65, 85, 30} b:={50, 40, 30, 60}
15 a:={160, 140, 170} b:={120, 50, 190, 110}	30 a:={180, 200, 20} b:={110, 90, 120, 80}

Задача вибору або задача про призначення.

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

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

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

Побудуємо математичну модель задачі.

Нехай x _ij=1 це розробка i-им конструктором j-го вузла машини,а x _ij=0 – це розробка i-им конструктором j-го вузла машини, с _ij – витрати часу на цю розробку, i,j=1,…,n.Тоді функцією мети L буде функція сумарних витрат на проектування всієї машини.

Математична модель має вигляд:

Функція мети min (max)

Система граничних умов:

3. , якщо i - й ресурс призначений на виконання j - й роботи; 0 - інакше.

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