bannerka.ua

Транспортная задача

Транспортная задача. Нахождения начального Базисного распределения поставок

1. Общая постановка транспортной задачи

2. Нахождение опорного плана транспортной задачи.

1. Пусть с некоторых M пунктов отправления (поставщиков) A1, A2, …, Am нужно перевезти груз в N пунктов назначения (потребителей) B1, B2, …, Bn. Известно, сколько груза должны в каждом пункте отправления и сколько требуется его в каждом пункте назначения. Известны также расходы доставки единицы груза от поставщика к потребителю или расстояние между пунктами перевозок. Необходимо определить, какое количество груза должен направить поставщик той или иной потребителю, чтобы общие затраты на его транспортировку (общее количество тонно-километров) или время его доставки были минимальными.

Для записи модели транспортной задачи введем следующие обозначения:

Аи — Запасы груза I-м пункте отправления (I = 1,2,3, …, m);

Bj— Потребность в грузе в J — М пункте назначения (J = 1,2,3, …, n);

Хij — Количество единиц груза, перевозимого от И-Го пункта отправления до J-Го пункта;

Сij — Тарифы перевозки единицы груза от И-Го пункта отправления до J-Го пункта.

Тогда математическая постановка задачи сводится к нахождению минимального значения функции

Транспортная задача (1)

При условиях

Транспортная задача (2)

Транспортная задача (3)

Транспортная задача (4)

Поскольку переменные Транспортная задача удовлетворяют системам линейных уравнений (2) и (3) и условиям неотрицательности (4), то обеспечивается доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также не допускаются обратные перевозки.

Определения. Любой — который неотъемлемый решение системы линейных уравнений (2) и (3), что определяется матрицей Транспортная задача называется планом транспортной задачи.

Определения. План Транспортная задача, при котором функция (1) принимает своего минимального значения называется оптимальным планом транспортной задачи.

Входные данные ТС записывают в виде таблицы 1.

Таблица 1.

Пункты отправления

Пункты назначения

Запасы

B1

B2

B3

BN

А1

С11

Х11

С12

Х12

С13

Х13

С1N

Х1N

A1

А2

С21

Х21

С22

Х22

С23

Х23

С2N

Х2N

A2

А3

С31

Х31

С32

Х32

С33

Х33

С3N

Х3N

A3

Аm

Сm1

Хm1

Сm2

Хm2

Сm3

Хm3

СMn

ХmN

Am

Потребности

B1

B2

B3

Bn

Очевидно, общие запасы груза у поставщиков равны Транспортная задача, а общая потребность в грузе в пунктах назначения равна Транспортная задача.

Если общая потребность в грузе в пунктах назначения равна общим запасы груза в пунктах отправления, т. е.

Транспортная задачаТранспортная задача (5)

То модель такой транспортной задачи называется Закрытой. Если заданное условие не выполняется, то модель транспортной задачи называется Открытой.

Теорема. Для розришимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления составили потребностям в грузе в пунктах назначения, т. е. чтобы выполнялось равенство (5).

В случае, если запасы превышают потребности, т. е. Транспортная задачаТранспортная задача, вводится фиктивный (N+1)-Й пункт назначения с потребностью Транспортная задачаТранспортная задача и соответствующие тарифы считаются равными нулю: СIn+1= 0 ( ). Полученная задача является транспортной задачей для которой выполняется равенство (5).

Аналогично при Транспортная задачаТранспортная задача вводится фиктивный (M+1)-Й пункт отправления с запасом груза Транспортная задачаТранспортная задача и тарифы считаются равными нулю: СM+1J= 0 ( ).

2. Нахождение опорного плана транспортной задачи.

Как и при решении задач ЛП симплексным методом, определение оптимального плана ТС начинается с нахождения которого — нибудь ее опорного плана. Для его построения используются следующие методы:

1. северо — западного угла;

2. минимальной стоимости;

3. двойного преимущества.

Суть этих методов заключается в том, что опорный план находят последовательно по N+M-1 Шагов, на каждом из которых в таблице условия задачи заполняют одну ячейку, которую называют Занятой. Заполнение одной из ячеек обеспечивает полностью или удовлетворения потребностей в грузе одного из пунктов назначения или вывоза груза из одного из пунктов отправления. В первом случае временно исключается из рассмотрения столбик, содержащий заполненную на данном шаге ячейку, и рассматривают задачу, таблица условий которой содержит на один столбик меньше, чем было перед этим шагом, но то же количество строк и соответственно изменены запасы груза в одном из пунктов отправления. Во втором случае временно исключается из рассмотрения строка, содержащий заполненную ячейку, и считают, что таблица условий имеет одну строку меньше и соответствующих изменениях потребностей в грузе в пункте назначения, столбик которого содержит занятую ячейку.

После выполнения N+M-2 Шагов получают задачу с одним пунктом отправления и одним пунктом. При этом останется свободной только одна ячейка, а запасы пункта отправления будут равны потребностям пункта отправления оставшихся. Заполнив эту ячейку (N+M-1 —И шаг), получают искомый опорный план.

Метод северо-западного угла. При нахождении опорного плана транспортной задачи методом северо — западного угла на каждом шагу рассматривают первый пункт отправления и первый пункт назначения с оставшихся. Заполнение ячеек таблицы условий начинается с левой верхней ячейки для неизвестного Х11 (Северо — западный угол) и заканчивают для неизвестного ХMn.

2. Терминологический словарь

Любой — который неотъемлемый решение системы линейных уравнений (2) и (3), что определяется матрицей Транспортная задача называется Планом транспортной задачи.

План Транспортная задача, при котором функция (1) принимает своего минимального значения называется Оптимальным планом транспортной задачи

3. Рекомендуемая литература

1. Исследование операций в экономике: Учебн. пособие для вузов / Н. Ш. Кремер, Б. А. Путко, И. М. Тришин. М. Н. Фридман; Под ред. проф. Н. Ш. Кремера. — М.: Банки и биржи, ЮНИТИ, 1997.

2. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.

3. Бугир М. К. Математика для экономистов. Линейная алгебра, линейные модели: Учеб. пособие. — К.: ВЦ «Академия», 1998.

4. Гвоздинський А. М. Оптимизационные задачи в организационном управлении: Учеб. посиб.-Харьков: ХГТУРЭ, 1997.

Tagged with: , , ,
Posted in Математические модели в расчетах на эвм
Перечень предметов
  1. Бухучет в ресторанном хозяйстве
  2. Введение в специальность 4к.2с
  3. Высшая математика 3к.1с
  4. Делопроизводство
  5. Информационные технологии в области
  6. Информационные технологии в системах качества стандартизаціісертифікаціі
  7. История украинской культуры
  8. Математические модели в расчетах на эвм
  9. Методы контроля пищевых производств
  10. Микробиология молока и молочных продуктов 3к.1с
  11. Микропроцессорные системы управления технологическими процессами
  12. Научно-практические основы технологии молока и молочных продуктов
  13. Научно-практические основы технологии мяса и мясных продуктов
  14. Общая технология пищевых производств 4к.2с
  15. Общие технологии пищевых производств
  16. Организация обслуживания в предприятиях ресторанного хозяйства
  17. Основы научных исследований и техничнои творчества
  18. Основы охраны труда
  19. Основы пидприемницькои деятельности и агробизнеса
  20. Основы физиологии и гигиены питания 3к.1с
  21. Пищевые и диетические добавки
  22. Политология
  23. Получения доброкачественного молока 3к.1с
  24. Прикладная механика
  25. Прикладная механика 4к.2с
  26. Теоретические основы технологии пищевых производств
  27. Технологический семинар
  28. Технологическое оборудование для молочной промышленности
  29. Технологическое оборудование для мьяснои промышленности
  30. Технология продукции предприятий ресторанного хозяйства
  31. Технология хранения консервирования и переработки молока
  32. Технология хранения, консервирования и переработки мяса
  33. Технохимическому контроль
  34. Управление качеством продукции ресторанного хозяйства
  35. Физика
  36. Физическое воспитание 3к.1с
Возможно Вы искали: