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


 

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

22526. Основы вибропрочности конструкций 155.5 KB
  Если период вынужденных колебаний совпадет с периодом свободных колебаний стержня то мы получим явление резонанса при котором амплитуда размах колебаний будет резко расти с течением времени. Так как период раскачивающих возмущающих сил обычно является заданным то в распоряжении проектировщика остается лишь период собственных свободных колебаний конструкции который надо подобрать так чтобы он в должной мере отличался от периода изменений возмущающей силы. Вопросы связанные с определением периода частоты и амплитуды свободных и...
22527. Расчет динамического коэффициента при ударной нагрузке 140.5 KB
  Скорость ударяющего тела за очень короткий промежуток времени изменяется и в частном случае падает до нуля; тело останавливается. передается реакция равная произведению массы ударяющего тела на это ускорение. Обозначая это ускорение через а можно написать что реакция где Q вес ударяющего тела. Эти силы и вызывают напряжения в обоих телах.
22528. Сопротивление материалов. Введение и основные понятия 40.5 KB
  Прочность это способность конструкции выдерживать заданную нагрузку не разрушаясь. Жесткость способность конструкции к деформированию в соответствие с заданным нормативным регламентом. Деформирование свойство конструкции изменять свои геометрические размеры и форму под действием внешних сил Устойчивость свойство конструкции сохранять при действии внешних сил заданную форму равновесия. Надежность свойство конструкции выполнять заданные функции сохраняя свои эксплуатационные показатели в определенных нормативных пределах в течение...
22529. Метод сечений для определения внутренних усилий 92.5 KB
  Метод сечений для определения внутренних усилий Деформации рассматриваемого тела элементов конструкции возникают от приложения внешней силы. Внутренние усилия это количественная мера взаимодействия двух частей одного тела расположенных по разные стороны сечения и вызванные действием внешних усилий. Здесь {S} и {S } внутренние усилия возникающих соответственно в левой и правой отсеченных частях вследствие действия внешних усилий. Используя общую методологию теоремы Пуансо о приведении произвольной системы сил к заданному центру и...
22530. Эпюры внутренних усилий при растяжении-сжатии и кручении 48.5 KB
  Рассмотрим расчетную схему бруса постоянного поперечного сечения с заданной внешней сосредоточенной нагрузкой Р и распределенной q рис. а расчетная схема б первый участок левая отсеченная часть в второй участок левая отсеченная часть г второй участок правая отсеченная часть д эпюра нормальных сил Рис. В пределах первого участка мысленно рассечем брус на 2 части нормальным сечением и рассмотрим равновесие допустим левой части введя следующую координату х1 рис. Мысленно рассечем его сечением 2 2 и рассмотрим равновесие левой...
22531. Эпюры внутренних усилий при прямом изгибе 87.5 KB
  Рассмотрим пример расчетной схемы консольной балки с сосредоточенной силой Р рис. а расчетная схема б левая часть в правая часть г эпюра поперечных сил д эпюра изгибающих моментов Рис. Построение эпюр поперечных сил и внутренних изгибающих моментов при прямом изгибе: Прежде всего вычислим реакции в связи на базе уравнений равновесия: После мысленного рассечения балки нормальным сечением 1 1 рассмотрим равновесие левой отсеченной части рис. Для правой отсеченной части при рассмотрении ее равновесия результат аналогичен рис.
22532. Понятие о напряжениях и деформациях 80.5 KB
  а вектор полного напряжения б вектор нормального и касательного напряжений уменьшаются главный вектор и главный момент внутренних сил причем главный момент уменьшается в большей степени. Введенный таким образом вектор рn называется вектором напряжений в точке. Совокупность всех векторов напряжений в точке М для всевозможных направлений вектора п определяет напряженное состояние в этой точке. В общем случае направление вектора напряжений рn не совпадает с направлением вектора нормали п.
22533. Свойства тензора напряжений. Главные напряжения 95 KB
  Свойства тензора напряжений. Главные напряжения Тензор напряжений обладает свойством симметрии. Для доказательства этого свойства рассмотрим приведенный в лекции 5 элементарный параллелепипед с действующими на его площадках компонентами тензора напряжений. Отличные от нуля моменты создают компоненты верхняя грань и права грань: После сокращения на элемент объема dV=dxdydz получим Аналогично приравнивая нулю сумму моментов всех сил относительно осей Оу и Ог получим еще два соотношения Эти условия симметрии и тензора напряжений...
22534. Плоское напряженное состояние 98.5 KB
  Тензор напряжений в этом случае имеет вид Геометрическая иллюстрация представлена на рис. Инварианты тензора напряжений равны а характеристическое уравнение принимает вид Корни этого уравнения равны 1 Нумерация корней произведена для случая Рис. Позиция главных напряжений Произвольная площадка характеризуется углом на рис. Если продифференцировать соотношение 2 по и приравнять производную нулю то придем к уравнению 4 что доказывает экстремальность главных напряжений.