Знаходження оптимального плану тз методом потенціалів

Знаходження оптимального плану ТЗ методом потенціалів.

1. Знаходження оптимального плану ТЗ методом потенціалів

1. В пунктах відправлення А1, А2, А3, …. знаходиться однорідний вантаж в кількості a1, а2, а3, …. відповідно, який необхідно перевезти в пункти призначення В1, В2, В3, …. , потреба кожного з яких становить b1, b2, b3, …. . Відома відстань між пунктами перевезень (оцінки).

Маємо три постачальника з такими запасами вантажу:

А1 = 26 т, А2 = 33 т, А3 = 45 т;

і чотири споживача з потребою на цей вантаж:

В1 = 14 т,

В2 = 19 т, В3 = 20 т, В4 = 5 т.

Відома відстань між пунктами перевезень.

Відстань між пунктами перевезень, км (Сij).

Постачальники	Споживачі
B1	B2	B3	B4
A1	6	4	15	19
A2	13	17	28	3
A3	5	20	6	10

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

Рішення.

Задача, в якій загальні запаси дорівнюють загальним потребам називається закритою транспортною задачею:

– загальні запаси = 26+33+45 = 104 т;

– загальні потреби = 14+19+20+5 = 58 т.

Отже задача відкрита, тому необхідно ввести фіктивного споживача, якому слід перевезти Вфікт = 104–58 = 46 т.

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

Першу транспортну таблицю заповнимо методом північно-західного кута

При такому плані перевезень загальна кількість тонно-кілометрів буде становити:

Fmin=14*6+12*4+7*17+20*28+5*3+1*0+45*0=826 т-км.

За допомогою методу потенціалів можна визначити оптимальний план транспортної задачі. Задача має оптимальне значення, коли сума потенціалів в усіх клітинах таблиці не перевищує оцінок, тобто при рішенні задачі на мінімум план вважається оптимальним в тому випадку, якщо для всіх вільних клітинок дотримується вимога: Ui +Vj £Cij, а для зайнятих Ui +Vj =Cij.

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

Ui +Vj =Cij

Де: Cij – оцінка клітинки;

I – рядки (I = 1, 2, … , M),

J – стовпчики ( J=1, 2, … , H)

Ui – оцінка I–го рядка (I = 1, 2, … M)

Vj – оцінка J–го стовпця (J = 1, 2, … H)

Тобто, якщо відомий потенціал Ui, То Vj=Cij–Ui, а якщо відомий Vj, то Ui=Cij – Vj . При цьому один з рядків або один з стовпчиків отримує довільну оцінку, а оцінки останніх рядків і стовпчиків треба розрахувати за вказаними формулами.

Нехай U1 =0, тоді потенціали першого та другого стовпчиків будуть становити:

V1=C11 –U1 = 6-0 = 6 для В1

V2=C12 –U1 = 4-0 = 4 для В2

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

U2 = C22 – V2 = 17 – 4 = 13

Визначимо потенціали для В3 , В4 І Вфікт:

V3=C23 –U2 = 28 – 13 = 15 для В3

V2=C24 –U2 = 3 – 13 = -10 для В4

V2=C25 –U2 = 0 – 13 = -13 для Вфікт

Тепер можна визначити потенціал А3:

U3 = C35 – V5 = 0 – (-13) = 13

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

Для Х13 сума потенціалів U1 + V3 = 0 + 15 = 15, що £ 15

Для Х14 сума потенціалів U1 + V4 = 0 + (-10) = -10, що £ 19

Для Х15 сума потенціалів U1 + V5 = 0 + (-13) = -13, що£ 0

Для Х21 сума потенціалів U2 + V1 = 13 + 6 = 19, що > 13

Для Х31 сума потенціалів U3 + V1 = 13 + 6 = 19, що > 5

Для Х32 сума потенціалів U3 + V2 = 13 + 4 = 17, що £ 20

Для Х33 сума потенціалів U3 + V3 = 13 + 15 = 28, що > 6

Для Х34 сума потенціалів U3 + V4 = 13 + (-10) = 3, що £ 10

Отже, даний план перевезень не є оптимальним, тому що в клітинках Х21, Х31, Х33 не виконується вимога Ui + Vj £ Cij. Необхідно перейти до наступного плану.

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

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

Клітини, які ввійшли до фігури перерахунку позначаються по черзі знаками “+”, “-”,”+”, “-”, … , починаючи з клітини перерахунку.

Заповнюється нова транспортна таблиця:

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

–  для клітин фігури перерахунку: кількість вантажу в клітинках зі знаком “+” збільшується, а в клітинках зі знаком “-“ зменшується на одну і ту ж величину, а саме, на найменшу кількість вантажу у клітинках, позначених знаком “-“.

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

При такому плані перевезень загальна кількість тонно-кілометрів буде становити:

FMin=14*6+12*4+7*17+5*3+21*0+20*6+25*0=386 т-км.

Вибирається клітина Х31, починаючи з неї будується фігура перерахунку.

Наступна транспортна таблиця має вигляд:

При такому плані перевезень загальна кількість тонно-кілометрів буде становити:

FMin=7*6+19*4+5*3+28*0+7*5+20*6+18*0=288 т-км.

Даний план перевезень не є оптимальним, тому що в клітинці Х15 не дотримується вимога оптимальності Ui + Vj £ Cij. Побудуємо фігуру перерахунку та розрахуємо нову таблицю.

Малюємо фігуру перерахунку та розрахуємо нову таблицю.

Поста-чальники	Споживачі	Запаси	Потенціали, Ui
В1	В2	В3	В4	Вфіктивний
A1		6		4		15		19		0	26	0
		19						7
A2		13		17		28		3		0	33	0
						5		28
A3		5		20		6		10		0	45	0
14				20				11
Потреба	14	19	20	5	46	104
Потенціали, VJ	5	4	6	3	0

При такому плані перевезень загальна кількість тонно-кілометрів буде становити:

FMin=7*6+19*4+5*3+28*0+7*5+20*6+18*0=281 т.-км.

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

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

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

–  з пункту А1 необхідно перевезти 19тон в пункт В2 та 7тон в пункт Вфікт;

–  з пункту А2 необхідно перевезти 5тон в пункт В4 та 28тон в пункт Вфікт;

–  з пункту А3 необхідно перевезти 14тон в пункт В1, 20тон в пункт В3 та 11тон в пункт Вфікт.

2. Термінологічний словник

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

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

При розв’язанні задачі на мінімум План вважається оптимальним в тому випадку, якщо для всіх вільних клітинок дотримується вимога: Ui +Vj £Cij, а для зайнятих Ui +Vj =Cij.

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

Ui +Vj =Cij

Де: Cij – оцінка клітинки;

I – рядки (I = 1, 2, … , M),

J – стовпчики ( J=1, 2, … , H)

Ui – оцінка I–го рядка (I = 1, 2, … M)

Vj – оцінка J–го стовпця (J = 1, 2, … H)

3. Рекомендована література

1. Исследование операций в экономике: Учебн. пособие для вузов/ Н. Ш.Кремер, Б. А.Путко, И. М.Тришин. М. Н.Фридман; Под ред. проф. Н. Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 1997.

2. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. – М.: Высш. шк., 1986.

3. Бугір М. К. Математика для економістів. Лінійна алгебра, лінійні моделі: Навч. посіб. – К.: ВЦ «Академія», 1998.

4. Гвоздинський А. М. Оптимізаційні задачі в організаційному управлінні: Навч. посіб.-Харків: ХДТУР, 1997.

5. Гетманцев В. Д. Лінійна алгебра і лінійне програмування:

Навч. посіб. – К.: Либідь, 2001.

6. Григорків B. C., Бойчук М. В. Практикум з математичного програмування: Навч. посіб. – Чернівці: Прут, 1995.

7. Деордица Ю. С., Савченко В. Т. Компьютерные технологии в экономике и менеджменте: Учеб. пособие. – Луганск: ВУГУ, 1999.

8. Зайченко Ю. П. Дослідження операцій: Підручник. – К.:

ВШОЛ, 2000.

9. Исследование операций в экономике: Учеб. пособие / Под ред. Н. Ш. Кремера. – М.: ЮНИТИ, 1999.

10. Кігель В. Р. Елементи лінійного, цілочислового лінійного, нелінійного програмування: Навч. посіб. – К.: ІСДО, 1995.

11. Мазаракі А. А., Толбатов Ю. А. Математичне програмування в Ехсе1:Навч. посіб. – К.: Четверта хвиля, 1998.

12.Романюк Т. П., Терещенко Т. А., Присенко Г. В., Городкова І. М. Математичне програмування: Навч. посіб. – К.: ІЗМН, 1996.

13.Цегелик Г. Г. Лінійне програмування: Навч. посіб. – Львів: Світ, 1995.

14.Экономико-математические методы и прикладные модели: Учеб. пособие / Под ред. В. В. Федосеева. – М.: ЮНИТИ, 1999.

15.Крушевський А. В. Справочник по экономико-математическим моделям и методам. – К.: Техника, 1982, – 208 с.

Іб. Вивальнюк Л. М. Елементи лінійного програмування. – К.: Вищашк., 1975,-191 с.

17. Шуенкин В. А., Жуков И. А. Основы математического программирования. – К.: КМУГА, 1999, – 306 с.

18. Ляшенко И. Н. Линейное и нелинейное программирование. – і К.: Вищашк., 1975,-371 с.

19. Богаєнко І. М., Григорків B. C., Бойчук М. В., Рюмашин М.0. Математичне програмування: Навч. посіб. – К.: Логос, 1996.

Ви прочитали: "Знаходження оптимального плану тз методом потенціалів"
Читати далі