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


 

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

27382. ЗУНы для вычисления в пределах 100 (сложение и вычитание) 22.28 KB
  Остальные случаи вычислений над числами большими 100 относятся к письменным вычислениям. Рассмотрим методические особенности формирования умений складывать и вычитать числа в пределах 100 которые нашли отражение в учебниках М1М и М2М Моро. Овладение вычислительными приемами предполагает усвоение: нумерации чисел в пределах 100 разрядного состава двузначного числа табличных случаев сложения вычитания и свойств сложения и вычитания; прибавления числа к сумме вычитания числа из суммы прибавления суммы к числу вычитания...
27383. Алгоритмы: 1. Письменного сложения и вычитания 2. Письменного умножения 3. Письменного деления 20.18 KB
  Письменного деления ЗУНы для сложения и вычитания: Нумерация многозначных чисел Разрядный состав многозначных чисел Десятичный состав числа Навык сложения и вычитания чисел в пределах 20 Знание переместительного и сочетательного закона сложения Как и другие алгоритмы письменного вычисления в и рассматриваются поэтапно: Актуализация ЗУН подготовка к изучению алгоритма подготовка и изучение алгоритма Введение самого алгоритма Усвоение алгоритма Продуктивное повторение новой темы включать новые знания в систему имеющихся Основная...
27384. Функции текстовых задач 17.29 KB
  Любое математическое задание можно рассматривать как задачу выделив в нем условие т. Функции текстовых задач. Ведущие методисты отмечают что решение текстовых задач в начальной школе преследует двойную цель: с одной стороны научить решать текстовые задачи различных видов с другой стороны сами текстовые задачи выступают как средство обучения воспитания и развития школьников.
27385. Математическое развитие младших школьников невозможно без приобщения их к геометрии 19.38 KB
  Эта особенность находит свое выражение и в начальных классах где формирование представлений о геометрических фигурах связано с изучением таких величин как длина и площадь. Основой формирования у детей представлений о геометрических фигурах является способность их к восприятию формы. В развитии представлений о геометрических фигурах учащиеся начальных классов проходят два этапа. Формируя у них целостное представление о геометрических фигурах следует идти от реальных предметов к их моделям геометрическим фигурам и наоборот: от...
27386. Различные подходы к построению урока математики 19.44 KB
  Основные этапы подготовки учителя к уроку математики: общий способ деятельности связанный с планированием урока можно представить в виде следующей последовательности вопросов. Какова функция учебных заданий данного урока обучающая развивающая контролирующая Какие знания умения навыки и приемы умственных действий формируются в процессе их выполнения 5. Какова дидактическая цель данного урока 6.
27387. Анализ и синтез 18.71 KB
  Способность к аналитикосинтетической деятельности находит свое выражение не только в умении выделять элементы того или иного объекта его различные признаки или соединять элементы в единое целое но и в умении включать их в новые связи увидеть их новые функции. Так как работу по формированию у детей логического приема сравнения лучше начать с первых уроков математики то в качестве объектов можно сначала использовать предметы или рисунки с изображением предметов хорошо им знакомых в которых они могут выделить те или иные признаки опираясь...
27388. Методика преподавания русского языка 36 KB
  Как и любая другая наука методика русского языка имеет свой предмет. Методика русского языка призвана изучить закономерности формирования умений и навыков в области языка усвоения систем научных понятий по грамматике и по другим разделам науки о языке. Методика русского языка изучает уровни знаний умений и навыков учащихся на разных ступенях обучения выясняет причины успехов или неудач в обучении исследует типичные ошибки речевые орфографические и пр.
27389. Место курса «Русский язык» в учебном плане 76 KB
  Это обусловлено тем что русский язык является государственным языком Российской Федерации родным языком русского народа средством межнационального общения. Осознание единства звукового состава слова и его значения. Установление числа и последовательности звуков в слове. Сопоставление слов различающихся одним или несколькими звуками.
27390. Коммуникативно-познавательная основа русского языка 80 KB
  Коммуникативный принцип предусматривает: осмысление и реализацию основной функции языка быть средством общения; развитие умения ориентироваться в ситуациях общения понимать цель и результат общения собеседников контролировать и корректировать свою речь в зависимости от ситуации общения; знакомство с различными системами общения устными и письменными речевыми и неречевыми; формирование представления о тексте как результате продукте речевой деятельности; развитие у учащихся желания потребности создавать собственные тексты...