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


 

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

26551. ВСЭ И САНИТАРНАЯ ОЦЕНКА МЯСА ВЫНУЖДЕННО УБИТЫХ ЖИВОТНЫХ ПРИ НЕЗАРАЗНЫХ БОЛЕЗНЯХ (ТИМПАНИЯ, ОЖОГИ, АСФИКСИЯ, ТРАВМЫ) 15.16 KB
  ВСЭ И САНИТАРНАЯ ОЦЕНКА МЯСА ВЫНУЖДЕННО УБИТЫХ ЖИВОТНЫХ ПРИ НЕЗАРАЗНЫХ БОЛЕЗНЯХ ТИМПАНИЯ ОЖОГИ АСФИКСИЯ ТРАВМЫ. ВСЭ и санитарная оценка мяса вынужденно убитых животных при незаразных болезней. ВОСПАЛЕНИЯ ВЕРХНИХ ДЫХАТЕЛЬНЫХ ПУТЕЙ а также бронхиты пневмонии плевриты бронхопневмонии и плевропневмонии незаразной этиологии регистрируют чаще у молодняка и реже у взрослых убойных животных. Наиболее частые причины болезней содержание животных в сырых холодных помещениях на сквозняках цементном полу; скармливание заплесневелых кормов...
26552. ВСЭ И САНИТАРНАЯ ОЦЕНКА МЯСА ПРИ АКТИНОМИКОЗЕ И НЕКРОБАКТЕРИОЗЕ. НЕКРОБАКТЕРИО3 11.61 KB
  Больные овцы хромают; при поражении обеих передних ног они ползают на путовых или карпальных суставах при поражении задних конечностей овцы подставляют их далеко под живот; при глубоком поражении тканей нередко спадает роговой башмак. При поражении нескольких органов удовлетворительной упитанности туши решение о возможности использования мяса и внутренних органов принимают после проведения бактериологического исследования на наличие патогенной кокковой микрофлоры и сальмонелл. При поражении костей на месте губчатого костного вещества...
26553. ВСЭ И САНИТАРНАЯ ОЦЕНКА МЯСА ПРИ БРУЦЕЛЛЕЗЕ 5.19 KB
  При ветеринарносанитарной оценке мяса от бруцеллезных животных учитывают клинические признаки заболевания патологоанатомические изменения и данные серологических исследований. Мясо полученное от убоя животных всех видов которые имели клинические или патологоанатомические признаки бруцеллеза выпускают после проварки. Голова печень сердце легкие почки желудки и другие внутренние органы полученные от убоя животных всех видов реагирующих на бруцеллез или имеющие клинические признаки бруцеллеза выпускать в сыром виде запрещается; их...
26554. ВСЭ ПРОДУКТОВ УБОЯ ДИКИХ ПРОМЫСЛОВЫХ ЖИВОТНЫХ 8.84 KB
  ВСЭ ПРОДУКТОВ УБОЯ ДИКИХ ПРОМЫСЛОВЫХ ЖИВОТНЫХ В зависимости от вида диких животных их мясо отличается по органолептическим признакам морфологическому и химическому составу вкусовым и кулинарным качествам. У одних животных его мало лось заяц и такое мясо относится к тощему у других бывают значительные отложения медведь северный олень кабан. У большинства диких животных сразу после снятия шкуры мясо красного цвета. МЯСО ЛОСЯ темнокрасного цвета мышцы на разрезе грубоволокнистые однородного цвета покрыты плотными хорошо...
26555. ВСЭ ПРОДУКТОВ УБОЯ ЖИВОТНЫХ ПРИ ЛУЧЕВОЙ БОЛЕЗНИ,ВЫЗВАННОЙ ВНЕШНИМ ГАММА-ОБЛУЧЕНИЕМ 3.55 KB
  ВСЭ ПРОДУКТОВ УБОЯ ЖИВОТНЫХ ПРИ ЛУЧЕВОЙ БОЛЕЗНИВЫЗВАННОЙ ВНЕШНИМ ГАММАОБЛУЧЕНИЕМ. При внешнем облучении и первом начальном периоде болезни возбуждение сменяется угнетением и общей слабостью снижается атшетит 'появляется тахикардия гиперемия слизистых оболочек одышка 'повышение температуры на 03 05 С усиливается перистальтика возможны рвота и . Третий период разгар болезни характеризуется лихорадкой снижением аппетита общим угнетением поносом с кровью j нарушениями в органах кроветворения и сердечнососудистой...
26556. ВСЭ ПРОДУКТОВ УБОЯ ПРИ ВНУТРЕННЕМ ПОРАЖЕНИИ РВ 2.97 KB
  Выздоровление длится более 3 мес а при крайне тяжелой степени наступает смертельный исход.При хроническом течении различают три степени болезни: легкую среднюю и тяжелую. При легкой степени наблюдаются функциональные изменения в сердечнососудистой системе и органах пищеварения дистоння. При средней степени снижается количество лимфоцитов и нейтрофилов с общей лейкопенией проявляется тромбоцитопения и умеренная эритропения.
26557. ВСЭ ПРОДУКТОВ УБОЯ ПРИ ЛЕПТОСПИРОЗЕ И ЛИСТЕРИОЗЕ 8.32 KB
  Если имеются дегенеративные изменения мускулатуры или желтушное окрашивание не исчезающее в течение двух суток тушу и все внутренние органы направляют на техническую утилизацию. При отсутствии дегенеративных изменений в мускулатуре но при наличии в ней желтушного окрашивания исчезающего в течение двух суток тушу а также внутренние органы не имеющие патологических изменений выпускают после проварки. Кишечник и патологически измененные органы направляют на техническую утилизацию. Патологически измененные органы кровь и головы от...
26558. ВСЭ ТУШ И ОРГАНОВ ВЫНУЖДЕННО УБИТЫХ ЖИВОТНЫХ ПРИ ОТРАВЛЕНИИ ОРГАНИЧЕСКИМИ И МИНЕРАЛЬНЫМИ ЯДАМИ. ПРИЧИНА ОТРАВЛЕНИЙ И ПИЩЕВАЯ НЕПОЛНОЦЕННОСТЬ МЯСА ОТРАВИВШИХСЯ ЖИВОТНЫХ ДЛЯ ЧЕЛОВЕКА 21.73 KB
  ВСЭ ТУШ И ОРГАНОВ ВЫНУЖДЕННО УБИТЫХ ЖИВОТНЫХ ПРИ ОТРАВЛЕНИИ ОРГАНИЧЕСКИМИ И МИНЕРАЛЬНЫМИ ЯДАМИ. ПРИЧИНА ОТРАВЛЕНИЙ И ПИЩЕВАЯ НЕПОЛНОЦЕННОСТЬ МЯСА ОТРАВИВШИХСЯ ЖИВОТНЫХ ДЛЯ ЧЕЛОВЕКА. В практике встречаются случаи отравлений сельскохозяйственных животных минеральными удобрениями ядовитыми растениями хлоридом натрия и другими солями минеральными ядами мышьяк медь и др. Особо опасны при отравлениях животных фосфорорганические хлорорганические карбаматные ртутьсодержащие и другие пестициды ядохимикаты} которые используют в борьбе с...
26559. ВСЭ И САНИТАРНАЯ ОЦЕНКА ТУШ И ОРГАНОВ ПРИ РОЖЕ СВЕНЕЙ 7.89 KB
  Мускулатура туши иногда гиперемирована и с кровоизлияниями. В случае обнаружения в мясе или внутренних органах этих бактерий туши обеззараживают проваркой а внутренние органы направляют на техническую утилизацию или уничтожают. Кроме того такие туши можно направлять на изготовление вареноконченых грудинок и кореек. В случаях убоя животных туши со всеми внутренними органами и шкурой уничтожают.