Автор admin | Рубрика Современные оконные системы | Posted 21-07-2009
Tags: задачи, метод, система
Для решения транспортной задачи в матричной форме существуют различные методы (потенциалов, дифференциальных рент, разрешающих слагаемых).
Перечисленные методы, наиболее часто используемые для решения транспортных задач, основаны на принципах: 1) последовательного улучшения плана (потенциалов) 2) последовательного сокращения невязок, именуемых также методами условно-оптимальных планов (дифференциальных рент, разрешаемых слагаемых).
Трудоемкость решения транспортной задачи во многом определяется рациональностью построения начального (отправного, базисного) плана. От того, как построен начальный план, зависит количество шагов (итераций), необходимых для получения оптимального решения задачи.Диагональный метод, или метод северо-западного угла.
Этот метод описан в литературе одним из первых. Он дает возможность построить базисный план, отличающийся тем, что число корреспонденции (пунктов перевозок грузов) должно быть равно m + п — 1, гдеяг — число поставщиков, an — число потребителей.
Достоинством диагонального метода является его строгая формализации, но первоначальное распределение весьма далеко от оптимального, что увеличивает число итераций при решении задачи.
Рассмотрим построение плана этим методом на примере. Исходные данные систематизируем в табл. 47.
В клетках табл. 47 поставлена стоимость перевозок, принятая в качестве критерия оптимальности. Задача заключается в получении такого плана перевозок, при котором себестоимость перевозок будет минимальна.
Заполнение матрицы исходного плана начинаем с левого верхнего угла и постепенно по диагонали подходим к правому нижнему углу. Количество заполненных (загруженных) клеток, как указано выше, должно быть равно m + п — 1 = 7.
Начинаем заполнение с левой верхней клетки табл. 48, клетка 1. В левом верхнем углу каждой клетки проставлен ее номер, а в правом верхнем — стоимость перевозок.