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). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс опять повторяется для левой верхней клеткиоставшейся матрицы и так до тех пор пока весь запас товаров не будет

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


 

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

31126. Типовое проектирование ИС 248.38 KB
  Рисунок 1 – Классификация методов типового проектирования ИС. Элементный метод типового проектирования. В качестве типового элемента системы используется ТПР по задаче или по отдельному виду обеспечения информационному техническому. Достоинства метода: Применение модульного подхода к проектированию и документированию ИС Недостаток метода: Большие затраты времени на сопряжение разнородных элементов вследствие информационной программной и технической несовместимости ТПР Плохая адаптивность элементов к особенностям объекта применения ИС...
31127. Организация процесса конструирования 54.29 KB
  Технология конструирования программного обеспечения ТКПО – система инженерных принципов для создания экономичного ПО которое надежно и эффективно работает в реальных компьютерах. Стратегии: Однократный проход или водопадная стратегия – это линейная последовательность этапов конструирования с определением всех требований вначале процесса. Быстрая разработка достигается за счет использования компонентноориентированного конструирования.
31128. Процесс руководства проектом и планирование проектных задач 17.3 KB
  Анализ риска. Исследование области неопределенности анализ ее влияние на проект. Первыми выполняемыми задачами являются системный анализ и анализ требований. Системный анализ проводится с целью: 1 выяснения потребностей заказчика; 2 оценки выполнимости системы; 3 выполнения экономического и технического анализа; 4 распределения функций по элементам компьютерной системы аппаратуре программам людям базам данных и т.
31129. Модели качества процесса конструирования. Архитектура программных систем 41.02 KB
  Архитектура программной системы ПС – это набор внутренних структур ПС которые видны с различных точек зрения и состоят из компонентов их связей и возможных взаимодействий между компонентами а также доступных извне свойств этих компонентов. Вид с точки зрения прецедентов Use cse view охватывает прецеденты которые описывают поведение системы наблюдаемое конечными пользователями аналитиками и тестировщиками. Вид с точки зрения проектирования Design view охватывает классы интерфейсы и кооперации формирующие словарь задачи и ее...
31130. Базис языка UML 249.01 KB
  Словарь UML образуют 3 разновидности строительных блоков это предметы отношения и диаграммы. Предметы – это абстракции основные элементы в модели отношения связывают предметы а диаграммы группируют коллекции предметов. Структурные предметы это существительные в UML моделях статические части. Предметы поведения Предметы поведения – это динамические части глаголы модели поведение объектов во времени.
31131. Унифицированный процесс разработки программных систем 45.19 KB
  Прецеденты должны быть основным артефактом на основании которого устанавливается желаемое поведение системы проверяется и подтверждается правильность выбранной системной архитектуры производится тестирование. Системная архитектура является решающим фактором при разработке концепций конструировании управлении и развитии создаваемой системы. Итеративным называется процесс который предполагает управление потоком исполняемых версий системы. Разработка стабильной базовой архитектуры продукта которая позволяет решать поставленные перед...
31132. Основы объектно-ориентированного представления программных систем 169.01 KB
  Сцепление модулей. Сцепление – это мера взаимозависимости модулей по данным внешняя характеристика модуля которую желательно уменьшить. Измеряется сцепление степенью сцепления. Выделяют 6 видов степени сцепления: Сцепление по данным; Сцепление по образцу; Сцепление по управлению; Сцепление по внешним ссылкам; Сцепление по общей области; Сцепление по содержанию.
31133. Статические модели объектно-ориентированного представления программных систем 142.29 KB
  Диаграмма классов это набор классов и связей между ними. Диаграммы классов используются: в ходе анализа – для указания ролей и обязанностей сущностей которые обеспечивают поведение системы; в ходе проектирования – для фиксации структуры классов которые формируют системную архитектуру. Отношения в диаграммах класса. Ассоциации отображают структурные отношения между экземплярами классов.
31134. Динамические модели объектно-ориентированного представления программных систем: автоматы 336.98 KB
  Динамические модели обеспечивают представление поведения системы путем отображения изменения состояний в процессе работы системы в зависимости от времени. Автомат – описывает поведение в терминах последовательности состояний через которые проходит объект в течение своей жизни. Диаграмма схем состояний – отображает конечный автомат выделяя поток управления от состояния к состоянию. Конечный автомат – поведение определяющее последовательность состояний в ходе существования объекта.