67466

ТРАНСПОРТНА ЗАДАЧА. ЗНАХОДЖЕННЯ ПОЧАТКОВОГО ОПОРНОГО ПЛАНУ МЕТОДОМ МІНІМАЛЬНОГО ЕЛЕМЕНТУ

Лекция

Логистика и транспорт

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

Украинкский

2014-09-10

329.5 KB

2 чел.

Міністерство освіти і науки України
Інститут підприємництва та перспективних технологій
при Національному університеті “Львівська політехніка”

ТРАНСПОРТНА ЗАДАЧА. ЗНАХОДЖЕННЯ ПОЧАТКОВОГО ОПОРНОГО ПЛАНУ МЕТОДОМ МІНІмального елементу

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

до лабораторної роботи  
з курсу “Логістика
 еколого-економічних процесів”

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

“Комп’ютерні науки” спеціальності
“Інтелектуальні системи прийняття рішень” (7.080.404)

Затверджено

    на засіданні кафедри ІСМ.

Протокол №  від 25.10.2006 р.

Львів –2006


Транспортна задача. Знаходження початкового опорного плану методом мінімального елементу
. Інструкція до лабораторної роботи з курсу “Логістика еколого-економічних процесів” для студентів базового напрямку “Комп’ютерні науки” / Укл. Я. П.Кісь, — Львів: Інститут підприємництва та перспективних технологій при Національному університеті “Львівська політехніка”, 2006.—8ст.

Укладачі     Я. П. Кісь

Відповідальний за випуск  д.т.н., проф. Я.М.Матвійчук

Рецензенти:    к.е.н., доц. А.Ю.Берко,

   к.т.н., доц. О.М.Верес

 


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

Теоретичні відомості

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

Необхідно перевезти однорідний продукт з пунктів зберігання в пункти споживання таким чином, щоб сумарна вартість перевезень була мінімальною. Наявно m пунктів зберігання А1, А2,  ... , Аm і n пунктів споживання В1, B2, ... , Bn. Запас продукту в кожному і-тому пункті зберігання Аі становить аі , а в кожному і-тому пункті споживання Вj становить bj. Вартість перевезення одиниці продукту з пункту Аі в пункт Вj становить сij. Необхідно перевезти продукти зі складів в пункти споживання таким чином, щоб задовольнити потреби і забезпечити мінімальну вартість перевезень.

Нехай xij – кількість продукту перевезеного  з пункту Аі в пункт Вj. У такому випадку формальна постановка задачі матиме такий вигляд:

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

  •  Закритого типу.:
  •  Відкритого типу

У випадку задачі відкритого типу має місце рівність:

У протилежному випадку транспортна задача буде відкритого типу.

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

  •  Фіктивний пункт споживання

  •  Фіктивний пункт постачання

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

  1.   (початкового базового розв’язку).
  2.  Покрокове покращення плану перевезень до моменту досягнення оптимуму.

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

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

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

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

Позначення клітинок

 

Хід роботи

1. Ознайомитись з змістовною постановкою транспортної задачі.

2. Розглянути математичну постановку транспортної задачі.

3. Ознайомитись з типами транспортної задачі.

4. Вивчити метод мінімального елемента.

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

6. За допомогою написаної програми згідно індивідуального завдання знайти початковий опорний план транспортної задачі.

7. Оформити звіт

Зміст звіту

1. Короткі теоретичні відомості.

2. Умова індивідуального завдання.

4. Текст програми.

5. Результати роботи програми.

6. Висновки.

Література

  1.  Акулич И. “Математическое програмирование в примерах и задачах” М.: Высшая школа, 1986
  2.  Йенсен П. Барнес Д. “Потоковое програмирование” М.: Радио и связь, 1984
  3.  Катренко А. “Дослідження операцій. Матеріали до лекційного курсу” Л. 1999
  4.  Кристофидес Н. “Теория графов. Алгоритмической подход” М.: Мир, 1978
  5.  Таха Х. “Введение в иследование операций” Т.1, М.: Мир, 1985

Варіанти завдань до лабораторної роботи

Варіанти індивідуальних завдань подаються у такому вигляді:

Варіант № 1

 11   1   2  83

 15   6   8  44

  6   5   9  14

 92  15  53

Варіант № 2

 11  11   5  74

  3   2   4  45

  6   2  10  53

 93  18  46

Варіант № 3

 12   2  12  84

  4   5   1  22

  5  11   1  97

 19  34  54

Варіант № 4

  5   5  15  49

  3  13   4  92

  7   2   6  62

 35  52  57

Варіант № 5

  2  10   6  88

  2  10  13  40

  2   2  11  45

 53  71  97

Варіант № 6

 13  12   8  86

  7  11   7  39

 11   2   2  70

 79  51  71

Варіант № 7

  2  12  10  44

 11   5  14  97

 10   2   7  48

 55  95  85

Варіант № 8

 12   2   4  40

  1   5   1  64

  4  12  10  39

 31  18  53

Варіант № 9

  2  15  10  84

  7   8   9  97

  1  15   3  88

 38  48  19

Варіант № 10

  8  14   9  99

  4   4   8  74

  5   1  11  87

 76  38  67

Варіант № 11

 13   4   3  30

  7   3   9  53

  7  12  10  39

 17  60  58

Варіант № 12

 11   1   4  50

  3   9   3  47

  7  12   3  95

 44  59  33

Варіант № 13

 13   4   5  60

  2  12   6  10

  5   6   5  34

 14  33  72

Варіант № 14

  5   5  10  27

  7   7  10  42

  7  11   2  45

 79  13  22

Варіант № 15

 11   2   2  84

 13   1   6  84

  9  13   9  35

 51  75  72

Варіант № 16

  1   1   1  71

  6   3   6  96

  4   8  14  51

 37  60  80

Варіант № 17

 12   3   6  26

  6   1   8  82

  1   3  13  74

 85  93  54

Варіант № 18

  2   6   7  80

 14   6   2  28

 11   1   7  61

 70  64  80

Варіант № 19

 15  14   4  29

  4   1   2  26

  6   8   2  56

 41  75  92

Варіант № 20

 10   3  13  82

 11   2   6  18

  3   2  12  22

 36  91  88

Варіант № 21

  8   5  12  67

  3  14  10  25

  4  10   2  67

 61  63  75

Варіант № 22

 11   8  12  25

  1   9  11  65

 13  15  12  78

 55  60  76

Варіант № 23

  7   9   5  40

  9  15   8  14

  3   9   2  37

 23  11  30

Варіант № 24

  4   3  12  29

  6   4  13  17

  4   7   6  89

 44  27  49

Варіант № 25

  3  12   2  59

  2   4   1  16

  3   6   3  46

 27  26  27


Навчальне видання

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

до лабораторної роботи  
з курсу “Логістика”

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

“Комп’ютерні науки” спеціальності
“Інтелектуальні системи прийняття рішень” (7.080.404)

Укладачі     Кісь Ярослав Петрович

Редактор

Комп’ютерне складання

Підписано до друку……..
Формат 70х100 1/16. Папір офсетний.

Друк на різографі. Умовн. друк. арк…… Обл.-вид. арк………..

Наклад …….. прим. Зам. ……

Поліграфічний центр

Видавництва Державного університету “Львівська політехніка”

вул. Ф. Колесси, 2, 79000, Львів


 

А также другие работы, которые могут Вас заинтересовать

85477. Сценарій родинного свята «Щастя бути разом» 74.5 KB
  Прекрасно, коли в сім’ї панують мир і злагода, взаєморозуміння, повага, кохання, вірність, теплота, затишок. Через сім’ю ми – діти, виходимо в суспільство. В сім’ї нам вручають естафету досвіду поколінь, котру ми повинні нести далі, щоб передати її своїм дітям і тим самим майбутньому.
85478. Батько і мати 47.5 KB
  Є скарби, заховані в землю, є такі, що розташовані на поверхні і передаються з покоління в покоління. чаруючи людську душу. До таких скарбів належать пам’ять роду, його звичаї, традиції. Мамина пісня, батьківська хата, бабусина вишиванка, дідусева казка - все це наша родослівна пам’ять.
85479. ДОЛЯ МОЄЇ РОДИНИ В ДОЛІ УКРАЇНИ 80 KB
  Формувати уявлення про родину як частину суспільства, про роль і місце родини в житті людини, дослідити минуле своїх родин, пов’язане з історією України; виховувати шанобливе ставлення до батьків, старших і молодших членів сім’ї, розвивати навички спілкування в сім’ї, що сприяють родоводу...
85480. Творчість Г.С.Сковороди 30.5 KB
  Вчитель: Добру справу завжди починають рукостисканням яке означає взаємоповагу довіру готовність спільно плідно працювати. Вчитель: Активізуємо наші знання про діалог. Що таке діалог Що повинні пам’ятати під час складання діалогу Вчитель: Перед вами конверти в них завдання: група отримала тему треба...
85481. Урок-путешествие по чтению «Сказки А.С.Пушкина» 47.5 KB
  А для кого они Для вас Мы знаем вы любите игры Песни загадки и пляски Но нет интересней для детворы Чем наши волшебные сказки. На какие две группы делятся все известные вам сказки Сказки бывают народные а бывают авторские Чем авторская сказка отличается от народной Авторы народных сказок...
85482. Ю.Збанацький «Гвардії Савочка» 1.7 MB
  Вчити учнів виразно читати та розуміти текст, навчати добору робочого матеріалу до роботи над текстом, розвивати читацькі інтереси учнів, навички стислого переказу, увагу, мовлення. Збагатити знання учнів про мужність народу в роки Великої Вітчизняної війни, участь у ній дітей, виховувати глибоку вдячність...
85483. Особенности развития мышления у подростков в условиях раннего выбора профильного обучения 1.48 MB
  В то же время повсеместное внедрение профильного обучения осуществляется на основе имеющихся образовательных ресурсов учебных заведений, которые далеко не всегда отвечают задачам модернизации образования – в этом случае может происходить простое натаскивание учащихся тем же педагогом за счет увеличения количества часов.
85484. Модель современного школьного издания 495 KB
  Среди наиболее часто называемых проблем современной молодёжи, решению которых также могут способствовать школьные СМИ, нередко упоминается её низкий интерес к чтению и к осмысленной работе с информацией вообще.
85485. Совершенствование методического обеспечения принятия решений о привлечении и погашении заимствований в системе управления государственным (региональным) долгом субъекта РФ на этапе её реформирования 760 KB
  Критерий привлечения заемных средств для финансирования капитальных расходов бюджета субъекта РФ. Критерий принятия решений о досрочном погашении долговых обязательств субъекта РФ в условиях избытка платежеспособности бюджета. Методика расчета относительной стоимости капитальных расходов бюджета.