У вас вопросы?
У нас ответы:) SamZan.net

ТЕМАХrdquo; для студентів напряму підготовки 6.

Работа добавлена на сайт samzan.net: 2016-03-13

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 12.4.2025

         МІНІСТЕРСТВО ОСВІТИ і НАУКИ,

         МОЛОДІ та СПОРТУ УКРАЇНИ

         НАЦІОНАЛЬНИЙ  ТРАНСПОРТНИЙ  УНІВЕРСИТЕТ

МЕТОДИЧНІ  ВКАЗІВКИ

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

“ДОСЛІДЖЕННЯ ОПЕРАЦІЙ

В ТРАНСПОРТНИХ СИСТЕМАХ”

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

«ТРАНСПОРТНІ ТЕХНОЛОГІЇ»

спеціальності 7.010102

«Організація перевезень і управління на транспорті

(автомобільний транспорт)»

(у рамках кредитно-модульної системи організації навчального процесу)

Київ НТУ 2012


Методичні  вказівки до виконання курсового проекту з дисципліни “Дослідження операцій в транспортних системах“ для студентів напряму підготовки 6.070101 “Транспортні технології” зі спеціальності 6.07010102 “Організація перевезень і управління на транспорті (автомобільний)”/ Укл. Г.С. Прокудін

Укладач: Прокудін Георгій Семенович

   

   

Відповідальний за випуск Г.С. Прокудін


1. ОПИС ДИСЦИПЛІНИ

Мета і завдання вивчення дисципліни

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

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

Це в повної мірі також стосується управлінню вантажними потоками в транспортних системах (ТС), аналізу яких і є призначеною дисципліна “Дослідження операцій в транспортних системах”. Зауважимо лише, що значна розмірність задач дослідження операцій стосовно транспортних процесів, а також певна специфіка функціонування ТС обумовили розвиток цілого ряду методів дослідження операцій, що є притаманними саме транспортним системам.

Проблеми аналізу і синтезу складних ТС можна розв’язати інтуїтивно, методом “спроб та помилок”, поступово наближаючись до задовільного їх функціонування, але цей процес удосконалення буде досить тривалим, пов’язаним з великими витратами часу і коштів , в той час як передчасне вивчення всього комплексу чинників, моделювання на ЕОМ різних варіантів розв’язування проблеми з метою вибору найбільш ефективних варіантів рішення з багатьох можливих дасть змогу вже на першому етапі вибрати якщо не оптимальне рішення, то рішення, що до нього наближається.

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

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

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

Предмет курсу передбачає отримання студентами теоретичної та практичної підготовки управління вантажними потоками в ТС.

Після вивчення цієї дисципліни студент має знати:

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

Студент повинен вміти:

  •  вибирати оптимальне (або близьке до нього) рішення певної транспортної проблеми серед множини можливих рішень;
  •  розв`язувати різноманітні транспортні задачі, пов`язані з перевезенням вантажів в заданих транспортних мережах;
  •  складати графіки призначення комплексу транспортних засобів з їх наступним поліпшенням або оптимізацією;
  •  визначати оптимальні складські запаси і режими їх транспортного обслуговування з урахуванням характеру дії основного виробництва;
  •   застосовувати сучасні програмні засоби для розв’язання  різних задач дослідження операцій в ТС.

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

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

Курс: другий, третій

Семестр: четвертий, п’ятий

Напрям, освітньо-кваліфікаційний рівень

Характеристика навчальної дисципліни

Кількість кредитів:

  •  національних – 4
  •  ECTS –  6

       

4 семестр

Кількість модулів: 2

Кількість змістових модулів: 5

5 семестр

Кількість модулів: 2

Кількість змістових модулів: 6

Загальна кількість годин:

216

„Транспортні технології”, бакалавр

Лекції:  51 год.

4 семестр –  34 год.

5 семестр –  17 год.

Практичні заняття: 53 год.

4 семестр – 17 год.

5 семестр – 36 год.

Самостійна робота:112 год.

4 семестр –  57 год.

5 семестр –  55 год.

Форма підсумкового контролю:

4 семестр – залік

5 семестр – екзамен

5 семестр – захист

                    курсового

                    проекту

2. ДИДАКТИЧНИЙ МАТЕРІАЛ

ДО ВИКОНАННЯ КУРСОВОГО ПРОЕКТУ

Завдання на курсовий  проект

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

Курсовий проект припускає роботу з матрично-мережевою моделлю (МММ) здійснення вантажних перевезень в транспортних системах. Робота з МММ включає наступні етапи:

  •  створення матриці транспортних кореспонденцій (матриці суміжності) для відповідної транспортної мережі (ТМ);
  •  зведення за допомогою методу найкоротших відстаней сітьового представлення перевезень вантажу на ТМ до табличного виду – транспортної таблиці (ТТ);
  •  побудову у ТТ одним з відомих методів опорного плану перевезень вантажу;
  •  знаходження одним з відомих методів оптимального плану перевезень вантажу на ТМ;
  •  побудову маршрутів транспортування вантажів у відповідності з оптимальним планом перевезень вантажу на ТМ;
  •  закріплення за отриманими у оптимальному плану перевезень вантажу на ТМ транспортними роботами рухомого складу.

У звіт по курсовому проекту включити наступне:

  •  теоретичні відомості про наступні методи – метод найкоротших відстаней на ТМ, метод побудови опорного плану перевезень вантажу, метод оптимального плану перевезень вантажу на ТМ, угорський метод розв’язання транспортної задачі про призначення;
  •  розв’язання на ТМ за допомогою одного з відомих методів знаходження оптимального плану перевезень вантажу;
  •  закріплення за отриманими у оптимальному плану перевезень вантажу на ТМ транспортними роботами рухомого складу;
  •  розрахунки на ПК за допомогою табличного процесора Microsoft Office Excel 2003(2007) задач розв’язання на ТМ за допомогою одного з відомих методів знаходження оптимального плану перевезень вантажу і  закріплення за отриманими у оптимальному плану перевезень вантажу на ТМ транспортними роботами рухомого складу.

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

  •    по номеру студента у журналі академічної групи вибирається структура ТМ (Додаток 1);
  •  по передостанньої цифрі у номері залікової книжки студента вибираються обсяги поставок і замовлень вантажу (Додаток 2);
  •   по останньої цифрі у номері залікової книжки студента вибираються вартості перевезення одиниці вантажу між сусідніми вузлами ТМ (Додаток 3);
  •  по номеру місяця народження студента вибирається метод побудови опорного плану перевезень вантажу, а саме:
  1.  – метод північна – західного кута;
  2.  – метод північна – східного кута;
  3.  – метод південна – західного кута;
  4.  – метод південна – східного кута;
  5.  – метод найменшого елемента строки ТТ;
  6.  – метод найменшого елемента стовпця ТТ;
  7.  – метод найменшого елемента ТТ;
  8.  – метод мінімального вузла відправлення вантажу ТТ;
  9.  – метод мінімального вузла призначення вантажу ТТ;
  10.  – метод мінімального вузла відправлення-призначення вантажу ТТ;
  11.  – метод випадкового заповнення (рандомизації);
  12.  – метод апроксимації Фогеля;
  •  метод оптимізації плану перевезень, а саме: симплексний метод (непарний номер студента у журналі академічної групи) або метод потенціалів (парний номер студента у журналі академічної групи);
  •  матриця П продуктивності виконання кожним з шості транспортних засобів кожної із шості транспортних робіт, яка використовується при виконанні завдання по закріпленню за отриманими у оптимальному плану перевезень вантажу на ТМ транспортними роботами рухомого складу, єдина для усіх студентів єдина і наведена у Додатку 4.

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

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

Аналіз наявних у вітчизняній і світовій практиці підходів до оптимізації перевезень пасажирів і вантажів у ТС виявив низку недоліків:

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

Більшу частини перерахованих вище недоліків по оптимальному плануванню і маршрутизації вантажних перевезень у ТС знято за допомогою використання  МММ представлення й управління вантажними перевезеннями на ТМ. Вирішення цього завдання має сприяти розв'язанню такої важливої проблеми національної економіки як підвищення ефективності управління вантажними перевезеннями у ТС України.

Розглянемо необхідні теоретичні відомості для  використання  МММ представлення й управління вантажними перевезеннями на ТМ.

3. МЕТОДИ ПОБУДОВИ ОПОРНИХ ПЛАНІВ ПЕРЕВЕЗЕНЬ ВАНТАЖУ

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

3.1. Метод північна – західного кута

Процес пошуку опорного плану перевезень у транспортної задачі розглянемо на конкретному прикладі. Відмітимо також, що всі без винятку спрощені методи розв’язання транспортної задачі базуються на транспортній таблиці (табл. 1).

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

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

Згідно таблиці 1 маємо:

m = 3; n = 4.

а1 = 100; а2 = 120; а3 = 140;

b1 = 80; b2 = 100; b3 = 110; b4 = 70.

Таблиця 1

Вихідна ТТ

B1

B2

B3

B4

Запаси

ai

A1

4

x11

7

x12

2

x13

5

x14

100

A2

3

x21

6

x22

1

x23

8

x24

120

A3

9

x31

3

x32

6

x33

2

x34

140

Заявки

bj

80

100

110

70

360

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

  1.  Задовольнимо  за рахунок А1, решту  відправимо до B2 (див. табл. 2). (Нижній індекс у обсягах перевезень показує черговість розподілу вантажу, а символ прочерку “–“ у деяких клітинках ТТ означає відсутність у них перевезень вантажу.);

Таблиця 2

ТТ з розподілом запасів А1

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

801

7

202

2

–

5

–

100

100-80=20

20-20=0

A2

3

–

6

1

8

120

A3

9

–

3

6

2

140

Заявки

bj

80

100

110

70

360

bj'

80-80=0

100-20=80

  1.  Оскільки В2 ще не задовольнили, додамо необхідний обсяг за рахунок  (ще 80); решту  відправимо до В3 (див. табл. 3);

Таблиця 3

ТТ з розподілом запасів А2

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

801

7

202

2

–

5

–

0

A2

3

–

6

803

1

404

8

–

120

120-80=40

40-40=0

A3

9

–

3

–

6

2

140

Заявки

bj

0

80

110

70

260

bj'

80-80=0

110-40=70

  1.  Щоб повністю задовольнити В3, додамо необхідний обсяг за рахунок А3 (ще 70). Решту  відправимо до В4, задовольнив таким чином його повністю (див. табл. 4).

Таблиця 4

ТТ з розподілом запасів А3

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

801

7

202

2

–

5

–

0

A2

3

–

6

803

1

404

8

–

0

A3

9

–

3

–

6

705

2

706

140

140-70=70

70-70=0

Заявки

bj

0

0

70

70

140

bj'

70-70=0

70-70=0

Підрахуємо кількість ненульових перевезень (зайнятих клітинок). Таких є 6, що відповідає обов'язкової умові (m + n – 1) = (3 + 4 – 1) = 6. Оскільки суми перевезень по рядах і колонках відповідають  і , отриманий план перевезень є можливим і опорним, тому що цей план є початковим. Для отриманого плану можливо підрахувати загальні витрати на здійснення всіх перевезень, тобто

умовних грошових одиниць (у.г.о.).

3.2. Метод північна – східного кута

Процес пошуку опорного плану перевезень за методом північна – східного кута розглянемо на тому же самому прикладі (див. табл. 1).

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

  1.  Задовольнимо  за рахунок А1, решту  відправимо до B3 (див. табл. 5). (Нижній індекс у обсягах перевезень показує черговість розподілу вантажу, а символ прочерку “–“ у деяких клітинках ТТ означає відсутність у них перевезень вантажу.);
  2.  Оскільки В3 ще не задовольнили, додамо необхідний обсяг за рахунок А2 (ще 80); решту  відправимо до В2 (див. табл. 6);
  3.  Щоб повністю задовольнити В2, додамо необхідний обсяг за рахунок А3 (ще 60). Решту  відправимо до В1, задовольнив таким чином його повністю (див. табл. 7).

Підрахуємо кількість ненульових перевезень (зайнятих клітинок). Таких є 6, що відповідає обов'язкової умові (m + n – 1) = (3 + 4 – 1) = 6. Оскільки суми перевезень по рядах і колонках відповідають  і , отриманий план перевезень є можливим і опорним, тому що цей план є початковим. Для отриманого плану можливо підрахувати загальні витрати на здійснення всіх перевезень, тобто

 у.г.о.

Таблиця 5

ТТ з розподілом запасів А1

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

302

5

701

100

100-70=30

30-30=0

A2

3

6

1

8

–

120

A3

9

3

6

2

–

140

Заявки

bj

80

100

110

70

360

bj'

110-30=80

70-70=0

Таблиця 6

ТТ з розподілом запасів А2

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

302

5

701

0

A2

3

–

6

404

1

803

8

–

120

120-80=40

40-40=0

A3

9

3

6

–

2

–

140

Заявки

bj

80

100

80

0

260

bj'

100-40=60

80-80=0

Таблиця 7

ТТ з розподілом запасів А3

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

302

5

701

0

A2

3

–

6

404

1

803

8

–

0

A3

9

806

3

605

6

–

2

–

140

140-60=80

80-80=0

Заявки

bj

80

60

0

0

140

bj'

80-80=0

60-60=0

3.3. Метод південна – західного кута

Процес пошуку опорного плану перевезень за методом південна – західного кута розглянемо на тому же самому прикладі (див. табл. 1).

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

  1.  Задовольнимо  за рахунок А3, решту  відправимо до B2 (див. табл. 8). (Нижній індекс у обсягах перевезень показує черговість розподілу вантажу, а символ прочерку “–“ у деяких клітинках ТТ означає відсутність у них перевезень вантажу.);
  2.  Оскільки В2 ще не задовольнили, додамо необхідний обсяг за рахунок А2 (ще 40); решту  відправимо до В3 (див. табл. 9);
  3.  Щоб повністю задовольнити В3, додамо необхідний обсяг за рахунок А1 (ще 30). Решту  відправимо до В4, задовольнив таким чином його повністю (див. табл. 10).

Таблиця 8

ТТ з розподілом запасів А3

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

2

5

100

A2

3

–

6

1

8

120

A3

9

801

3

602

6

–

2

–

140

140-80=60

60-60=0

Заявки

bj

80

100

110

70

360

bj'

80-80=0

100-60=40

Таблиця 9

ТТ з розподілом запасів А2

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

5

100

A2

3

–

6

403

1

804

8

–

120

120-40=80

80-80=0

A3

9

801

3

602

6

–

2

–

0

Заявки

bj

0

40

110

70

220

bj'

40-40=0

110-80=30

Підрахуємо кількість ненульових перевезень (зайнятих клітинок). Таких є 6, що відповідає обов'язкової умові (m + n – 1) = (3 + 4 – 1) = 6. Оскільки суми перевезень по рядах і колонках відповідають  і , отриманий план перевезень є можливим і опорним, тому що цей план є початковим. Для отриманого плану можливо підрахувати загальні витрати на здійснення всіх перевезень, тобто

 у.г.о.

Таблиця 10

ТТ з розподілом запасів А1

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

305

5

706

100

100-30=70

70-70=0

A2

3

–

6

403

1

804

8

–

0

A3

9

801

3

602

6

–

2

–

0

Заявки

bj

0

0

30

70

100

bj'

30-30=0

70-70=70

3.4. Метод південна – східного кута

Процес пошуку опорного плану перевезень за методом південна – східного кута розглянемо на тому же самому прикладі (див. табл. 1).

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

  1.  Задовольнимо  за рахунок А3, решту  відправимо до B3 (див. табл. 11). (Нижній індекс у обсягах перевезень показує черговість розподілу вантажу, а символ прочерку “–“ у деяких клітинках ТТ означає відсутність у них перевезень вантажу.);
  2.  Оскільки В3 ще не задовольнили, додамо необхідний обсяг за рахунок А2 (ще 40); решту  відправимо до В2 (див. табл. 12);
  3.  Щоб повністю задовольнити В2, додамо необхідний обсяг за рахунок А1 (ще 20). Решту  відправимо до В1, задовольнив таким чином його повністю (див. табл. 13).

Таблиця 11

ТТ з розподілом запасів А3

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

7

2

5

–

100

A2

3

6

1

8

–

120

A3

9

–

3

–

6

702

2

701

140

140-70=70

70-70=0

Заявки

bj

80

100

110

70

360

bj'

110-70=30

70-70=0

Таблиця 12

ТТ з розподілом запасів А2

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

7

2

–

5

–

100

A2

3

–

6

802

1

403

8

–

120

140-40=80

80-80=0

A3

9

–

3

–

6

702

2

701

0

Заявки

bj

80

100

40

0

220

bj'

100-80=20

40-40=0

Підрахуємо кількість ненульових перевезень (зайнятих клітинок). Таких є 6, що відповідає обов'язкової умові (m + n – 1) = (3 + 4 – 1) = 6. Оскільки суми перевезень по рядах і колонках відповідають  і , отриманий план перевезень є можливим і опорним, тому що цей план є початковим. Для отриманого плану можливо підрахувати загальні витрати на здійснення всіх перевезень, тобто

 у.г.о.

Таблиця 13

ТТ з розподілом запасів А1

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

806

7

205

2

–

5

–

100

100-20=80

80-80=0

A2

3

–

6

804

1

403

8

–

0

A3

9

–

3

–

6

702

2

701

0

Заявки

bj

80

20

0

0

100

bj'

80-80=0

20-20=0

3.5. Метод найменшого елемента строки ТТ

Цей метод укладається в тім, що першої заповнюють клітинку ТТ з найменшим значенням  у першої строчці матриці, причому , а запаси 1-го постачальника зменшаться до  і заявки j-го споживача до . При цьому, якщо , те з розгляду з таблиці викреслюється повністю 1-й рядок (всі запаси 1-го постачальника використані), у противному випадку j-й стовпець (всі заявки j-го споживача задоволені). Якщо ж , то викреслюється і 1-й рядок і j-й стовпець одночасно. Потім аналогічним способом заповнюється клітинка ТТ з найменшим зі значень  у другої строчці матриці, і т.д. до останньої строки. Цей процес буде повторятися до тих пір, поки не буде одержано (m + n - 1) перевезень.

Розглянемо побудову опорного плану методом найменших елементів строки ТТ на нашому прикладі з таблиці 1.

  1.  На першому кроці заповнюємо клітинку  з найменшим значенням  = 2 у першої строчці ТТ; одержуємо нові значення  = 100 – 100 = 0 і  = 110 – 100 = 10. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 1-у строку (див. табл. 14).

Таблиця 14

ТТ з розподілом вантажу у клітинку А2В3

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

1001

5

–

100

100-100=0

A2

3

6

1

8

120

A3

9

3

6

2

140

Заявки

bj

80

100

110

70

360

bj'

110-100=10

  1.  Найменшим значенням  у другої строчці ТТ володіє клітка (); одержуємо нові значення  = 120 – 10 = 110 і  = 10 – 10 =0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 3-й стовпець (див. табл. 15).
  2.  Найменшим значенням  у третьої строчці таблиці володіє клітка (); одержуємо нові значення  = 140 – 70 = 70 і  = 70 – 70 = 0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 4-й стовпець (див. табл. 16).
  3.  Починаємо процес спочатку – з першої строки. Але запаси вантажу у першого постачальника А1 вичерпали, тому перейдемо до другої строки ТТ.  Наступним найменшим значенням  у другої строчці таблиці володіє клітка  () ;одержуємо нові значення  = 110 – 80 = 30 і  = 80 – 80 = 0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 1-й рядок (табл. 17).

Таблиця 15

ТТ з розподілом вантажу у клітинку А3В4

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

1001

5

–

0

A2

3

6

1

102

8

120

120-10=110

A3

9

3

6

–

2

140

Заявки

bj

80

100

10

70

260

bj'

10-10=0

Таблиця 16

ТТ з розподілом вантажу у клітинку А2В1

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

1001

5

–

0

A2

3

6

1

102

8

–

110

A3

9

3

6

–

2

703

140

140-70=70

Заявки

bj

80

100

0

70

250

bj'

70-70=0

  1.  Наступним найменшим значенням  у третьої строчці таблиці володіє клітка  () ;одержуємо нові значення  = 70 – 70 = 0 і  = 100 – 70 = 30 (див. табл. 18).
  2.  Починаємо процес спочатку – з першої строки. Але запаси вантажу у першого постачальника А1 вичерпали, тому перейдемо до другої строки ТТ. Останнім незаповненим значенням  у таблиці володіє клітка  (); одержуємо нові значення  = 30 – 30 = 0 і  = 30 – 30 = 0 (див. табл. 19).

Таблиця 17

ТТ з розподілом вантажу у клітинку А3В2

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

1001

5

–

0

A2

3

804

6

1

102

8

–

110

110-80=30

A3

9

–

3

6

–

2

703

70

Заявки

bj

80

100

0

70

180

bj'

80-80=0

Таблиця 18

ТТ з розподілом вантажу у клітинку А1В1

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

1001

5

–

0

A2

3

804

6

1

102

8

–

30

A3

9

–

3

705

6

–

2

703

70

170-70=0

Заявки

bj

0

100

0

70

100

bj'

100-70=30

Одержали (m + n – 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

 у.г.о.

Таблиця 19

ТТ з розподілом вантажу у клітинку А1В2

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

1001

5

–

0

A2

3

804

6

306

1

102

8

–

30

30-30=0

A3

9

–

3

705

6

–

2

703

0

Заявки

bj

0

30

0

70

100

bj'

30-30=0

3.6. Метод найменшого елемента стовпця ТТ

Цей метод укладається в тім, що першої заповнюють клітинку ТТ з найменшим значенням  у першому стовпці матриці, причому , а запаси i-го постачальника зменшаться до  і заявки 1-го споживача до . При цьому, якщо , те з розгляду з таблиці викреслюється повністю i-а строка (всі запаси i-го постачальника використані), у противному випадку 1-й стовпець (всі заявки 1-го споживача задоволені). Якщо ж , то викреслюється і i-й рядок і 1-й стовпець одночасно. Потім аналогічним способом заповнюється клітинка ТТ з найменшим зі значень  у другому стовпці матриці, і т.д. до останнього стовпця. Цей процес буде повторятися до тих пір, поки не буде одержано (m + n - 1) перевезень.

Розглянемо побудову опорного плану методом найменших елементів стовпця ТТ на нашому прикладі з таблиці 1.

  1.  На першому кроці заповнюємо клітинку  з найменшим значенням  = 3 у першому стовпці ТТ; одержуємо нові значення  = 120 – 80 = 40 і  = 80 – 80 = 0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 1-й стовпець (див. табл. 20).

Таблиця 20

ТТ з розподілом вантажу у клітинку А2В3

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

2

5

100

A2

3

801

6

1

8

120

120-80=40

A3

9

–

3

6

2

140

Заявки

bj

80

100

110

70

360

bj'

80-80=0

  1.  Найменшим значенням  у другому стовпці ТТ володіє клітка (); одержуємо нові значення  = 140 – 100 = 40 і  = 100 – 100 =0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 2-й стовпець (табл. 21).

Таблиця 21

ТТ з розподілом вантажу у клітинку А3В4

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

5

100

A2

3

801

6

–

1

8

40

A3

9

–

3

1002

6

2

140

140-100=40

Заявки

bj

0

100

110

70

280

bj'

100-100=0

  1.  Найменшим значенням  у третьому стовпці таблиці володіє клітка (); одержуємо нові значення  = 40 – 40 = 0 і  = 110 – 40 = 70. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 2-у строку (табл. 22).

Таблиця 22

ТТ з розподілом вантажу у клітинку А2В1

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

5

100

A2

3

801

6

–

1

403

8

–

40

40-40=0

A3

9

–

3

1002

6

2

40

Заявки

bj

0

0

110

70

180

bj'

110-40=70

  1.  Найменшим значенням  у четвертому стовпці таблиці володіє клітка (); одержуємо нові значення  = 40 – 40 = 0 і  = 70 – 40 = 30. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 3-у строку (табл. 23).

Таблиця 23

ТТ з розподілом вантажу у клітинку А3В2

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

5

100

A2

3

801

6

–

1

403

8

–

0

A3

9

–

3

1002

6

–

2

404

40

40-40=0

Заявки

bj

0

0

70

70

140

bj'

70-40=30

  1.  Починаємо процес спочатку – з першого стовпця. Але заявки вантажу у першого і другого споживача вже задоволені, тому перейдемо до третього стовпця ТТ. Наступним найменшим значенням  у 3-у стовпці ТТ володіє клітка  () ;одержуємо нові значення  = 100 – 70 = 30 і  = 70 – 70 = 0 (табл. 24).

Таблиця 24

ТТ з розподілом вантажу у клітинку А1В1

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

705

5

100

100-70=30

A2

3

801

6

–

1

403

8

–

0

A3

9

–

3

1002

6

–

2

404

0

Заявки

bj

0

0

70

30

100

bj'

70-70=0

  1.  Наступним і останнім найменшим значенням  у третьому стовпці таблиці володіє клітка  () ;одержуємо нові значення  = 30 – 30 = 0 і  = 30 – 30 = 0 (табл. 25).

Таблиця 25

ТТ з розподілом вантажу у клітинку А1В2

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

–

7

–

2

705

5

306

30

30-30=0

A2

3

801

6

–

1

403

8

–

0

A3

9

–

3

1002

6

–

2

404

0

Заявки

bj

0

0

0

30

30

bj'

30-30=0

Одержали (m + n – 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

 у.г.о.

3.7. Метод найменшого елемента ТТ

Цей метод укладається в тім, що першої заповнюють клітку з найменшим значенням  у всій матриці, причому , а запаси i-го постачальника зменшаться до  і заявки j-го споживача до . При цьому, якщо , те з розгляду з таблиці викреслюється повністю і-й рядок (всі запаси i-го постачальника використані), у противному випадку j-й стовпець (всі заявки j-го споживача задоволені). Якщо ж , то викреслюється і i-й рядок і j-й стовпець одночасно. Потім аналогічним способом заповнюється клітка з найменшим зі значень , що залишилися в таблиці , і т.д. до одержання (m + n - 1) перевезень.

Розглянемо побудову опорного плану методом найменших елементів на нашому прикладі з таблиці 1.

  1.  На першому кроці заповнюємо клітку  з найменшим значенням  = 1; одержуємо нові значення  = 120 – 110 = 10 і  = 110 – 110 = 0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 3-й стовпець (див. табл. 26).
  2.  Наступним найменшим значенням  у таблиці володіє клітка ();одержуємо нові значення  = 140 – 70 = 70 і  = 70 – 70 =0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 4-й стовпець (див. табл. 27).

Таблиця 26

ТТ з розподілом вантажу у клітинку А2В3

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

7

2

–

5

100

A2

3

6

1

1101

8

120

120-110=10

A3

9

3

6

–

2

140

Заявки

bj

80

100

110

70

360

bj'

110-110=0

Таблиця 27

ТТ з розподілом вантажу у клітинку А3В4

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

7

2

–

5

–

100

A2

3

6

1

1101

8

–

10

A3

9

3

6

–

2

702

140

140-70=70

Заявки

bj

80

100

0

70

250

bj'

70-70=0

  1.  Наступним найменшим значенням  у таблиці володіє клітка () і клітка  () – беремо першу з них, тобто ; одержуємо нові значення  = 10 – 10 = 0 і  = 80 – 10 = 70 (див. табл. 28).
  2.  Наступним найменшим значенням  у таблиці володіє клітка  () ;одержуємо нові значення  = 70 – 70 = 0 і  = 100 – 70 = 30. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 3-й рядок (табл. 29).

Таблиця 28

ТТ з розподілом вантажу у клітинку А2В1

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

7

2

–

5

–

100

A2

3

103

6

–

1

1101

8

–

10

10-10=0

A3

9

3

6

–

2

702

70

Заявки

bj

80

100

0

0

180

bj'

80-10=70

Таблиця 29

ТТ з розподілом вантажу у клітинку А3В2

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

7

2

–

5

–

100

A2

3

103

6

–

1

1101

8

–

0

A3

9

–

3

704

6

–

2

702

70

70-70=0

Заявки

bj

70

100

0

0

170

bj'

100-70=30

  1.  Наступним найменшим значенням  у таблиці володіє клітка  () ;одержуємо нові значення  = 100 – 70 = 30 і  = 70 – 70 = 0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 1-й стовпець (див. табл. 30).
  2.  Останнім найменшим значенням  у таблиці володіє клітка  () ;одержуємо нові значення  = 30 – 30 = 0 і  = 30 – 30 = 0 (див. табл. 31).

Таблиця 30

ТТ з розподілом вантажу у клітинку А1В1

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

705

7

2

–

5

–

100

100-70=30

A2

3

103

6

–

1

1101

8

–

0

A3

9

–

3

704

6

–

2

702

0

Заявки

bj

70

30

0

0

100

bj'

70-70=0

Таблиця 31

ТТ з розподілом вантажу у клітинку А1В2

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

705

7

306

2

–

5

–

30

30-30=30

A2

3

103

6

–

1

1101

8

–

0

A3

9

–

3

704

6

–

2

702

0

Заявки

bj

0

30

0

0

30

bj'

30-30=0

Одержали (m + n – 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

 у.г.о.

3.8. Метод мінімального вузла відправлення вантажу ТТ

Метод мінімального вузла відправлення вантажу побудови опорного плану перевезень, який поєднує кращі якості перерахованих вище методів також розглянемо на конкретному прикладі (див. табл. 1).

Спочатку знайдемо суми вартостей перевезення одиниці вантажу окремо по рядках (Сі , i = 1,m) ТТ і відсортуємо отримані величини у порядку їх зростання (табл. 32). Порядкові номери зростання сум проставлені у вигляді нижніх індексів відповідних величин.

Таблиця 32

Вихідна ТТ

B1

B2

B3

B4

Запаси

ai

Ci

A1

4

x11

7

x12

2

x13

5

x14

100

181

A2

3

x21

6

x22

1

x23

8

x24

120

182

A3

9

x31

3

x32

6

x33

2

x34

140

203

Заявки

bj

80

100

110

70

360

Заносити обсяги перевезень починаємо з вузла, який має найменшу суму вартостей одиниці перевезень вантажу по окремому рядку – вузлу відправлення вантажу (звідси і назва методу). Подальший процес формування опорного плану буде відбуватися у відповідності з порядковими номерами зростання сум вартостей перевезень одиниці вантажу вузлів відправлення, що залишилися і т.д., до одержання (m + n - 1) перевезень. Принцип заповнення клітинок ТТ у самому рядку буде наступним: максимально задовольнити весь обсяг замовлення вантажу в першу чергу за рахунок найменших вартостей перевезень одиниці вантажу.

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

Таблиця 33

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

відправлення вантажу ТТ

B1

B2

B3

B4

Запаси

ai

Ci

A1

4

–

7

–

2

1001

5

–

100

181

A2

3

804

6

306

1

102

8

–

120

182

A3

9

–

3

705

6

–

–

2

703

140

203

Заявки

bj

80

100

110

70

360

Одержали (m + n – 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

 у.г.о.

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

Метод мінімального вузла призначення вантажу побудови опорного плану перевезень також розглянемо на конкретному прикладі (див. табл. 1).

Спочатку знайдемо суми вартостей перевезення одиниці вантажу окремо по стовпцях (Сj , j = 1,n) ТТ і відсортуємо отримані величини у порядку їх зростання (табл. 34). Порядкові номери зростання сум проставлені у вигляді нижніх індексів відповідних величин.

Заносити обсяги перевезень починаємо з вузла призначення, який має найменшу суму вартостей одиниці перевезень вантажу по окремому стовпцю (звідси і назва методу). Подальший процес формування опорного плану буде відбуватися у відповідності з порядковими номерами зростання сум вартостей перевезень одиниці вантажу вузлів призначення, що залишилися і т.д., до одержання (m + n - 1) перевезень. Принцип заповнення клітинок ТТ у самому стовпці буде наступним:

Таблиця 34

Вихідна ТТ

B1

B2

B3

B4

Запаси

ai

A1

4

x11

7

x12

2

x13

5

x14

100

A2

3

x21

6

x22

1

x23

8

x24

120

A3

9

x31

3

x32

6

x33

2

x34

140

Заявки

bj

80

100

110

70

360

Cj

163

164

91

152

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

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

Таблиця 35

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

призначення вантажу ТТ

B1

B2

B3

B4

Запаси

ai

A1

4

705

7

306

2

–

5

–

100

A2

3

103

6

–

1

1101

8

–

120

A3

9

–

3

704

6

–

2

702

140

Заявки

bj

80

100

110

70

360

Cj

163

164

91

152

Одержали (m + n – 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

 у.г.о.

3.10. Метод мінімального вузла відправлення-призначення вантажу ТТ

Метод мінімального вузла відправлення-призначення вантажу побудови опорного плану перевезень, який поєднує кращі якості перерахованих вище методів також розглянемо на конкретному прикладі (див. табл. 1).

Спочатку знайдемо суми вартостей перевезення одиниці вантажу окремо по рядках (Сі , i = 1,m) і стовпцям ТТ (Сj , j = 1,n) і відсортуємо отримані величини у порядку їх зростання (табл. 36). Порядкові номери зростання сум проставлені у вигляді нижніх індексів відповідних величин.

Таблиця 36

Вихідна ТТ

B1

B2

B3

B4

Запаси

ai

Ci

A1

4

x11

7

x12

2

x13

5

x14

100

185

A2

3

x21

6

x22

1

x23

8

x24

120

186

A3

9

x31

3

x32

6

x33

2

x34

140

207

Заявки

bj

80

100

110

70

360

Cj

163

164

91

152

Заносити обсяги перевезень починаємо з вузла, який має найменшу суму вартостей одиниці перевезень вантажу або по окремому рядку, або по окремому стовпцю (звідси і назва методу). Подальший процес формування опорного плану буде відбуватися у відповідності з порядковими номерами зростання сум вартостей перевезень одиниці вантажу вузлів, що залишилися до одержання (m + n - 1) перевезень.

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

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

Таблиця 37

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

відправлення-призначення вантажу ТТ

B1

B2

B3

B4

Запаси

ai

Ci

A1

4

705

7

306

2

–

5

–

100

185

A2

3

103

6

–

1

1101

8

–

120

186

A3

9

–

3

704

6

–

2

702

140

207

Заявки

bj

80

100

110

70

360

Cj

163

164

91

152

Одержали (m + n – 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

 у.г.о.

3.11. Метод випадкового заповнення (рандомизації)

Побудова опорного плану перевезень методом випадкового заповнення (рандомизації) також розглянемо на конкретному прикладі (див. табл. 1).

Заносити обсяги перевезень починаємо з клітинки, у якої номер строки і стовпця генерується випадковим способом (звідси і назва методу). Подальший процес формування опорного плану буде відбуватися аналогічно до одержання (m + n - 1) перевезень, причому вже заповнені клітинки ТТ будуть пропускатися, а номера строк і стовпців будуть генеруватися у діапазоні ,відповідно, від 1 до m і від 1 до n. У нашому прикладі опорний план побудований методом випадкового заповнення за допомогою відповідної програми відображений на рис. 1.

Рис. 1. Варіант опорного плану перевезень вантажу

Сам процес побудови опорного плану представлений у таблиці 38 (причому нижній індекс у обсягах перевезень вказує на черговість розподілу вантажу) і представляє наступне:

1-а генерація номерів строки і стовпця:  i = 3; j = 3; х33 = 110;

2-а генерація номерів строки і стовпця:  i = 3; j = 4; х34 =  30;

3-а генерація номерів строки і стовпця:  i = 1; j = 3;

(вантаж у клітинку А1В3 не розподіляється, оскільки заявка b3  вже задоволена)

4-а генерація номерів строки і стовпця:  i = 1; j = 1; х11 =  80;

5-а генерація номерів строки і стовпця:  i = 2; j = 2; х22 =   80;

6-а генерація номерів строки і стовпця:  i = 3; j = 4;

(вантаж у клітинку А3В4 не розподіляється, оскільки вона вже заповнена)

7-а генерація номерів строки і стовпця:  i = 1; j = 2; х12 =   20;

8-а генерація номерів строки і стовпця:  i = 2; j = 1;

(вантаж у клітинку А2В1 не розподіляється, оскільки заявка b1  вже задоволена)

9-а генерація номерів строки і стовпця:  i = 2; j = 4; х24 =   20;

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

Таблиця 38

Опорний план за методом випадкового

заповнення клітинок ТТ

B1

B2

B3

B4

Запаси

ai

ai'

ai'’

A1

4

803

7

205

2

–

5

–

100

100-80=20

20-20=0

A2

3

–

6

804

1

–

8

406

120

120-80=40

40-40=0

A3

9

–

3

–

6

1101

2

302

140

140-110=30

30-30=0

Заявки

bj

80

100

110

70

360

bj'

80-80=0

100-80=20

110-110=0

70-30=40

bj'’

20-20=0

40-40=0

Одержали (m + n – 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

 у.г.о.

3.12. Метод апроксимації Фогеля

Побудова опорного плану перевезень методом апроксимації Фогеля також розглянемо на тому же самому прикладі (див. табл. 1).

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

У такому випадку, перевіряють, чи є мінімальний елемент у стовпці також мінімальним і в рядку. Якщо такий елемент єдиний, то в нього й поміщають відповідну кореспонденцію. Якщо ж мінімальних елементів і в стовпці і у рядку декілька, то необхідно знайти в рядках другу різницю і вибрати той елемент, у якого друга різниця більше. У нашім випадку мінімальне значення 2 у четвертому стовпці  одночасно є і мінімальним значенням у третьому рядку, а тому що воно єдине, те саме в цю клітку А3В4 і поміщаємо максимально можливу кореспонденцію 70, при цьому  виключаємо з подальшого розгляду четвертий стовпець, поставивши в його вільних клітках знак “ –“, а нижче різниці - букву К (кінець). Різниці в інших стовпцях не змінилися, удруге їх не переписуємо. Різниці ж у рядках можуть змінитися, тому обчислюємо їх знову і записуємо у табл. 40.

Таблиця 39

Перша ітерація ТТ

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

7

2

5

–

100

4-2=2

A2

3

6

1

8

–

120

3-1=2

A3

9

3

6

2

70

140

3-2=1

140-70=70

Заявки

bj

80

100

110

70

360

4-3=1

6-3=3

2-1=1

5-2=3

К

bj'

70-70=0

Знову максимальне значення різниці 3 зустрічається у нашому прикладі двічі - у другому стовпці і у третьому рядку (також підкреслюємо ці значення). Але тому що мінімальні значення елементів, що залишилися, і в цьому стовпці, і в цьому рядку збігаються і являють собою значення  3 клітки А3В2, те саме в цю клітку А3В2 і поміщаємо максимально можливу кореспонденцію 70, при цьому  виключаємо з подальшого розгляду третій рядок, поставивши в його вільних клітках знак “–“, а нижче різниці - букву К (кінець), тому що повністю вичерпаний весь запас вантажу у третього постачальника.

Таблиця 40

Друга ітерація ТТ

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

7

2

5

–

100

4-2=2

A2

3

6

1

8

–

120

3-1=2

A3

9

–

3

70

6

–

2

70

70

6-3=3

К

70-70=0

Заявки

bj

80

100

110

0

290

4-3=1

6-3=3

2-1=1

К

bj'

100-70=30

В таблиці 41 максимальне значення різниці 2 знаходиться у першої і другій строчці, але тільки у другій строчці значення її мінімального елементу 1 у клітинці А2В3 є мінімальним і у третьому стовпці. Тому поміщаємо у цю клітинку (А2В3) максимально можливий обсяг вантажу – 110, при цьому  виключаємо з подальшого розгляду третій стовпець, поставивши в його вільних клітках знак “–“, а нижче різниці - букву К (кінець), тому що повністю задоволена заявка у третього споживача.

Таблиця 41

Третя ітерація ТТ

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

7

2

–

5

–

100

4-2=2

A2

3

6

1

110

8

–

120

3-1=2

120-110=10

A3

9

–

3

70

6

–

2

70

0

К

Заявки

bj

80

30

110

0

220

4-3=1

7-6=1

2-1=1

К

К

bj'

110-110=0

В таблиці 42 максимальне значення різниці 3 також знаходиться у першої і другій строчці, але тільки у другій строчці значення її мінімального елементу 3 у клітинці А2В1 є мінімальним і у першому стовпці. Тому поміщаємо у цю клітинку (А2В1) максимально можливий обсяг вантажу – 10, при цьому  виключаємо з подальшого розгляду другу строку, поставивши в його вільних клітках знак “–“, а нижче різниці - букву К (кінець), тому що повністю вичерпаний весь запас вантажу у другого постачальника.

Таблиця 42

Четверта ітерація ТТ

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

7

2

–

5

–

100

7-4=3

A2

3

10

6

–

1

110

8

–

10

6-3=3

10-10=0

К

A3

9

–

3

70

6

–

2

70

0

К

Заявки

bj

80

30

0

0

110

4-3=1

7-6=1

К

К

bj'

80-10=70

Оскільки у таблиці 43 перший і другий стовпці містять по одному елементу, то різниця у цьому випадку знаходиться між ними, тобто дорівнює 0. У першої єдиної строчці знаходимо мінімальний елемент – це 4 у клітинці А1В1. Тому поміщаємо у цю клітинку максимально можливий обсяг вантажу – 70, при цьому  виключаємо з подальшого розгляду перший стовпець, поставивши нижче різниці – букву К (кінець), тому що повністю задоволена уся заявка вантажу першого споживача.

У таблиці 44 заповнюється остання вільна клітинка ТТ, а саме А1В2 обсягом вантажу рівним 30 одиницям.

Таблиця 43

П’ята ітерація ТТ

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

70

7

2

–

5

–

100

7-4=3

100-70=30

A2

3

10

6

–

1

110

8

–

0

К

A3

9

–

3

70

6

–

2

70

0

К

Заявки

bj

70

30

0

0

100

4-4=0

К

7-7=0

К

К

bj'

70-70=0

Таблиця 44

Шоста ітерація ТТ

B1

B2

B3

B4

Запаси

ai

ai'

A1

4

70

7

30

2

–

5

–

30

7-7=0

К

30-30=0

A2

3

10

6

–

1

110

8

–

0

К

A3

9

–

3

70

6

–

2

70

0

К

Заявки

bj

0

30

0

0

30

К

7-7=0

К

К

К

bj'

30-30=0

В результаті одержано (m + n - 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

 у.г.о.

4. МЕТОДИ ЗНАХОДЖЕННЯ ОПТІМАЛЬНИХ ПЛАНІВ

ПЕРЕВЕЗЕНЬ ВАНТАЖУ

4.1. Симплексний метод оптимізації транспортних перевезень

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

Оскільки ТЗ є окремим випадком загальної задачі ЛП (ЗЗЛП), то до неї також цілком можливо застосувати всі стандартні методи її розв’язання (зокрема найвідоміший з них – симплексний метод), попередньо привівши ТЗ до вигляду задачі ЛП і врахувавши її специфічність. Для цього необхідно провести над математичною моделлю ТЗ ряд перетворень. Ці перетворення будемо здійснювати на конкретному прикладі ТЗ, а саме для m постачальників (m=3) і n споживачів продукції (n=4) (див. табл. 1).

а) спочатку запишемо вихідну систему рівнянь ТЗ у такому вигляді:

||  ||   ||  ||

b1  b2     b3  b4

де: xij – кількість продукції, відправленої від і-го постачальника до j-го споживача;

аi – обсяг продукції наявної у і-го постачальника ( i=1, 2, 3);

bj – обсяг продукції необхідної j-ому споживачу (j=1, 2, 3, 4).

б) подамо її у вигляді системи (т + n) лінійних рівнянь таким чином:

в) замінимо x11 на x1, x12 на x2, x13 на x3, . . ., x34 на x12. Маємо:

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

У результаті цих перетворень ми утворили систему (т + п) лінійних рівнянь з (mп + т+ n) позитивними перемінними, розв’язати яку можна за допомогою симплекс-методу. Оскільки сума рівнянь системи в рядках дорівнює сумі рівнянь системи в стовпцях, то ми одержали лінійно-залежну систему рівнянь. Щоб привести її до нормального (лінійно-незалежного) виду, одне з рівнянь системи (переважно останнє) можна без шкоди для кінцевого результату розв’язку ТЗ відкинути. Тоді ми матимемо (т +  п – 1) лінійних рівнянь і (mп + т+ n - 1) перемінних.

Необхідно також відзначити те, що у класичній ТЗ перевезти продукцію від усіх постачальників (аi) потрібно так, щоб усі замовлення були виконані (bj), а загальна вартість (L) транспортних перевезень була б мінімальною, тобто:

,

де: с1 , с2, ... сk – вартість перевезення одиниці продукції від кожного постачальника до кожного споживача (k = 1,т п).

Розглянемо розв'язання ТЗ на конкретному прикладі, умови якого дані у вигляді ТТ (табл. 45) , де т = 3 , n = 4. Відповідно, кількість рівнянь становитиме (m + n – 1 ) = 6, кількість вихідних перемінних – (m × n) = 12 і кількість додаткових перемінних – (т + п – 1) = 6.

Таблиця 45

Дані ТЗ у вигляді ТТ

B1

B2

B3

B4

Запаси

ai

A1

c1 = 4

x1

c2 = 7

x2

c3 = 2

x3

c4 = 5

x4

100

A2

c5 = 3

x5

c6 = 6

x6

c7 = 1

x7

c8 = 8

x8

120

A3

c9 = 9

x9

c10 = 3

x10

c11 = 6

x11

c12 = 2

x12

140

Заявки

bj

80

100

110

70

360

Запишемо умову нашої ТЗ у термінах ЗЗЛП.

Необхідно мінімізувати цільову функцію  L = 4× x1 +7 × x2 +2 × x3 +5 × x4 +3 × x5 + 6 × x6 +1×x7+8 × x8 +9 × x9 +3 × x10 + 6 × x11 +2×x12,  

за таких обмежень:

тобто кількість рівнянь становить 6, а кількість вихідних перемінних дорівнює 12.

Вводимо до обмежень нові змінні  x13, x14, x15, x16, x17, x18. Значення відповідних коефіцієнтів впливу вибираємо набагато більші ніж існують. У нашому випадку приймемо за цю величину суму всіх коефіцієнтів при невідомих у початковій цільовій функції, тобто 56. Завдяки цьому перемінні   x13, x14, x15, x16, x17, x18  з базисних поступово будуть переведені у вільні, що забезпечує тим самим мінімум цільової функції. Після введення нових перемінних маємо: 

L = 4× x1 +7 × x2 +2 × x3 +5 × x4 +3 × x5 + 6 × x6 +1×x7+8 × x8 +9 × x9 +3 × x10 + 6 × x11 +2×x12+56 × x13 +56 × x14 +56 × x15 + 56 × x16 +56×x17+56 × x18, → min,

за обмежень

Остаточна кількість рівнянь k = 6; кількість перемінних l = 18. 

За базисні обираємо x13, x14, x15, x16, x17, x18 і отримуємо перше базисне рішення X = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100, 120, 140, 80, 100, 110}, що забезпечує L = 56 × 100 + 56 × 120 +56 × 140 + 56 × 80 + 56 × 100 +56 × 110 = 36400  у.г.о.

Складемо першу симплекс-таблицю (СТ) – табл. 46. У першому рядку цієї таблиці знаходяться значення коефіцієнтів cj при невідомих цільової функції; у першій графі СТ розташовані значення коефіцієнтів cбі при базових невідомих цільової функції; друга графа містить самі базові невідомі хбі; третя – значення базових невідомих bбi (у першій СТ це значення правих частин останньої системи рівнянь) і частина СТ, що залишилася, крім останнього рядка, зайнята коефіцієнтами aij при невідомих також останньої системи рівнянь.

Останній рядок (індексний ряд) служить для розрахунків індексів ∆j , що є характеристиками оптимальності отриманого плану. Індекси розраховуються за допомогою наступних формул:

Таблиця 46

Перша СТ

4

7

2

5

3

6

1

8

9

3

6

2

56

56

56

56

56

56

cбі

хбі

bбі

х1

х2

х3

х4

х5

х6

х7

х8

х9

х10

х11

х12

х13

х14

х15

х16

х17

х18

56

х13

100

1

1

1

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

56

х14

120

0

0

0

0

1

1

1

1

0

0

0

0

0

1

0

0

0

0

56

х15

140

0

0

0

0

0

0

0

0

1

1

1

1

0

0

1

0

0

0

56

х16

80

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

0

56

х17

100

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

56

х18

110

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

∆0 = 36400

∆1=

108

∆2=105

∆3=110

∆4=51

∆5=109

∆6=106

∆7=111

∆8=48

∆9=103

∆10=109

∆11=

106

∆12=54

∆13=0

∆14=0

∆15=0

∆16=0

∆17=0

∆18=0

Вважається, що отримане рішення хбі  є оптимальним, якщо .

Порахуємо значення індексів для першої  СТ:

∆0 = 56 × 100 + 56 × 120 +56 × 140 + 56 × 80 +56 × 100 + 56 × 110 = 36400  у.г.о.

∆1 = 56 × 1 + 56 × 0 +56 × 0 + 56 × 1 +56 × 0 + 56 × 0 – 4 =  108

∆2 = 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 1 + 56 × 0 – 7 =  105

∆3 = 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 1 – 2 =  110

∆4 = 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 5 =    51

∆5 = 56 × 0 + 56 × 1 +56 × 0 + 56 × 1 +56 × 0 + 56 × 0 – 3 =  109

∆6 = 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 1 + 56 × 0 – 6 =  106

∆7 = 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 0 + 56 × 1 – 1 =  111

∆8 = 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 8=     48

∆9 = 56 × 0 + 56 × 0 +56 × 1 + 56 × 1 +56 × 0 + 56 × 0 – 9 =  103

∆10 = 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 1 + 56 × 0 – 3 = 109

∆11 = 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 0 + 56 × 1 – 6 = 106

∆12 = 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 0 + 56 × 0 – 2   = 54

∆13 = 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 56 =   0

∆14 = 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 56 =   0

∆15 = 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 0 + 56 × 0 – 56 =   0

∆16 = 56 × 0 + 56 × 0 +56 × 0 + 56 × 1 +56 × 0 + 56 × 0 – 56 =   0

∆17 = 56 × 0 + 56 × 0 +56 × 0 + 56 × 0 +56 × 1 + 56 × 0 – 56 =   0

∆18 = 56 × 0 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 1 – 56 =   0

Очевидно, що базове рішення не є оптимальним, тому що усі індекси від  ∆1 до  ∆18 позитивні, тому продовжимо поліпшення (оптимізацію) базового плану далі.

У якості ключового стовпця, який містить внесену в базу вільну змінну,  вибираємо стовпець х7, що має максимальне позитивне значення ∆7 = 111. Для визначення ключового  рядка рахуємо відповідні відношення значень базових невідомих bбi на не нульові значення елементів обраного ключового стовпця, а саме:

  ;    і вибираємо з них  мінімальне, тобто друге.

Тоді ключовим рядком буде шостий і він містить базову змінну  х18 , що виводиться з базису. Тобто змінна ключового шостого рядка базису  х18 має бути замінена на вільну змінну ключового стовпця х7 , при цьому ключове число a67 = 1 (це число відмічено у СТ більшим розміром). Складаємо нову СТ (див. табл. 47).

Спочатку введемо в базис замість змінної х18 змінну х7 зі значенням її коефіцієнта  c7 = 1  і розділимо всі елементи цього рядка на ключове число a67 = 1. Після цього перерахуємо значення частини елементів таблиці, що залишилася,  таким способом:

,

де: НЕ і СЕ – відповідно будь-який новий елемент (aijн або biн) з не ключового рядка і той же старий елемент  (aij  або  bi) СТ, що перетворюється;

 ЕКр і  ЕКст – відповідно елементи  ключового рядка і ключового стовпчику СТ, що перетворюється;

 К  –  ключовий  елемент СТ, що перетворюється (у нашому випадку для першої СТ це  a67).

Порахуємо як приклад по цій формулі нові значення b2  ,  a23 і a27:

  .

Інші елементи перенесемо в нову СТ без демонстрації аналогічних детальних розрахунків.

Як видно з таблиці 47 нове значення цільової функції дорівнює 24190 у.г.о., що значно менше попереднього її значення і, що,  у свою чергу, свідчить про нормальний плин процесу оптимізації. Індексний рядок нової СТ містить позитивні елементи – це означає, що отримане значення не є оптимальним і план перевезень вимагає поліпшення. Відзначимо в СТ ключовий елемент a25 і опускаючи всі розрахунки перейдемо до наступної СТ (див. табл. 48).

Таблиця 47

Друга СТ

4

7

2

5

3

6

1

8

9

3

6

2

56

56

56

56

56

56

cбі

хбі

bбі

х1

х2

х3

х4

х5

х6

х7

х8

х9

х10

х11

х12

х13

х14

х15

х16

х17

х18

56

х13

100

1

1

1

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

56

х14

10

0

0

-1

0

1

1

0

1

0

0

-1

0

0

1

0

0

0

-1

56

х15

140

0

0

0

0

0

0

0

0

1

1

1

1

0

0

1

0

0

0

56

х16

80

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

0

56

х17

100

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

1

х7

110

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

∆0 = 24190

∆1=

108

∆2=105

∆3=

-1

∆4=51

∆5=109

∆6=106

∆7=0

∆8=48

∆9=103

∆10=109

∆11=

-5

∆12=54

∆13=0

∆14=0

∆15=0

∆16=0

∆17=0

∆18=

-111

Із цієї СТ також видно, що процес оптимізації триває (нове значення цільової функції дорівнює 23100), але в індексному рядку ще присутні позитивні елементи – це означає, що план перевезень вимагає подальшого поліпшення. Відзначимо також у СТ ключовий елемент a5,10 і  перейдемо до наступної СТ (див. табл. 49).

Таблиця 48

Третя СТ

4

7

2

5

3

6

1

8

9

3

6

2

56

56

56

56

56

56

cбі

хбі

bбі

х1

х2

х3

х4

х5

х6

х7

х8

х9

х10

х11

х12

х13

х14

х15

х16

х17

х18

56

х13

100

1

1

1

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

3

х5

10

0

0

-1

0

1

1

0

1

0

0

-1

0

0

1

0

0

0

-1

56

х15

140

0

0

0

0

0

0

0

0

1

1

1

1

0

0

1

0

0

0

56

х16

70

1

0

1

0

0

-1

0

-1

1

0

1

0

0

-1

0

1

0

1

56

х17

100

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

1

х7

110

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

∆0 = 23100

∆1=

108

∆2=105

∆3=

108

∆4=51

∆5=0

∆6=

-3

∆7=0

∆8=

-61

∆9=103

∆10=109

∆11=

104

∆12=54

∆13=0

∆14=

-109

∆15=0

∆16=0

∆17=0

∆18=

-2

У цій таблиці також присутні позитивні елементи в індексному рядку, тому переходимо до нового СТ із новим ключовим елементом – a41 (див. табл. 50).

Таблиця 49

Четверта СТ

4

7

2

5

3

6

1

8

9

3

6

2

56

56

56

56

56

56

cбі

хбі

bбі

х1

х2

х3

х4

х5

х6

х7

х8

х9

х10

х11

х12

х13

х14

х15

х16

х17

х18

56

х13

100

1

1

1

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

3

х5

10

0

0

-1

0

1

1

0

1

0

0

-1

0

0

1

0

0

0

-1

56

х15

40

0

-1

0

0

0

-1

0

0

1

0

1

1

0

0

1

0

-1

0

56

х16

70

1

0

1

0

0

-1

0

-1

1

0

1

0

0

-1

0

1

0

1

3

х10

100

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

1

х7

110

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

∆0 = 12200

∆1=

108

∆2=

-4

∆3=

108

∆4=51

∆5=0

∆6=

-112

∆7=0

∆8=

-61

∆9=103

∆10=0

∆11=

104

∆12=54

∆13=0

∆14=-109

∆15=0

∆16=0

∆17=

-109

∆18=

-2

У цій таблиці також присутні позитивні елементи в індексному рядку, тому переходимо до нового СТ із новим ключовим елементом – a3,12 (див. табл. 51).

Таблиця 50

П’ята СТ

4

7

2

5

3

6

1

8

9

3

6

2

56

56

56

56

56

56

cбі

хбі

bбі

х1

х2

х3

х4

х5

х6

х7

х8

х9

х10

х11

х12

х13

х14

х15

х16

х17

х18

56

х13

30

0

1

0

1

0

1

0

1

-1

0

-1

0

1

1

0

-1

0

-1

3

х5

10

0

0

-1

0

1

1

0

1

0

0

-1

0

0

1

0

0

0

-1

56

х15

40

0

-1

0

0

0

-1

0

0

1

0

1

1

0

0

1

0

-1

0

4

х1

70

1

0

1

0

0

-1

0

-1

1

0

1

0

0

-1

0

1

0

1

3

х10

100

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

1

х7

110

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

∆0 = 4640

∆1=

0

∆2=

-4

∆3=

0

∆4=51

∆5=0

∆6=

-4

∆7=0

∆8=

47

∆9=

-5

∆10=0

∆11=

-4

∆12=54

∆13=0

∆14=

-1

∆15=0

∆16=

-108

∆17=

-109

∆18=

-110

У цій таблиці також присутні позитивні елементи в індексному рядку, тому переходимо до нового СТ із новим ключовим елементом – a1,4 (див. табл. 52).

Отримана симплекс-таблиця містить усі  , завдяки чому можна стверджувати, що отримане рішення є оптимальним, тобто: х1 = 70;  х2 = 0;  х3 = 0;  х4 = 30;  х5 = 10;  х6 = 0;  х7 = 110;  х8 = 0;  х9 = 0;  х10 = 100;  х11 = 0;  х12 = 40;  х13 = 0;  х14 = 0; …; х18 = 0, що забезпечує Lopt = 950 у.г.о. (У додатку 5 наведений розрахунок цього ж самого прикладу у матричному процесорі Excel).

Представимо одержаний оптимальний план перевезень вантажу для нашого прикладу у вигляді ТТ (табл. 53).

Таблиця 51

Шоста СТ

4

7

2

5

3

6

1

8

9

3

6

2

56

56

56

56

56

56

cбі

хбі

bбі

х1

х2

х3

х4

х5

х6

х7

х8

х9

х10

х11

х12

х13

х14

х15

х16

х17

х18

56

х13

30

0

1

0

1

0

1

0

1

-1

0

-1

0

1

1

0

-1

0

-1

3

х5

10

0

0

-1

0

1

1

0

1

0

0

-1

0

0

1

0

0

0

-1

2

х12

40

0

-1

0

0

0

-1

0

0

1

0

1

1

0

0

1

0

-1

0

4

х1

70

1

0

1

0

0

-1

0

-1

1

0

1

0

0

-1

0

1

0

1

3

х10

100

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

1

х7

110

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

∆0 = 2480

∆1=

0

∆2=

50

∆3=

0

∆4=51

∆5=0

∆6=

50

∆7=0

∆8=

47

∆9=

-59

∆10=0

∆11=

-58

∆12=0

∆13=0

∆14=

-1

∆15=-54

∆16=

-108

∆17=

-55

∆18=

-110

Таблиця 52

Сьома СТ

4

7

2

5

3

6

1

8

9

3

6

2

56

56

56

56

56

56

cбі

хбі

bбі

х1

х2

х3

х4

х5

х6

х7

х8

х9

х10

х11

х12

х13

х14

х15

х16

х17

х18

5

х4

30

0

1

0

1

0

1

0

1

-1

0

-1

0

1

1

0

-1

0

-1

3

х5

10

0

0

-1

0

1

1

0

1

0

0

-1

0

0

1

0

0

0

-1

2

х12

40

0

-1

0

0

0

-1

0

0

1

0

1

1

0

0

1

0

-1

0

4

х1

70

1

0

1

0

0

-1

0

-1

1

0

1

0

0

-1

0

1

0

1

3

х10

100

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

1

х7

110

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

∆0 = 950

∆1=

0

∆2=

-1

∆3=

0

∆4=

0

∆5=0

∆6=

-1

∆7=0

∆8=

-4

∆9=

-8

∆10=0

∆11=

-7

∆12=0

∆13=-51

∆14=

-52

∆15=-54

∆16=

-57

∆17=

-55

∆18=

-59

Таблиця 53

Оптимальний план перевезень вантажу у вигляді ТТ

B1

B2

B3

B4

Запаси

ai

A1

c1 = 4

x1=70

c2 = 7

x2=0

c3 = 2

x3=0

c4 = 5

x4=30

100

A2

c5 = 3

x5=10

c6 = 6

x6=0

c7 = 1

x7=110

c8 = 8

x8=0

120

A3

c9 = 9

x9=0

c10 = 3

x10=100

c11 = 6

x11=0

c12 = 2

x12=40

140

Заявки

bj

80

100

110

70

360

4.2. Метод потенціалів оптимізації транспортних перевезень

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

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

2. Після визначення всіх  i  (;) перевіряємо нерівність  для всіх (ij) незайнятих кліток таблиці (тобто для ). Якщо ця нерівність має місце для усіх без виключення незайнятих кліток, план перевезень є оптимальним.

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

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

Наприклад, є певний опорний план перевезень (табл. 54). Відмітимо, що для отриманого плану маємо L1 = 30×7 + 70×2 + 80×3 + 40×1 + 70×3 + 70×2 = 980 у.г.о.

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

Приймаємо , тоді ; . Використовуючи вже отримані потенціали, визначаємо решту потенціалів:

;   ;

;   .

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

;  ;  ;

;  ;  .

Таблиця 54

Вихідна ТТ

B1

B2

B3

B4

ui

Запасиai

A1

4

7

30

2

70

5

+

0

100

A2

3

80

6

1

40

8

-1

120

A3

9

3

70 +

6

2

70

-4

140

vj

4

7

2

6

Заявки

bj

80

100

110

70

360

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

Для цього шукаємо контур, що містить у решті кутів зайняті клітинки. Це контур:  (див. табл. 54). Оскільки ми завантажуємо , присвоюємо їй знак “+”, потім, пересуваючись по контуру, послідовно міняємо знаки. Мінімальне абсолютне значення від'ємного обсягу знаходиться в клітинці  і дорівнює xп = 30 в.о. Пересуваємо цей обсяг по контуру з урахуванням знаків і отримуємо новий план перевезень (див. табл. 55), при цьому вартість його реалізації буде дорівнювати:

L2 = 70×2 + 30×5 + 80×3 + 40×1 + 100×3 + 40×2 = 950 у.г.о.

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

 .

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

;  ;  ;

;  ;  .

Таблиця 55

ТТ після розподілу вантажу у клітинку А1В4

B1

B2

B3

B4

ui

Запасиai

A1

4

7

2

70

5

30

0

100

A2

3

80

6

1

 40

8

-1

120

A3

9

3

100

6

2

40

-3

140

vj

4

6

2

5

Заявки

bj

80

100

110

70

360

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

5. УГОРСЬКИЙ МЕТОД РОЗВ’ЯЗАННЯ ТРАНСПОРТНОЇ ЗАДАЧІ

ПРО ПРИЗНАЧЕННЯ

Угорський метод є одним з найцікавіших і найпоширеніших методів рішення транспортних завдань. Основна ідея цього методу була вперше висловлена угорським математиком Е. Егерварі (звідси й назва методу) задовго до виникнення теорії лінійного програмування.

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

5.1. Постановка завдання

Припустимо, що є  різні транспортні засоби (ТЗ), кожний з яких може виконувати будь-яку транспортну роботу, але з неоднаковою ефективністю. Продуктивність кожного i-го ТЗ при виконанні j-тої транспортної роботи позначимо Cij , і = 1, … ,n; j = 1, … ,n. Потрібно так розподілити ТЗ по роботах, щоб сумарний ефект від їхнього використання був максимальний. Таке завдання називається завданням вибору або завданням про призначення.

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

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

5.2. Розв’язання завдання

Введемо наступні поняття:

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

Еквівалентні матриці С і D (C ~ D), якщо сij  = dij + ai + bj для всіх i,j.

Виділені елементи – елементи, які розташовані у виділених рядках або стовпчиках. Блок-схема алгоритму угорського методу наведена нижче:

Попередній етап. Розшукують максимальний елемент в j-му стовпці й всі елементи цього стовпця послідовно віднімають із максимального. Цю операцію проробляють над всіма стовпцями матриці С. У результаті утвориться матриця з ненегативними елементами, у кожному стовпці якої є, принаймні, один нуль.

Далі розглядають i-ий рядок отриманої матриці, розшукують її мінімальний елемент і з кожного елемента цього рядка віднімають мінімальний. Цю процедуру повторюють із усіма рядками. У результаті одержимо матрицю С0 (С0 ~ C), у кожному рядку й стовпці якої є, принаймні, один нуль. Описаний процес перетворення С у С0 називається приведенням матриці.

Знаходимо довільний нуль у першому стовпці й відзначаємо його зірочкою. Потім переглядаємо другий стовпець, і якщо в ньому є нуль, розташований у рядку, де немає нуля із зірочкою, то відзначаємо його зірочкою. Аналогічно переглядаємо один за іншим всі стовпці матриці С0 і відзначаємо, якщо можливо, що випливають нулі знаком '*'. Очевидно, що нулі матриці С0, відзначені зірочкою, є незалежними. На цьому попередній етап закінчується.

(k+1)-а ітерація. Припустимо, що k-та ітерація вже проведена й у результаті отримана матриця Сk. Якщо в ній є рівно n нулів із зірочкою, то процес рішення закінчується. У противному випадку переходимо до (k+1) –ої ітерації.

Кожна ітерація починається першим і закінчується другим етапом. Між ними може кілька разів проводитися пари етапів: третій - перший. Перед початком ітерації знаком '+' виділяють стовпці матриці Сk, які містять нулі із зірочками.

Перший етап. Переглядають невиділені стовпці Сk. Якщо серед них не виявиться нульових елементів, то переходять до третього етапу. Якщо ж невиділений нуль матриці Сk виявлений, то можливо один із двох випадків:

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

2) цей рядок не містить нуля із зірочкою.

У другому випадку переходимо відразу до другого етапу, відзначивши цей нуль штрихом.

У першому випадку цей невиділений нуль відзначають штрихом і виділяють рядок, у якій він утримується (знаком '+' праворуч від рядка). Переглядають цей рядок, знаходять нуль із зірочкою й знищують знак '+' виділення стовпця, у якому втримується даний нуль.

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

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

1) всі нулі матриці Сk виділені, тобто перебувають у виділених рядках або стовпцях. При цьому переходять до третього етапу;

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

Другий етап. На цьому етапі будують наступний ланцюжок з нулів матриці Сk: вихідний нуль зі штрихом, нуль із зірочкою, розташований в одному стовпці з першим нулем зі штрихом в одному рядку з попереднім нулем із зірочкою й т.д. Отже, ланцюжок утвориться пересуванням від 0' до 0* по стовпці, від 0* до 0' по рядку й т.д.

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

Далі над елементами ланцюжка, що знаходяться на непарних місцях ( 0' ) ставимо зірочки, знищуючи їх над парними елементами (0*). Потім знищуємо всі штрихи над елементами Сk і знаки виділення '+'. Кількість незалежних нулів буде збільшено на одиницю. На цьому (k+1)-а ітерація закінчена.

Третій етап. До цього етапу переходять після першого, якщо всі нулі матриці Сk виділені. У такому випадку серед невиділених елементів Сk вибирають мінімальний і позначають його h (h>0). Далі віднімають h із всіх елементів матриці Сk, розташованих у невиділених рядках і додають до всіх елементів, розташованим у виділених стовпцях. У результаті одержують нову матрицю Сk', еквівалентну Сk. Помітимо, що при такому перетворенні, всі нулі із зірочкою матриці Сk залишаються нулями й у Сk', крім того, у ній з'являються нові невиділені нулі. Тому переходять знову до першого етапу. Завершивши перший етап, залежно від його результату або переходять до другого етапу, або знову повертаються до третього етапу.

Після кінцевого числа повторень черговий перший етап обов'язково закінчиться переходом на другий етап. Після його виконання кількість незалежних нулів збільшиться на одиницю й (k+1)-а ітерація буде закінчена.

5.3. Приклад розв’язання задачі за допомогою угорського методу

Нехай в результаті вирішення основної транспортної задачі ми отримали оптимальні обсяги перевезень xij>=0  у кількості (m+n–1). З урахуванням матриці відстаней  можна отримати відповідну матрицю обсягів транспортної роботи (ТР)  , причому кількість її ненульових елементів також дорівнює (m+n–1).

Перенумеруємо всі ненегативні обсяги ATPij від 1 до (m+n–1), рухаючись послідовно по кожному рядку матриці обсягів ТР зверху до низу. В результаті отримуємо матрицю-строку А = {Aj}, (), де N = (m+n– 1) – кількість необхідних ТР.

Припустимо, що для виконання спланованих обсягів перевезень передбачено також N транспортних засобів (ТЗ), кожний з котрих характеризується деякою продуктивністю виконання одиниці тієї чи іншої ТР (Пij – продуктивність виконання i – м ТЗ  j – ї ТР, де ,  ). Очевидно, що термін виконання  j – ї ТР i – им ТЗ дорівнює

З метою застосування при розв’язанні цієї задачі алгоритму угорського методу призведемо з матрицею Tрч – матрицею робочого часу виконання ТЗ відповідних транспортних робіт наступні перетворення, а саме:

  •  знайдемо у матриці T максимальне значення – саму довгу за терміном виконання транспортну роботу;
  •  потім порахуємо за який робочий час tроб буде вона виконана, причому час виконання буде кратним 8 (кількості робочих годин у зміну);
  •  побудуємо нову матрицю Tвч, елементи якої   означають вільний час, який залишиться після виконання усіма ТЗ відповідних транспортних робіт.    

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

,     (1)

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

Розглянемо вищеописану методику на конкретному прикладі – оптимальному плану перевезень вантажу з табл. 55, який був отриманий за допомогою методу потенціалів (див. табл. 56).

Таблиця 56

ТТ з оптимальним планом перевезень вантажу

B1

B2

B3

B4

Запасиai

A1

4

7

2

70

5

30

100

A2

3

80

6

1

 40

8

120

A3

9

3

100

6

2

40

140

Заявки

bj

80

100

110

70

360

З табл. 56 формуємо матрицю-строку А = {Aj}, (), де N = (m+n– 1) – кількість необхідних ТР: 70×2 = 140; 30×5 = 150; 80×3 = 240; 40×1 = 40; 100×3 =

300; 40×2 = 80.  Припустимо, що задана матриця Пij–продуктивності виконання i–м ТЗ  j–ї ТР:

 

10

20

30

40

10

20

30

40

10

20

30

40

П =

40

30

20

10

40

30

20

10

40

30

20

10

10

30

20

40

10

30

20

40

10

30

20

40

Розрахуємо по формулі (з приведенням до цілого числа) матрицю Tрч – матрицю робочого часу виконання ТЗ відповідних транспортних робіт:

14

8

8

1

30

4

5

4

24

2

10

2

Трч=

4

5

12

4

8

3

7

15

6

1

15

8

14

5

12

1

30

3

7

4

24

1

15

2

Побудуємо нову матрицю Tвч, елементи якої із розрахунку  tроб = 8(8 годин у зміну)×4(зміни) = 32 години:

18

24

24

31

2

28

27

28

8

30

22

30

Твч=

28

27

20

28

24

29

25

17

26

31

17

24

18

27

20

31

2

29

25

28

8

31

17

30

При рішенні завдання використаємо наступні позначення: знак виділення '+', що підлягає знищенню, обводимо кружком.

Попередній етап. Відшукуємо максимальний елемент першого стовпця – 28. Віднімаємо з нього всі елементи цього стовпця. Аналогічно для одержання другого, третього, четвертого, п’ятого й шостого стовпців нової матриці віднімаємо всі елементи цих стовпців від 28, 26, 31, 24 і 30 відповідно. Одержимо матрицю С0(C0~Твч).

10

4

2

0

22

2

1

0

18

1

2

0

С0=

0

1

6

3

0

1

3

11

0

0

7

6

10

1

6

0

22

1

3

0

18

0

7

0

Тому що в кожному рядку С0 є хоча б один нуль, то на цьому процес приведення матриці закінчується. Далі шукаємо й відзначаємо знаком '*' незалежні нулі в С0, починаючи з першого рядка. Число незалежних нулів дорівнює 5 (5 ≠ n(6)), тому переходимо на першу ітерацію.  

10

4

2

0*

22

2

1

0*

18

1

2

0

С0=

0*

1

6

3

0

1

3

11

0*

0

7

6

10

1

6

0

22

1

3

0

18

0

7

0*

Перша ітерація

Виділяємо знаком '+' перший, другий, третій, четвертий і шостий стовпці матриці C0, які містять 0*.

Перший етап. Переглядаємо невиділений п’ятий стовпець, знаходимо в ньому невиділений нуль C035 = 0, відзначаємо його штрихом і виділяємо знаком '+' третій рядок. Переглядаємо цей рядок, знаходимо в ньому елемент  C031= 0* і знищуємо знак виділення першого стовпця, що містить 0*.

+

+

+

+

10

4

2

0*

22

2

1

0*

18

1

2

0

С0=

0*

1

6

3

0'

1

+

3

11

0*

0

7

6

10

1

6

0

22

1

3

0

18

0

7

0*

Далі переглядаємо цей перший стовпець (який уже став невиділеним) і відшукуємо у ньому невиділений нуль (або нулі). Таких нулів у цьому стовпці не має і також всі нулі матриці C0 виділені, тобто усі вони перебувають у виділених стовпцях або рядках, тому переходимо до третього етапу.

Третій етап. Вибираємо серед невиділених елементів C0 мінімальний і позначаємо його h (h > 0). У нашому випадку h = min {10, 22, 1, 2, 3, 7, 10, 22, 3, 7} = 1. Далі віднімаємо h із всіх цих невиділених елементів C0, і додаємо до всіх елементів, розташованих на пересічні виділених рядків і стовпців.

 

+

+

+

+

10

4

2

0*

22

2

1

0*

18

1

2

0

С0=

0*

1

6

3

0'

1

+

3

11

0*

0

7

6

10

1

6

0

22

1

3

0

18

0

7

0*

Отримуємо наступну модифікацію таблиці C'0 і переходимо до першого етапу.

+

+

+

+

9

4

2

0*

21

2

0

0*

18

1

1

0

С'0=

0*

2

7

4

0'

2

+

2

11

0*

0

6

6

9

1

6

0

21

1

2

0

18

0

6

0*

Перший етап. Переглядаємо невиділений перший стовпець, знаходимо в ньому невиділений нуль C'021 = 0, відзначаємо його штрихом і виділяємо знаком '+' другий рядок. Переглядаємо цей рядок, знаходимо в ньому елемент  C'022= 0* і знищуємо знак виділення другого стовпця, що містить 0*. Далі переглядаємо цей другий стовпець (який уже став невиділеним) і відшукуємо у ньому невиділений нуль (або нулі) – це C'062 = 0. Відзначаємо його штрихом і виділяємо знаком '+' шостий рядок. Переглядаємо цей рядок, знаходимо в ньому елемент  C'066= 0* і знищуємо знак виділення шостого стовпця, що містить 0*. Далі переглядаємо цей шостий стовпець (який уже став невиділеним) і відшукують у ньому невиділений нуль (або нулі). Таких нулів у цьому стовпці не має і також всі нулі матриці C0 виділені, тобто усі вони перебувають у виділених стовпцях або рядках, тому переходимо до третього етапу.

+

+

9

4

2

0*

21

2

0'

0*

18

1

1

0

+

С'0=

0*

2

7

4

0'

2

+

2

11

0*

0

6

6

9

1

6

0

21

1

2

0'

18

0

6

0*

+

Третій етап. Вибираємо серед невиділених елементів C'0 мінімальний і позначаємо його h (h > 0). У нашому випадку h = min {9, 4, 21, 2, 2, 11, 6, 6, 9, 1, 21, 1} = 1. Далі віднімаємо h із всіх цих невиділених елементів C'0, і додаємо до всіх елементів, розташованих на пересічні виділених рядків і стовпців.

+

+

9

4

2

0*

21

2

0'

0*

18

1

1

0

+

С'0=

0*

2

7

4

0'

2

+

2

11

0*

0

6

6

9

1

6

0

21

1

2

0'

18

0

6

0*

+

Отримуємо наступну модифікацію таблиці C''0 і переходимо до першого етапу.

+

+

8

3

2

0*

20

1

0'

0*

19

2

1

0

+

С''0=

0*

2

8

5

0'

2

+

1

10

0*

0

5

5

8

0

6

0

20

0

2

0'

19

1

6

0*

+

Перший етап. Перший невиділений нуль C''052 = 0 знаходиться у другому стовпці, який перетинається з п’ятим рядком. Переглядаємо цей рядок і не знаходимо в ньому незалежного нуля 0*. Тому відмічаємо його штрихом і переходимо до другого етапу.

+

+

8

3

2

0*

20

1

0'

0*

19

2

1

0

+

С''0=

0*

2

8

5

0'

2

+

1

10

0*

0

5

5

8

0'

6

0

20

0

2

0'

19

1

6

0*

+

Другий етап. Починаючи з останнього відміченого нуля зі штрихом C''052 = 0', будуємо ланцюг, рухаючись від нього по стовпцю. Знаходимо нуль із зірочкою C''022= 0*, далі від нього рухаємося уздовж другого рядка й знаходимо нуль зі штрихом C''021 = 0'. Далі пересуваємося по першому стовпцю і знаходимо  нуль із зіркою C''031= 0*. Потім знаходимо нуль зі штрихом C''035 = 0', рухаючись уздовж третього рядка. На цьому ланцюг закінчується, тому що у п’ятому стовпці не має нулів із зірочкою.

Таким чином, ланцюг побудований: 0'52 → 0*22 → 0'21 → 0*31 → 0'35. Заміняємо у ланцюги штрих на зірочку й знищуємо зірочки над парними елементами ланцюга (0*52 → 022 → 0*21 → 031 → 0*35), а також всі знаки виділення стовпців і рядків. Після цієї ітерації кількість незалежних нулів у аналізованої матриці стало дорівнювати 6 (розмірності матриці С0) і тому алгоритм закінчує роботу. Шукані елементи призначення відповідають позиціям незалежних нулів матриці  С1 (тобто 0*).

8

3

2

0*

20

1

0*

0

19

2

1

0

С1=

0

2

8

5

0*

2

1

10

0*

0

5

5

8

0*

6

0

20

0

2

0

19

1

6

0*

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

F = Трч14 + Трч21 + Трч35 + Трч43 + Трч52 + Трч66 = 1 + 5 + 8 + 6 + 5 + 2 = 27 (умовних одиниць часу).

У додатку 7 наведений розрахунок цього ж самого прикладу у матричному процесорі Excel.

6. МАТРИЧНО-МЕРЕЖЕВА МОДЕЛЬ УПРАВЛІННЯ

ПЕРЕВЕЗЕННЯМИ ВАНТАЖІВ В ТС

Формування МММ управління перевезеннями вантажів у ТС включає декілька етапів. Розглянемо ці етапи на прикладі конкретної ТМ (рис. 2). На рис. 2 представлена ТМ, яка включає 3 пункту постачання – А1, А2 і А3; 7 пунктів споживання – В1, В2, В3, В4, В5, В6 і В7 та 2 транзитних пункту – С1 і С2 певного вантажу. Відстань між пунктами вказана на відповідних ребрах, обсяги поставок і заявок вантажу проставлені у відповідних графічних об'єктах транспортних вузлів.

Рис. 2. Транспортна мережа перевезень

Першим етапом формування МММ буде складання масиву відстаней між сусідніми вузлами ТМ, причому достатньо вказати відстань від пункту відправлення (ПВ) до пункту призначення (ПП) кожного ребра графу в одному напрямку, так як відстань в зворотному напрямку передбачається той же самою (табл. 57). Слід зазначити той факт, що цей етап припускає ручне складання масиву.

На другому етапі автоматично  (за допомогою відповідної програми) по масиву відстаней будується матриця транспортних кореспонденцій між всіма вузлами ТМ. Відстань між не сусідніми (суміжними) вузлами проставляється рівним нескінченності (табл. 58). Матриця щодо її головної діагоналі має симетричний характер, тому що ми маємо справу з неорієнтованою транспортною мережею. Слід зазначити той факт, що величина нескінченності в програмі моделюється свідомо більшим кожного з відстаней ТМ - звичайно ця величина може дорівнювати сумі всіх існуючих відстаней на ТМ.

Таблиця 57

Масив відстаней між сусідніми вузлами ТМ

№

п/п

ПВ

ПП

Відстань

№

п/п

ПВ

ПП

Відстань

1

А1

В7

5

12

А3

В3

8

2

А1

А2

7

13

В1

С1

5

3

А1

С1

6

14

В1

В2

11

4

А1

В1

3

15

В2

С1

9

5

А2

В7

8

16

В2

В3

11

6

А2

В6

9

17

В3

С2

9

7

А2

В5

7

18

В4

С2

6

8

А2

С2

7

19

В4

В5

3

9

А2

С1

4

20

В5

В6

5

10

А3

С1

10

21

В6

В7

4

11

А3

С2

10

Таблиця 58

Матриця транспортних кореспонденцій

між всіма вузлами ТМ

А1

А2

А3

В1

В2

В3

В4

В5

В6

В7

С1

С2

А1

∞

7

∞

3

∞

∞

∞

∞

∞

5

6

∞

А2

7

∞

∞

∞

∞

∞

∞

7

9

8

4

7

А3

∞

∞

∞

∞

∞

8

∞

∞

∞

∞

10

10

В1

3

∞

∞

∞

11

∞

∞

∞

∞

∞

5

∞

В2

∞

∞

∞

11

∞

11

∞

∞

∞

∞

9

∞

В3

∞

∞

8

∞

11

∞

∞

∞

∞

∞

∞

9

В4

∞

∞

∞

∞

∞

∞

∞

3

∞

∞

∞

6

В5

∞

7

∞

∞

∞

∞

3

∞

5

∞

∞

∞

В6

∞

9

∞

∞

∞

∞

∞

5

∞

4

∞

∞

В7

5

8

∞

∞

∞

∞

∞

∞

4

∞

∞

∞

С1

6

4

10

5

9

∞

∞

∞

∞

∞

∞

∞

С2

∞

7

10

∞

∞

9

6

∞

∞

∞

∞

∞

Метод найкоротших маршрутів (МHМ) є методом третього етапу формування МММ. Цей метод (модифікований метод Дейкстри), використовуючи дані матриці кореспонденцій (див. табл. 58), знаходить як значення найкоротших відстаней на ТМ від кожного постачальника вантажу до кожного його споживача (табл. 59), так і відповідні цим відстаням маршрути, які можуть містити проміжні пункти на шляхах переміщення вантажу (див. рис. 3).

Таблиця 59

Матриця найкоротших відстаней на ТМ

В1

В2

В3

В4

В5

В6

В7

А1

3

14

23

17

14

9

5

А2

9

13

16

10

7

9

8

А3

15

19

8

16

19

23

21

А1В1     =  3;    А2С1В1 =  9;

А1В1В2   =14;    А2С1В2 =13;

А1А2С2В3  =23;    А2С2В3 =16;

А1А2В5В4  =17;    А2В5В4 =10;

А1А2В5   =14;    А2В5   =  7;

А1В7В6   =  9;    А2В6   =  9;

А1В7     =  5;    А2В7   =  8;

А3С1В1  =15;

А3В3В2  =19;

А3В3    =  8;

А3С2В4  =16;

А3С2В4В5 =19;

А3С1А2В6 =23;

А3С1А1В6 =21;

Рис. 3. Маршрути найкоротших відстаней

Четвертий етап полягає в складанні за вихідними даними ТМ (рис. 2) і отриманими даними табл. 58 класичної ТТ (табл. 60) і розв'язання отриманої ТЗ стандартними методами – спочатку складання опорного плану перевезень (допустимо методом мінімального вузла відправлення-одержання вантажу (див. табл. 60)) і подальше його поліпшення (наприклад методом потенціалів).

У результаті проведених перетворень ми маємо збалансовану, не вироджену ТЗ. Вартість реалізації цієї ТЗ при вартості 1 ткм рівною 1 у.г.о. складе:

L0 = 1 у.г.о. × (30 × 3 + 30 × 14 + 60 × 9 + 80 × 5 + 30 × 13 + 120 × 10 +

+ 50 × 7 + 40 × 19 + 60 × 8) =  4630 у.г.о.

Побудуємо потенціали всіх рядків і стовпців ТТ або вершин ТМ (табл. 61) і перевіримо всі її вільні від перевезень клітки на предмет перерозподілу в них вантажопотоків:

A1B3:0+3=3<23;    A1B4:0+11=11<17;   A1B5:0+8=8<14;

A2B1:-1+3=2< 9;    A2B3:-1+3=2 < 16;   A2B6:-1+9=8< 9;    A2B7:-1+5=4<8;

A3B1:5+3=8<15;    A3B4:5+11=16=16;  A3B5:5+8=13<19;   A3B6:5+9=14<23;

A3B7:5+5=10<21.

Таблиця 60

Опорний план перевезень

B1

B2

B3

B4

B5

B6

B7

Запаси

ai

Ci

A1

3

30

14

30

23

17

14

9

60

5

80

200

859

A2

9

13

30

16

10

120

7

50

9

8

200

728

A3

15

19

40

8

60

16

19

23

21

100

12110

Замовлення bj

30

100

60

120

50

60

80

500

500

Cj

271

466

477

435

403

414

342

Таблиця 61

ТТ з потенціалами

B1

B2

B3

B4

B5

B6

B7

Ui

A1

3

30

14

30

23

17

14

9

60

5

80

0

A2

9

13

30

16

10

120

7

50

9

8

-1

A3

15

19

40

8

60

16

19

23

21

5

Uj

3

14

3

11

8

9

5

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

Перейдемо до останнього п'ятого етапу формування МММ – етапу представлення результатів знайденого оптимального плану перевезень на ТМ.

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

По маршруту з А1 до В1 довжиною в 3 км веземо 30 т вантажу.

По маршруту з А1 до В1 довжиною в 3 км, потім з В1 до В2 довжиною в 11 км веземо 30 т вантажу.

По маршруту з А1 до В7 довжиною в 5 км, потім з В7 до В6 довжиною в 4 км веземо 60 т вантажу.

По маршруту з А1 до В7 довжиною в 5 км веземо 80 т вантажу.

По маршруту з А2 до С1 довжиною в 4 км, потім з С1 до В2 довжиною в 9 км веземо 30 т вантажу.

По маршруту з А2 до В5 довжиною в 7 км, потім з В5 до В4 довжиною в 3 км веземо 120 т вантажу.

По маршруту з А2 до В5 довжиною в 7 км веземо 50 т вантажу.

По маршруту з А3 до В3 довжиною в 8 км, потім з В3 до В2 довжиною в 11 км веземо 40 т вантажу.

По маршруту з А3 до В3 довжиною в 8 км веземо 60 т вантажу.

Рис. 4. Розподіл оптимальних маршрутів перевезення вантажу на ТМ

Структура розрахунково-пояснювальної записки до курсового проекту має включати такі документи:

Титульний лист (Додаток 8);

Лист завдання на курсове проектування (Додаток 9);

Зміст;

Опис завдання на курсове проектування згідно обраному варіанту;

Вступ у якому дається статистична інформація про міжнародні вантажні

перевезення на території України за останні 5 років;

Теоретичні відомості про обрані методи:

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

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

відповідні Excel-таблиці;

Висновки;

Список використаної літератури;

Додатки.

7. ЛІТЕРАТУРА

  1.  Кунда Н.Т. Дослідження операцій у транспортних системах. / Н.Т. Кунда // Навчальний посібник для студентів напряму «Транспортні технології» вищих навчальних закладів. – К.: Видавничій дім «Слово», 2008. – 400 с.
  2.  Четверухін Б. М. Дослідження операцій в транспортних системах // Б.М. Четверухін // Частина І. Методи лінійного програмування та їх застосування. – К.:УТУ, 2000. – 91 с.
  3.  Зайченко Ю. П. Дослідження операцій / Ю.П. Зайченко // Навчальний посібник. – К.: ЗАТ ‘ВІПОЛ’, 2000. – 688 с.
  4.  Четверухін Б. М. Дослідження операцій в транспортних системах // Б.М. Четверухін // Частина 3. Спеціальні методи дослідження операцій. – К.:УТУ, 2004. – 148 с.
  5.  Прокудін Г.С. Модифікація методу Дейкстри стосовно розв’язання сітьових транспортних задач / Г.С. Прокудін // Вісник НТУ та ТАУ, № 7. – Київ : НТУ, 2002. – С. 195–198
  6.  Четверухін Б.М. Оптимізація перевезень вантажів у сітьової постановці / Б.М. Четверухін, Г.С. Прокудін, С.О. Білоус // Вісник НТУ та ТАУ, № 8. – Київ : НТУ, 2003. – С. 93–100
  7.  Четверухін Б.М. Моделі та алгоритми розв’язання сітьових транспортних задач великої розмірності / Б.М. Четверухін, Г.С. Прокудін // Автошляховик України. Окремий випуск віснику Північного наукового центру ТАУ. – К.: 2004. – № 7. – С. 11–15
  8.  Прокудін Г.С. Модель комплексных перевозок в транспортных системах / Г.С. Прокудін // Проблеми інформатизації та управління, вип. 12. – К.: НАУ, 2005. – С. 138–142
  9.  Прокудін Г.С. Моделі і методи оптимізації перевезень у  транспортних системах / Г.С. Прокудін. –  К.: НТУ, 2006. – 224 с.
  10.  Прокудін Г.С. Розв'язання мережевих транспортних задач у середовищі Excel / Г.С. Прокудін // Проблеми транспорту, вип. 4. – К.: НТУ, 2007. – С. 23–30
  11.  Прокудін Г.С. Приклад організації вантажних перевезень на транспортної мережі України / Г.С. Прокудін // Управління проектами, системний аналіз і логістика, вип. 5. – К.: НТУ, 2008. – С. 150–158
  12.  Прокудін Г.С. Система підтримки прийняття рішень по оптимальному управлінню не збалансованими вантажними перевезеннями: Свідоцтво про внесення суб'єкта підприємн. діяльн. до Реєстру виробн. та розповсюдж. прогр. забезп. /  Г.С. Прокудін,  М.М. Дмитрієв. – Серія ВР, № 00932, Україна, МОН – ід. код 02070915; заяв. 18.06.08; опуб. 25.06.08. – 66 с.
  13.  Прокудін Г.С. Програмний комплекс оптимізації вантажних перевезень симплексним методом: Свідоцтво про внесення суб'єкта підприємн. діяльн. до Реєстру виробн. та розповсюдж. прогр. забезп. /  Г.С. Прокудін,  М.М. Дмитрієв. – Серія ВР, № 00933, Україна, МОН – ід. код 02070915; заяв. 18.06.08; опуб. 25.06.08. – 10 с.
  14.  Прокудін Г.С. Програмно-інструментальний комплекс оптимізації вантажних перевезень на транспортній системі України: Свідоцтво про внесення суб'єкта підприємн. діяльн. до Реєстру виробн. та розповсюдж. прогр. забезп. /  Г.С. Прокудін,  М.М. Дмитрієв. – Серія ВР, № 00941, Україна, МОН – ід. код 02070915; заяв. 18.06.08; опуб. 25.06.08. – 60 с.
  15.  Прокудін Г.С. Програма пошуку найкоротших відстаней на транспортній мережі за допомогою матричного методу: свід-во про внесення суб'єкта підприємн. діяльн. до Реєстру виробн. та розповсюдж. прогр. забезп. /  Г.С. Прокудін,  М.М. Дмитрієв. – Серія ВР, № 00942, Україна, МОН – ід. код 02070915; заяв. 18.06.08; опуб. 25.06.08. – 7 с.
  16.  Прокудін Г.С. Моделі та методи оптимізації вантажних перевезень в транспортних системах / / Г.С. Прокудін // Автореф. докт. дисер. – К.: НТУ, 2009. – 43 с.
  17.  Прокудін Г.С. Інформаційна система оптимізації вантажних перевезень в транспортних системах / Г.С. Прокудін, В.Д. Данчук, О.Г. Прокудін // Проблеми транспорту, вип. 6. – К.: НТУ, 2010. – С. 90–95
  18.  Прокудін Г.С. Організація вантажних перевезень на транспортних мережах з обмеженнями на їх пропускні можливості / Г.С. Прокудін // Електроніка та системи управління, № 1(27). – К.: НАУ, 2011. – С. 115 – 121
  19.   Прокудін Г.С. Оптимізація вантажних перевезень в транспортних системах / Г.С. Прокудін, О.Г. Прокудін // Електроніка та системи управління, № 1(27). – К.: НАУ, 2011. – С. 128 – 133
  20.  Прокудін Г.С. Розв'язання багатоетапних транспортних задач / Г.С. Прокудін, О.Г. Прокудін, С.М. Печенко // Управління проектами, системний аналіз і логістика, Вип. 8. –  К.: НТУ, 2011. – С. 159 – 163
  21.  Прокудін Г.С. Підвищення ефективності управління перевезеннями легкових автомобілів / Г.С. Прокудін, О.С. Дудник // Управління проектами, системний аналіз і логістика, Вип. 8. –  К.: НТУ, 2011. – С. 154 – 158  

Додаток 1

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

   Варіант № 1       Варіант № 2

   Варіант № 3       Варіант № 4

   Варіант № 5       Варіант № 6

   Варіант № 7        Варіант № 8

   Варіант № 9       Варіант № 10

   Варіант № 11       Варіант № 12

   Варіант № 13       Варіант № 14

   Варіант № 15      Варіант № 16

   Варіант № 17        Варіант № 18

   Варіант № 19       Варіант № 20

   Варіант № 21       Варіант № 22

   Варіант № 23       Варіант № 24

   Варіант № 25       Варіант № 26

   Варіант № 27        Варіант № 28

   Варіант № 29       Варіант № 30

Додаток 2

Обсяги поставок і замовлень продукції до структур ТМ

з номерами варіантів від 1-го до 15-го

Передостання

цифра у №

залікової книжки

Поставки

Заявки

а1

а2

а3

b1

b2

b3

b4

0

8

10

12

6

7

8

9

1

12

8

10

9

6

7

8

2

10

12

8

8

9

6

7

3

8

10

12

7

8

9

6

4

12

8

10

6

7

8

9

5

10

12

8

9

6

7

8

6

8

10

12

8

9

6

7

7

12

8

10

7

8

9

6

8

10

12

8

6

7

8

9

9

8

10

12

9

6

7

8

Обсяги поставок і замовлень продукції до структур ТМ

з номерами варіантів від 16-го до 30-го

Передостання

цифра у №

залікової книжки

Поставки

Заявки

а1

а2

а3

a4

b1

b2

b3

0

6

7

8

9

8

10

12

1

9

6

7

8

12

8

10

2

8

9

6

7

10

12

8

3

7

8

9

6

8

10

12

4

6

7

8

9

12

8

10

5

9

6

7

8

10

12

8

6

8

9

6

7

8

10

12

7

7

8

9

6

12

8

10

8

6

7

8

9

10

12

8

9

9

6

7

8

8

10

12

Додаток 3

Вартість перевезення одиниці вантажу між сусідніми вузлами ТМ

Остання

цифра у №

залікової книжки

Номера шляхів

1

2

3

4

5

6

7

8

9

10

11

12

13

14

0

2

3

1

4

5

6

1

2

2

2

3

4

5

6

1

6

2

3

1

4

5

6

1

2

2

2

3

4

5

2

5

6

2

3

1

4

5

6

1

2

2

2

3

4

3

4

5

6

2

3

1

4

5

6

1

2

2

2

3

4

3

4

5

6

2

3

1

4

5

6

1

2

2

2

5

2

3

4

5

6

2

3

1

4

5

6

1

2

2

6

2

2

3

4

5

6

2

3

1

4

5

6

1

2

7

2

2

2

3

4

5

6

2

3

1

4

5

6

1

8

1

2

2

2

3

4

5

6

2

3

1

4

5

6

9

6

1

2

2

2

3

4

5

6

2

3

1

4

5

Додаток 4

Матриця Пij – продуктивності виконання i–м ТЗ  j–ї ТР

 

2

3

4

5

2

3

4

5

2

3

4

5

П =

5

4

3

2

5

4

3

2

5

4

3

2

1

3

2

4

1

3

2

4

1

3

2

4


Додаток 5

Перша СТ

СТ0

Х1

Х2

Х3

Х4

Х5

Х6

Х7

Х8

Х9

Х10

Х11

Х12

Х13

Х14

Х15

Х16

Х17

Х18

СБi

XБi

BБi

4

7

2

5

3

6

1

8

9

3

6

2

56

56

56

56

56

56

56

13

100

1

1

1

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

56

14

120

0

0

0

0

1

1

1

1

0

0

0

0

0

1

0

0

0

0

56

15

140

0

0

0

0

0

0

0

0

1

1

1

1

0

0

1

0

0

0

56

16

80

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

0

56

17

100

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

56

18

110

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

min=

110

C0 =

36400

108

105

110

51

109

106

111

48

103

109

106

54

0

0

0

0

0

0

max=

111

Друга СТ

СТ1

Х1

Х2

Х3

Х4

Х5

Х6

Х7

Х8

Х9

Х10

Х11

Х12

Х13

Х14

Х15

Х16

Х17

Х18

СБi

XБi

BБi

4

7

2

5

3

6

1

8

9

3

6

2

56

56

56

56

56

56

56

13

100

1

1

1

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

56

14

10

0

0

-1

0

1

1

0

1

0

0

-1

0

0

1

0

0

0

-1

min=

10

56

15

140

0

0

0

0

0

0

0

0

1

1

1

1

0

0

1

0

0

0

56

16

80

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

0

56

17

100

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

1

7

110

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

C1 =

24190

108

105

-1

51

109

106

0

48

103

109

-5

54

0

0

0

0

0

-111

max=

109

Третя СТ

СТ2

Х1

Х2

Х3

Х4

Х5

Х6

Х7

Х8

Х9

Х10

Х11

Х12

Х13

Х14

Х15

Х16

Х17

Х18

СБi

XБi

BБi

4

7

2

5

3

6

1

8

9

3

6

2

56

56

56

56

56

56

56

13

100

1

1

1

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

3

5

10

0

0

-1

0

1

1

0

1

0

0

-1

0

0

1

0

0

0

-1

56

15

140

0

0

0

0

0

0

0

0

1

1

1

1

0

0

1

0

0

0

56

16

70

1

0

1

0

0

-1

0

-1

1

0

1

0

0

-1

0

1

0

1

56

17

100

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

min=

100

1

7

110

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

C2 =

23100

108

105

108

51

0

-3

0

-61

103

109

104

54

0

-109

0

0

0

-2

max=

109

Четверта СТ

СТ3

Х1

Х2

Х3

Х4

Х5

Х6

Х7

Х8

Х9

Х10

Х11

Х12

Х13

Х14

Х15

Х16

Х17

Х18

СБi

XБi

BБi

4

7

2

5

3

6

1

8

9

3

6

2

56

56

56

56

56

56

56

13

100

1

1

1

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

3

5

10

0

0

-1

0

1

1

0

1

0

0

-1

0

0

1

0

0

0

-1

56

15

40

0

-1

0

0

0

-1

0

0

1

0

1

1

0

0

1

0

-1

0

56

16

70

1

0

1

0

0

-1

0

-1

1

0

1

0

0

-1

0

1

0

1

min=

70

3

10

100

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

1

7

110

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

C3 =

12200

108

-4

108

51

0

-112

0

-61

103

0

104

54

0

-109

0

0

-109

-2

max=

108

П’ята СТ

СТ4

Х1

Х2

Х3

Х4

Х5

Х6

Х7

Х8

Х9

Х10

Х11

Х12

Х13

Х14

Х15

Х16

Х17

Х18

СБi

XБi

BБi

4

7

2

5

3

6

1

8

9

3

6

2

56

56

56

56

56

56

56

13

30

0

1

0

1

0

1

0

1

-1

0

-1

0

1

1

0

-1

0

-1

3

5

10

0

0

-1

0

1

1

0

1

0

0

-1

0

0

1

0

0

0

-1

56

15

40

0

-1

0

0

0

-1

0

0

1

0

1

1

0

0

1

0

-1

0

min=

40

4

1

70

1

0

1

0

0

-1

0

-1

1

0

1

0

0

-1

0

1

0

1

3

10

100

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

1

7

110

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

C4 =

4640

0

-4

0

51

0

-4

0

47

-5

0

-4

54

0

-1

0

-108

-109

-110

max=

54

Шоста СТ

СТ5

Х1

Х2

Х3

Х4

Х5

Х6

Х7

Х8

Х9

Х10

Х11

Х12

Х13

Х14

Х15

Х16

Х17

Х18

Сбi

XБi

BБi

4

7

2

5

3

6

1

8

9

3

6

2

56

56

56

56

56

56

56

13

30

0

1

0

1

0

1

0

1

-1

0

-1

0

1

1

0

-1

0

-1

min=

30

3

5

10

0

0

-1

0

1

1

0

1

0

0

-1

0

0

1

0

0

0

-1

2

12

40

0

-1

0

0

0

-1

0

0

1

0

1

1

0

0

1

0

-1

0

4

1

70

1

0

1

0

0

-1

0

-1

1

0

1

0

0

-1

0

1

0

1

3

10

100

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

1

7

110

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

C5 =

2480

0

50

0

51

0

50

0

47

-59

0

-58

0

0

-1

-54

-108

-55

-110

max=

51

Сьома СТ

СТ6

Х1

Х2

Х3

Х4

Х5

Х6

Х7

Х8

Х9

Х10

Х11

Х12

Х13

Х14

Х15

Х16

Х17

Х18

Сбi

XБi

BБi

4

7

2

5

3

6

1

8

9

3

6

2

56

56

56

56

56

56

5

4

30

0

1

0

1

0

1

0

1

-1

0

-1

0

1

1

0

-1

0

-1

3

5

10

0

0

-1

0

1

1

0

1

0

0

-1

0

0

1

0

0

0

-1

2

12

40

0

-1

0

0

0

-1

0

0

1

0

1

1

0

0

1

0

-1

0

4

1

70

1

0

1

0

0

-1

0

-1

1

0

1

0

0

-1

0

1

0

1

3

10

100

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

1

7

110

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

C6 =

950

0

-1

0

0

0

-1

0

-4

-8

0

-7

0

-51

-52

-54

-57

-55

-59


Додаток 6

Додаток 7

Додаток 8

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТРАНСПОРТНИЙ УНІВЕРСИТЕТ

КАФЕДРА «МІЖНАРОДНІ ПЕРЕВЕЗЕННЯ ТА МИТНИЙ КОНТРОЛЬ»

КУРСОВОЙ ПРОЕКТ

 

з навчальної дисципліни «ДОСЛІДЖЕННЯ ОПЕРАЦІЙ В ТРАНСПОРТНИХ СИСТЕМАХ»

на  тему

«РАЦІОНАЛЬНА ОРГАНІЗАЦІЯ ВАНТАЖНИХ ПЕРЕВЕЗЕНЬ

НА ТРАНСПОРТНИХ МЕРЕЖАХ»

для студентів спеціальності

«Організація перевезень і управління на автомобільному транспорті»

Варіант № 1

Виконав: студент групи МП-ІIІ-1

Акіменко О.А.

Перевірив: проф. Прокудін Г.С.

Київ 2012

Додаток 9

ЗАТВЕРДЖЕНО

Завідуючим кафедрою "Міжнародні перевезення та митний контроль"

             проф. Прокудін Г.С.

            “01”  жовтня 2012 р.

Національний транспортний університет

(назва вищого навчального закладу)

Кафедра      Міжнародних перевезень та митного контролю

Дисципліна Дослідження операцій в транспортних системах

Напрям підготовки                   Транспортні технології

Спеціальність                            Організація перевезень і управління на транспорті
Курс   3         Група  Семестр  5

ЗАВДАННЯ

на курсову роботу студента

(прізвище, ім'я, по батькові)

1. Тема проекту (роботи) Раціональна організація вантажних перевезень

в транспортних системах

  1.  Строк здачі студентом закінченого проекту (роботи) – 24 грудня 2012 р.
  2.  Вихідні дані до роботи 3.1. Структура транспортної мережі  3.2. Обсяги перевезень ван-

тажу  3.3. Вартості перевезень вантажу  3.4. Метод складання опорного плану перевезень   3.5. Метод

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

4. Зміст розрахунково-пояснювальної записки (перелік питань, які підлягають розробці)

4.1. Складання опорного плану перевезень 4.2. Отримання оптимального плану перевезень

4.3. Закріплення рухомого складу за отриманим комплексом транспортних робіт

5. Перелік графічного матеріалу (з точним зазначенням обов'язкових креслень)

5.1. Excel-таблиця отримання оптимального плану перевезень  5.2. Excel-таблиця закріплення

рухомого складу за отриманим комплексом транспортних робіт

6. Дата видачі завдання 22 жовтня 2012 р.




1. Game Make Up a Story
2. культура в своем современном значении появился в Европе в произведениях мыслителей XVIII века Монтескье Вик
3. Это наука о связях между живыми существами и окружающей их средой между человеком и природой
4. Реферат- Явление молнии в природе
5. Как Люфтваффе считали свои победы
6. не верно. Театр Файясайн В этой части я хочу предложить несколько рабочих медитативных схем с помощью
7. Повышение качества продукции основа экономической эффективности
8.  Тип каникул нужное подчеркнуть- по четвертям-по триместрам-другое а именно- Номер св.
9. на тему- ldquo; Конституционноправовой статус главы суверенного государства rdquo; Слуш
10. тематики. Автор ряда работ по микологии и сравнительной анатомии

Материалы собраны группой SamZan и находятся в свободном доступе