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, Львів


 

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

47383. Разработка рекомендаций по эффективному использованию денежных средств на примере ООО «Вахрушевец» 967 KB
  На расчетном счете сосредотачиваются свободные денежные средства и поступления за реализованную продукцию, выполненные работы и услуги, краткосрочные и долгосрочные ссуды, получаемые от банка, и прочие зачисления
47384. Организация логистических процессов распределения товаров (на примере ОАО "Полоцкий молочный комбинат") 331.39 KB
  Предмет исследования: распределительная логистика Цель работы: обоснование актуальности создания распределительного центра продукции ОАО Полоцкий молочный комбинат в городе Риге обоснование актуальности использования услуг дистрибьютора в городе Пскове и актуальность внедрения логистического программного обеспечения на предприятии и оценка экономической эффективность предложенных мероприятий. Исследование и разработки: изучены основные аспекты логистических процессов распределения товаров проанализирована организация логистической...
47385. Разработка маркетинговой стратегии развития организации на примере ООО “Антарес” 170.01 KB
  Раздел 1 Маркетинг как философия производства Содержит анализ литературных источников посвященных рассмотрению теоретических аспектов маркетинга классификации услуг анализ потребителей и их потребностей сегментации рынка услуг по пошиву одежды особенностям стимулирования сбыта в данной отраслевой группе влияние рекламы как основного элемента коммуникационного воздействия на потребителя.1 Понятие маркетинга особенности маркетинга услуг.2 Эффективность внедряемой услуги 655 Правовая часть...
47386. Влияние самооценки на успешность обучения в младшем школьном возрасте 383.5 KB
  Широкое распространение феномена оценки в учебновоспитательном процессе школы послужило причиной того что оценивание учителем результатов учебной деятельности учащихся и самооценивание выделилось в последние годы в самостоятельное направление. Согласно теории учебной деятельности оценочная деятельность порождает потребность ученика или учителя получить информацию о том соответствует или нет качество знаний и умений учащихся по предмету требованиям программы. Целью оценочной деятельности является таким образом контроль успеваемости...
47387. Разработка миссии и целей компании «Ultra» 254.18 KB
  В первую очередь целевое начало в деятельности организации возникает потому что организация это объединение людей преследующих определенные цели. так же как и те кто являются хозяевами организации или работают в организации преследуя свои собственные цели при взаимодействии с организацией придают ее существованию определенную направленность и тем самым развивают целевое начало в деятельности организации. Цели и задачи исследования. Первая глава посвящена теоретическому осмыслению понятий миссия цели система целей и др.
47388. Технологічний процес визначення оптимальних змішаних стратегій автотранспортного підприємства 412 KB
  Особлива увага приділяється автомобільному транспорту бо саме він є самим мобільним і швидко реагує на зміни ринкового середовища тому саме цьому виду транспорту надають перевагу наші підприємці при здійсненні внутрішніх перевезень і перевезень в країни ближнього зарубіжжя. Україна росташована в центрі Європи на перетині важливих торгівельних шляхів і тому особливу увагу слід приділяти розвитку транспорту щоб не лишень забезпечувати власні потреби але й виводити цю галузь господарства на міжнародний рівень. Застарілі методи...
47389. Отграничение вандализма от смежных составов преступления 101.77 KB
  В соответствии с ч.1 статьи 214 Уголовного Кодекса Российской Федерации:- вандализм, то есть осквернение зданий или иных сооружений, порча имущества на общественном транспорте или в иных общественных местах,- (наказывается штрафом в размере до 40 тысяч рублей или в размере заработной платы или иного дохода осужденного за период до 3 месяцев, либо обязательными работами на срок от 120 до 180 часов, либо исправительными работами на срок от 6 месяцев до 1 года, либо арестом на срок до 3 месяцев).
47390. Строительство в г. Абакан, расчет и архитектурные особенности 2.07 MB
  Недостатком является стесненность площадки что не позволяет оптимально разместить на ней механизмы и материалы необходимые для проведения работ. Варианты фундаментов: ленточный работающий как балка на упругом основании; столбчатый под колонны. Данный дипломный проект был разработан при помощи ЭВМ. Методы проверки качества маркировка и транспортирование пиломатериалов должно производится по ГОСТ 656463 укладка и хранение по ГОСТ 3808 поверхностная антисептическая обработка по ГОСТ 1095064.
47391. Специфика патриотического воспитания дошкольников с отклонениями в эмоционально-личностном развитии и поведении 99.95 KB
  Они делают акцент на приобщение детей к культурному наследию народа. Куликова предлагают одним из решений проблемы воспитания патриотизма детейдошкольников познание ими РодиныРоссии. разработать комплекс занятий для детей с отклонениями направленных на патриотическое воспитание. Уровень патриотического воспитания детей дошкольного возраста с отклонениями в развитии и поведении станет выше если в процессе работы будут использованы игровые словесные наглядные экскурсионные методы и формы функционирования воспитательной системы...