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

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

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=CijVj . При цьому один з рядків або один з стовпчиків отримує довільну оцінку, а оцінки останніх рядків і стовпчиків треба розрахувати за вказаними формулами.

Нехай 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.

Tagged with: , ,
Posted in Математичні моделі в розрахунках на еом
Перелік предметів:
  1. Інформаційні технологіі в галузі
  2. Інформаційні технологіі в системах якості стандартизаціісертифікаціі
  3. Історія української культури
  4. Бухоблік у ресторанному господарстві
  5. Діловодство
  6. Мікропроцесорні системи управління технологічними процесами
  7. Науково-практичні основи технологіі молока і молочних продуктів
  8. Науково-практичні основи технологіі м’яса і м’ясних продуктів
  9. Організація обслуговування у підприємствах ресторанного господарства
  10. Основи наукових досліджень та технічноі творчості
  11. Основи охорони праці
  12. Основи підприємницькоі діяльності та агробізнесу
  13. Політологія
  14. Технологічне обладнання для молочноі промисловості
  15. Технологічне обладнання для м’ясноі промисловості
  16. Технологічний семінар
  17. Технологія зберігання консервування та переробки молока
  18. Технологія зберігання консервування та переробки м’яса
  19. Технологія продукціі підприємств ресторанного господарства
  20. Технохімічний контроль
  21. Технохімічний контроль
  22. Управління якістю продукціі ресторанного господарства
  23. Вища математика 3к.1с
  24. Вступ до фаху 4к.2с.
  25. Загальні технології харчових виробництв
  26. Загальна технологія харчових виробництв 4к.2с.
  27. Мікробіологія молока і молочних продуктів 3к.1с
  28. Математичні моделі в розрахунках на еом
  29. Методи контролю харчових виробництв
  30. Основи фізіології та гігієни харчування 3к.1с
  31. Отримання доброякісного молока 3к.1с
  32. Прикладна механіка
  33. Прикладна механіка 4к.2с.
  34. Теоретичні основи технології харчових виробництв
  35. Технологія зберігання, консервування та переробки м’яса
  36. Фізика
  37. Харчові та дієтичні добавки
  38. Фізичне виховання 3к.1с

На русском

  1. Методы контроля пищевых производств
  2. Общая технология пищевых производств
  3. Теоретические основы технологий пищевых производств
  4. Технология хранения, консервирования и переработки мяса
LiveInternet