36061

Нахождение начального решения для транспортной задачи

Доклад

Информатика, кибернетика и программирование

Для решения транспортной задачи разработано несколько методов каждый из которых отличается от другого методом заполнения матрицы перевозок. Метод минимального элемента Алгоритм метода минимального элемента состоит в следующем. Метод Фогеля Метод состоит в следующем. В выбранной строке или столбце как и в методе минимального элемента заполняется клетка с наименьшим значением тарифа.

Русский

2013-09-20

30.5 KB

5 чел.

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

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

Существуют два типа транспортной задачи: открытая и закрытая. Транспортная задача называется открытой если сумма запасов товара на складах отличается от суммы потребностей товаров у магазинов. Транспортная задача называется закрытой , если сумма запасов товара на складах равняется сумме потребностей магазинов. Решение существует только для закрытой транспортной задачи, поэтому если транспортная задача открытая , то ее надо привести к закрытому типу. Для этого в случае , если запас товара на складах превышает потребность магазинов, то вводят фиктивного потребителя, который выбирает весь избыток товара. В случае же, если существует дефицит товара, т.е. потребность магазинов больше, чем запас товаров на складах, то вводят фиктивного поставщика, с фиктивным запасом товара на складе. В обоих случаях в матрице тарифов перевозок C данному складу или магазину проставляется нулевая цена перевозки.

Метод минимального элемента

Алгоритм метода минимального элемента состоит в следующем. Просматривается вся матрица тарифов перевозок, и из нее выбирается позиция с наименьшим значением тарифа C, затем просматриваются значения наличия запасов на складе A и потребности потребителя B, затем в данную клетку записывается величина D=MIN(A,B). Из запасов соответствующего склада и потребностей магазина вычитается величина D . Если запас товара на складе исчерпан, то эта строка исключается из дальнейшего рассмотрения.

Если потребность магазина в товаре удовлетворена полностью, то этот столбец исключается из дальнейшего рассмотрения. Может быть случай , когда одновременно исключаются и строка и столбец, этот случай называется вырожденным. В дальнейшем весь процесс повторяется до тех пор , пока не будет исчерпан весь запас товаров на складах и не будет удовлетворена потребность всех магазинов. По полученной матрице перевозок вычисляется целевая функция задачи Z.

Метод Фогеля

Метод состоит в следующем. Просматриваются все строки и столбцы матрицы тарифов, вычисляется разность между двумя наименьшими элементами в строке или в столбце. Затем из всех этих разностей выбирается строка или столбец с максимальной разность. В выбранной строке или столбце , как и в методе минимального элемента, заполняется клетка с наименьшим значением тарифа. Затем обнулявшаяся строка или столбец исключаются из рассмотрения и весь процесс повторяется до полного исчерпания запаса товаров на складах. По полученной матрице перевозок вычисляется целевая функция Z.

Метод двойного предпочтения

В начальной своей стадии этот метод похож на метод минимального элемента , но для столбцов. Просматривается первый столбец матрицы тарифов, в нем находится наименьший элемент. Затем проверяется , минимален ли этот элемент в своей строке. Если элемент минимален в своей строке, то по методу  минимального элемента в эту клетку заносится значение D=MIN(A,B), соответствующие запас и потребность уменьшаются на эту величину. Обнулившаяся строка или столбец исключаются из рассмотрения и процесс повторяется, начиная с первого неисключенного столбца. Если найденный минимальный элемент не минимален в своей строке, то происходит переход к следующему столбцу и так до тех пор, пока не будет найден такой элемент. По полученной матрице перевозок вычисляется целевая функция Z. Этот метод требует интенсивных операции обмена с памятью , поэтому более громоздок посравнению с остальными и требует больших вычислительных ресурсов. Как и любая задача линейного программирования, необходимо построить первоначальный опорный план для решения задачи. Одним из методов построения исходного опорного плана является так называемый метод «северо-западного» угла.

Метод северо-западного угла

Метод состоит в следующем. Просматривается матрица тарифов перевозок C, начиная с левого верхнего угла (клетки). В эту клетку записывается величина D=MIN(A,B). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс опять повторяется для левой верхней клеткиоставшейся матрицы и так до тех пор пока весь запас товаров не будет

исчерпан. Полученный опорный план не оптимален, поэтому его дальнейшее решение продолжают одним из вышерассмотренных методов. Определение начального допустимого решения


 

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

35535. Интеллектуальные информационные системы (ИИС) 2.29 MB
  Автоматизация процесса информационного поиска основывается на формализации представления смыслового содержания информационного запроса и документов в виде соответственно поискового предписания ПП и поисковых образов документов ПОД. В процессе проведения информационного поиска в ДИПС определяется степень соответствия содержания документов и запроса пользователя путем сопоставления ПОД и ПП. Поэтому подсистема ввода и регистрации документов решает следующие основные задачи: создание электронных копий бумажных документов; подключение...
35536. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ УСТРОЙСТВ ЗАЩИТЫ ОТ ОШИБОК В ДИСКРЕТНОМ КАНАЛЕ ПЕРЕДАЧИ ИНФОРМАЦИИ 953 KB
  1 Исследовать распределение кратностей ошибок на длине кодового слова n для различных видов дискретной модуляции АМ ЧМ ФМ при когерентном приеме в канале связи с постоянными параметрами для следующих условий: символы 1 и 0 передаются с равной вероятностью блок Сигнал; регулярная составляющая отношения сигнал помеха равна 3 блок Непрерывный канал; решение принимается по правилу МП блок Решающее устройство; длина кодового слова 23 символа количество слов 10000 блок Стат 1. 2 Исследовать влияние правила решения для...
35537. Биоэтика в России: ценности и законы 963 KB
  Новые возможности медицины связанные не столько с лечением сколько с управлением человеческой жизнью например генетическая коррекция особенностей человека допущение донорства без согласия уничтожение жизни на эмбриональных стадиях отказ и прекращение медицинской помощи безнадежному больному вступают в противоречие с установившимися моральными ценностями и принципами. В силу этого противоречия и формируется биоэтика как система знания о границах допустимого манипулирования жизнью и смертью человека. В 1993 году в Общеправовой...
35538. Світове господарство: сутність та структура 479 KB
  Метою моєї курсової роботи було прослідкувати темпи розвитку світового господарства, міжнародної торгівлі, зробити аналіз географії світового експорту, показати співвідношення товарів та послуг у світовому товарообміні, також – вказати головну проблему, що зачіпає економіку кожної країни та світову економіку в цілому – проблему безпеки світової економіки.
35539. Разработка моделей детали типа «вал» в инструментальных средах КОМПАС 8.0 и Unigraphics 1.45 MB
  Unigraphics - это интерактивная система автоматизации проектирования и изготовления. Для обозначения систем этого класса используется аббревиатура CAD/CAM (Computer-Aided Design и Computer-Aided Manufacturing), что дословно переводится как Проектирование с Помощью Компьютера и Изготовление с Помощью Компьютера.
35540. ВЗАИМОЗАМЕНЯЕМОСТЬ, МЕТРОЛОГИЯ И СТАНДАРТИЗАЦИЯ 776 KB
  С учетом служебного назначения составлены и обоснованы технические требования предъявляемые к точности изготовления основных деталей и соединений цилиндрического редуктора. Принята система отверстия назначения посадок расчетным методом выбрана посадка с натягом соединения зубчатого колеса с валом с учетом класса точности выбраны посадки подшипников качения шпоночных шлицевых и резьбовых соединений. Обоснована методика достижения точности сборки узла. ДОПУСК ПОСАДКА ПРЕДЕЛЬНЫЕ КАЛИБРЫ ПОДШИПНИК РАЗМЕРНЫЕ ЦЕПИ МЕТОД ДОСТИЖЕНИЯ...
35541. Проектирование привода главного движения металлорежущего станка 1.82 MB
  Данные заносится в таблицу 1 которая представлена после расчетов режимов резания. Параметры фрезы: D=100 мм; B=16 мм; z=20 Глубина фрезерования: Подача: табл.283 [1] Принимаем: Стойкость фрезы: табл.5 постоянная зависящая от обрабатываемого материала табл.
35542. Двухбалочный мостовой кран Q=10 т 1.74 MB
  19 Разработка технологического процесса изготовления элементов балки20 Выбор метода и режима сварки. Для двухбалочного мостового крана принимаем: Высоту главной балки H=900мм Высоту опорного сечения балки hоп=600 мм Длину скоса d=4000 мм Высоту ограждения площадок обслуживания hо2=1200мм Ширину площадок обслуживания Базу крана Бкр=4400 Выбор геометрических параметров узлов конструкции Рис. Сечение главной балки. Сечение концевой балки.
35543. Привод ленточного транспортера с асинхронным двигателем трехфазного тока 1.55 MB
  Частота вращения тихоходного вала: где скорость движения ленты . Определение вращающих моментов на валах привода.4 Частота вращения тихоходного вала об мин 30.0 Частота вращения Быстроходного вала об мин.