Решение транспортной задачи с правильным балансом

В поставленной задаче обозначив через хij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю, сведём задачу в так называемую матрицу планирования, представленную в таблице 1.1

Таблица 1.1

Тогда математическая формулировка транспортной задачи сводится к минимизации линейной формы

(1.1)

при ограничениях:

ограничение по запасам:

(1.2)

ограничение по потребностям:

(1.3)

xij0 (1.4)

Различают задачи с закрытой моделью, когда ai=bj и открытой моделью, когда aibj, т.е. баланс между запасами и потребностями отсутствует.

Необходимым и достаточным условием разрешимости транспортной задачи является равенство суммарных запасов суммарным потребностям, т.е.

(1.5)

Если , то вводят фиктивный (n+1)-й пункт назначения с потребностью и полагают ci,n+1=0, .

Если , то вводят фиктивный (m+1)-й пункт отправления с запасами и принимают cm+1,j=0, .

Основные особенности транспортной задачи:

ограничения заданы в виде равенств;

каждая неизвестная входит лишь в 2 уравнения;

коэффициенты при неизвестных равны 1.

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

Решение транспортной задачи разбивается на 2 этапа:

Определение начального опорного плана.

Улучшение опорного плана.

Опорный план называется невырожденным, если содержит ровно (m+n-1) перевозку. Если перевозок меньше, чем m+n-1, то это вырожденный опорный план.

Для решения транспортной задачи используют различные методы, такие как: метод северо-западного угла, метод минимальной стоимости, метод Фогеля и метод потенциалов.

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

Был выбран метод потенциалов, т.к. этот метод производит улучшение опорного плана.

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

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

Алгоритм метода потенциалов.

Любым методом построить опорный план, убедиться, что он невырожденный.

Каждому поставщику Ai поставить в соответствие некоторый потенциал ui, а каждому потребителю Bj - потенциал pj.

Для каждой перевозки опорного плана составить сумму потенциалов, приравнять её к стоимости перевозки: ui+ pj=сij. Таким образом будет получена система (m+n-1) уравнений с (m+n) неизвестными. Такая система имеет бесконечное множество решений.

Выделить одно из возможных решений системы, присвоив любому из неизвестных произвольное значение. Из полученных значений потенциалов составить матрицу :

Вычислить max(- cij). Если max(- cij)=0, то вычисления прекращаются и последний план является оптимальным. В противном случае в ячейку, соответствующую максимальной разности, ввести перевозку Q>0. Чтобы не нарушился баланс перевозок, нужно отнять и прибавить Q в строках и столбцах так, чтобы по стокам и столбцам суммы Q были равны 0.

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

Убедиться, что опорный план невырожден (или привести его к невырожденному виду) и перейти к п.2.

По окончании расчётов проверить правильность размещения перевозок в соответствии с отграничениями по запасам и по потребностям, посчитать стоимость перевозки.

Пример решения транспортной задачи методом Фогеля представленный в таблице 1.2

транспортный задача еxcel delphi

Таблица 1.2

1.3 Обоснование выбора инструментальных средств

Для написания программы, позволяющей решить данную проблему, был выбран язык Delphi (а именно Borland Delphi 7.0). Причины такого выбора представлены ниже:

Delphi - один из самых распространенных языков программирования (наряду с несколькими другими) и является языком высокого уровня.

Delphi имеет очень мощную модель объектно-ориентированного программирования.

В высших учебных заведениях и колледжах очень популярен язык Delphi, так как он является модернизированным «потомком» языка Pascal, широко применяемого во многих школах и лицеях, в качестве обучающего языка программирования.

Создаваемые с его помощью программы могут работать не только под управлением Windows, а сама она относится к классу инструментальных средств ускоренной разработки программ.

Визуальное конструирование форм избавляет программиста от многих аспектов разработки интерфейса программы, так как Delphi автоматически готовит необходимые программные заготовки и соответствующий файл ресурсов. Программист использует специальное окно, которое называется окном формы, как прототип будущего окна программы и наполняет его компонентами, реализующими нужные интерфейсные свойства (разного рода списки, кнопки, полосы прокрутки и т.п.). После размещения на форме очередного компонента, Delphi автоматически вставляет в связанный с формой модуль ссылку на компонент, и корректирует специальный файл описания формы с расширением DFM, который после компиляции преобразуется в ресурсный файл Windows.

Использование компонентов не только во много раз сокращает сроки разработки программ, но и существенно снижает вероятность случайных ошибок, от которых, увы, не защищен ни один крупный программный проект. Однако в их применении есть оборотная сторона. Как правило, даже простые в функциональном отношении компоненты представляют лишь «вершину айсбергов» так как они создаются по объектно-ориентированной технологии и многие их функциональные черты наследуются от многочисленных родительских компонентов. В результате даже несложные программы, созданные в Delphi, редко имеют объем меньше сотен килобайт.

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

2. Проектная часть

ШАГ 1. Построение начального плана перевозок.

ШАГ 2. Проверка текущего плана на оптимальность.

Если план оптимален, то алгоритм завершен.

ШАГ 3. Улучшение плана перевозок. Переход к шагу 1.

Опишем алгоритм по шагам, иллюстрируя каждый шаг

ШАГ 1. Построение начального плана перевозок.

Построение начального решения (как и последующие расчеты) проводят в таблице, имеющей следующий вид:

Рис. 2.1

Клетка (i, j) таблицы соответствует коммуникации, связывающей i-го поставщика сj-м потребителем.

Построить начальный план перевозок означает - назначить объемы перевозок в клетки таблицы таким образом, чтобы:

а) число заполненных клеток было (m+n-1). (Тогда план перевозок будет отвечать базисному решению ЗЛП);

б) сумма перевозок в любой строке должна быть равна запасу соответствующего поставщика, а сумма перевозок в каждом столбце равна потребности потребителя. (Условие выполнения ограничений ТЗ). Существует несколько способов нахождения начального решения, которые отличаются только выбором клетки, в которую назначается очередная перевозка. Так, в способе северо-западного угла (СЗУ) для очередного назначения перевозки выбирается левая верхняя клетка таблицы (при этом никак не учитываются цены перевозок). Наоборот, в способе минимальной стоимости (МС) для заполнения выбирается клетка текущей таблицы с минимальной ценой перевозки, что в большинстве случаев (но не всегда) приводит к более дешевому (а значит и более близкому к оптимальному) начальному плану перевозок.

Мы будем пользоваться способом минимальной стоимости (МС).

Изложим теперь алгоритм нахождения начального решения.

ШАГ 1. Определенным способом выбираем клетку в текущей таблице. Пусть она имеет индексы (i, j) (i -номер поставщика, j - номер потребителя).

ШАГ 2. В качестве перевозок в эту клетку назначаем наименьшую из ai и потребности bj.

xij = min{ ai, bj }

ШАГ З. Уменьшим запас ai и потребность bj на величину перевозки xij, т.е.

ai = ai - xij,

bj =bj -xij

ШАГ 4. При исчерпании запаса (ai = 0) запрещаем к перевозке оставшиеся свободные клетки i-ой строки, а при исчерпании потребности

(bj =0) запрещаем такие же клетки вj-ом столбце.

В случае одновременного исчерпания запасов потребностей (ai =bj = 0) запрещаем перевозки или в строке (тогда считаем, что у потребителя осталась потребность в количестве равном нулю, которую необходимо удовлетворить), или в столбце (в этом случае считаем, что у поставщика остается запас равный нулю, который необходимо вывезти). Это делается для того, чтобы при одновременном запрещении перевозок в строке и столбце количество заполненных клеток таблицы не стало меньшим, чем m+n-1.

Получим новую текущую таблицу, в которую не входят заполненные и запрещенные клетки. Если таблица не пуста, переходим к шагу 1. (При исчерпании таблицы - конец).

Способ минимальной стоимости.

Рис. 2.2

1. Клетки с минимальной ценой (3,1), (3,2) и (3,3). Выбираем, например, (3,2). (Далее все шаги, как в предыдущем способе).

2. x32 = min{50,60} = 50

3. a '3 =50-50=0, b '2 = 100-50=50

4. Запрещаем строку 3.

Рис. 2.3

Клетка с min ценой ~ (2,3)

x23 = min{70,80} = 70

a2=70-70=0, b'3 = 80-70=10

Запрещаем строку 2.

Клетка с min ценой ~ (1,1)

x 11=min{120,60} = 60

a 1' =120-60 = 60, b1' = 0

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

Рис. 2.4

1. Выбираем клетку (1,2)

2. x 12 =min{110,100} = 100

3. a 1 =110-100 = 10, b'1 = 0

4. Текущая таблица содержит одну клетку (1,3).

Рис. 2.5

1. Выбираем последнюю клетку(1,3)

2. x13=min{10,10} = 10

3. a1' = b3 = 0

4. Таблица исчерпана. Конец.

Переходим к описанию следующего шага метода потенциалов.

ШАГ 2. Проверка текущего плана на оптимальность.

Признаком того, что текущий план перевозок является оптимальным, служит условие

(1)ui +vj -cij ?0

которое выполняется для всех клеток таблицы. Неизвестные здесь величины ui и vj (называемые потенциалами) определяются из условий

(2)ui + vj = cij

Условие (1) означает невозможность появления "спекулятивной" цены. Само же название "потенциалы" заимствовано из физического закона о том, что работа по перемещению заряда в электростатическом поле равна разности потенциалов в данных точках поля (У нас: "...цена перевозки единицы продукции по коммуникации равна разности цен в конце и в начале пути")

Так как заполненных клеток в таблице (m+n-1) штук, а неизвестных и (m+n) штук, то для их определения имеется система из (m+n-1) уравнений относительно (m+n) неизвестных. Чтобы найти решение (хотя бы какое-нибудь) такой системы, достаточно положить одно из неизвестных (произвольное) равным некоторому произвольно выбранному числу. Тогда остальные определяются единственным образом. Можно решать эту систему непосредственно (продолжаем работать с нашим "старым" примером и найдем потенциалы для начального плана, построенного способом МС).

Заполненные клетки Уравнения

(1,1) u1 + v1 =5

(1,2) u1 + v2 =10

(1,3) u1 + v3 =12

(2,3) u2 +v3 =4

(3,2) u3 +v2 =0

Положим, например, неизвестное u 1 равным 0 (через него можно из первых трех уравнений найти v1, v2 и v3). Последовательно из них находим u 2, u 3.

Этот метод можно сформулировать в виде единого правила:

Неизвестный потенциал находится вычитанием известного из цены перевозки в заполненной клетке

Применим это правило для определения u и v в нашем примере и получим:

u1 =0, u2 =-8, u3 =-6

v1 =5, v2 =10, v3 =12

Переходим к проверке условий оптимальности (1). Достаточно проверять их для незаполненных клеток, так как для клеток заполненных эти условия выполняются как равенства. Для проверки берется незаполненная клетка, складываются соответствующие ей потенциалы (первый элемент строки и последний элемент столбца) и из них вычитается цена перевозки в данной клетке. Если полученное число отрицательное (или ноль), то оптимальность в данной клетке не нарушается (в случае выполнения условия (1) для всех незаполненных клеток, имеем оптимальный план перевозок). Если же в таблице встретилась хотя бы одна клетка, для которой это число положительно, тогда решение не является оптимальным и может быть улучшено.

Проверим на оптимальность имеющееся решение

(2,1) u2+v1-c21=-8+5-8=-11<0

(2,2) u 2 +v2 -c22=-8+10-6=-4<0

(3,1) u 3 +v1 -c31=-10+ 5-0=-5<0

(3,3) u 3 +v3 -c33=-10+12-0=2>0

Следовательно, условие оптимальности нарушено в клетке (3,3).

Имеющийся план перевозок можно улучшить.

Дадим описание заключительного шага алгоритма метода потенциалов.

ШАГ 3 Улучшение плана перевозок.

Улучшение плана происходит путем назначения перевозки и>0 в ту клетку (i, j) таблицы, в которой нарушилось условие оптимальности. Но назначение ненулевой перевозки нарушает условия баланса вывоза продукции от поставщика i (вывозит весь запас и еще плюси>0) и условия баланса привоза продукции к потребителю j (получает все что можно и еще плюс и > 0). Условия баланса восстанавливают путем уменьшения вывоза от i-поставщика к какому-то другому потребителю j (уменьшают на и перевозку в какой-то заполненной клетке (i, j) строки i). При этом нарушается баланс привоза продукции к потребителю j (получает на и меньше, чем ему требуется). Восстанавливают баланс в столбце j, тогда он нарушается в некоторой строке i и т.д. до тех пор, пока цикл перемещения перевозок не замкнется на клетке, в которой нарушалось условие оптимальности. Продемонстрируем эти рассуждения на нашем примере.

Рис. 2.6

1. Оптимальность нарушена в клетке (3,3). Назначим в нее перевозку и>0 (+и означает, увеличение на и).

2.Нарушается баланс вывоза от поставщика 3 (вывозит 50+ и, а это больше его запаса!). Уменьшаем на и перевозку в заполненной клетке строки 3 (вне заполненной уменьшать нельзя, так как это приведет к отрицательной перевозке).

Рассмотрим те клетки цикла в которых уменьшаем на и перевозку и берём минимум из вычитаемых, у нас это min {10- и,50- и}=10.

И данное число надо подставить в цикл

Транспортная задача по критерию времени

Иногда возникает ситуация, когда в условиях (ТЗ) необходимо минимизировать не стоимость перевозок, а время их выполнения (Срочные грузы, перевозки скоропортящихся продуктов, работа «скорой помощи» и т.д.)

Имеется m поставщиков однородного груза и n потребителей груза. Для каждой пары (,) известно время , за которое груз перевозится от к . Требуется составить такой план перевозок, при котором все запасы поставщиков будут вывезены, а все запросы потребителей будут полностью удовлетворенны и наибольшее время доставки всех грузов будет минимизирован.

Задача о назначениях (Венгерский метод)

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

В ячейку D15 - записал целевую функцию:

{=СУММ((B8:F8*B13:F13)+(B9:F9*B14:F14))}

В ячейки D17:H17 записал ограничения, задающие требование о точном выполнении заявки каждого магазина. Как обычно, я записал соответствующую формулу в первую из этих ячеек:

{=СУММ(B13:B14) - E5 }

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

Затем задал следующую группу ограничений. Эти ограничения отвечают тому естественному условию, что со склада нельзя увести больше продукции, чем там имеется. Формула, помещенная в ячейку D18, имеет вид:

{=C4 - СУММ(B13:F13)}

Эта формула скопирована уже по столбцу в ячейку D19. Подготовительный этап завершен - можно вызывать Решатель.

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

Рис. 2.7 - Окно Решателя при решении транспортной задачи

Прежде чем дать команду на решение задачи, я провел настройку параметров в окне Options. В частности я включил флажки, указывающие на линейность модели и положительность переменных. Кроме того, я увеличил точность решения целочисленной задачи, задав в окне Tolerance значение в 1% вместо 5%, принятых по умолчанию.

Рис. 2.8 - Настройка в окне параметров Решателя при решении транспортной задачи

Осталось щелкнуть кнопку "Solve" и получить оптимальный план перевозок. Вы можете проанализировать, насколько оптимальный план отличается от равномерного распределения, предложенного в качестве первоначального варианта, и как уменьшились транспортные расходы:

Рис. 2.9 - Решение транспортной задачи

Параметры, управляющие работой Решателя

Рассмотрим возможности управления работой Решателя, задаваемые в окне Параметры (Options):

Максимальное время (MaxTime) - ограничивает время, отведенное на процесс поиска решения. По умолчанию задано 100 секунд, что обычно достаточно для задач небольшой размерности, имеющих около 10 ограничений. Для задач большой размерности придется это значение увеличивать.

Предельное число итераций (Iterations) - еще один способ ограничения времени поиска путем задания максимального числа итераций. По умолчанию задано 100, но это число можно увеличивать до 32767. Чаще всего, если решение не получено за 100 итераций, надежд получить его при увеличении этого значения мало. Лучше попытаться изменить начальное приближение и запустить процесс поиска заново.

Относительная погрешность (Precision) - задает точность выполнения ограничений. Иногда проще изменить ограничение, отодвинув границу, чем пытаться выполнить ограничения с высокой точностью.

Сходимость (Convergence) - задается десятичной дробью, меньшей единицы, позволяя остановить процесс поиска при сходимости решения к неподвижной точке, когда относительные изменения в течение последних 5 итераций не превышают заданную дробь.

Линейная модель (Assume Linear Model) - этот флажок следует включать, когда целевая функция и ограничения - линейные функции. Эта дополнительная информация позволяет Решателю упростить процесс поиска решения.

Неотрицательные значения (Assume Non-Negative) - этим флажком можно задать ограничения на переменные, что позволит искать решения в положительной области значений, не задавая специальных ограничений на их нижнюю границу.

Показывать результаты итераций (Show Iteration Results) - флажок, позволяющий включить пошаговый процесс поиска, показывая на экране результаты каждой итерации. В сложных ситуациях, когда Решатель не находит решения автоматически, рекомендуется включать этот флажок, так как иногда можно найти точку, от которой процесс поиска уклонился в сторону.

Автоматическое масштабирование (Use Automating Scaling) - флажок автоматического изменения масштаба следует включать, когда масштаб значений входных переменных и целевой функции и ограничений отличается, возможно, на порядки. Например, переменные задаются в штуках, а целевая функция, задающая суммарную стоимость, измеряется в миллионах рублей.

Относительная погрешность (Tolerance) - задается в процентах. Указанное значение имеет смысл только для задач с целочисленными ограничениями. Решатель в таких задачах вначале находит оптимальное не целочисленное решение, а потом пытается найти ближайшую целочисленную точку, решение в которой отличалось бы от оптимального не более чем на указанное данным параметром количество процентов. Если такая точка найдена, Решатель сообщает об успехе. При большом допуске (по умолчанию 5%) может быть потеряно лучшее целочисленное решение, правда, отличающееся от найденного Решателем в пределах допуска. Для целочисленных задач допуск имеет смысл уменьшить, что я и сделал при решении транспортной задачи. Хочу еще раз обратить внимание на эту особенность решения задач целочисленного программирования. Если значение параметра Tolerance задать большим, то Решатель может остановиться раньше времени, не найдя лучшего целочисленного решения. Если же его взять малым, то наилучшее целочисленное решение будет отличаться от оптимального нецелочисленного решения на величину большую, чем ту, которая задается параметром Tolerance. В этом случае формально решение заканчивается неуспехом, поскольку найденное решение не удовлетворяет всем требованиям. Конечно, параметр Tolerance играет служебную роль, и "умный" Решатель, найдя наилучшее целочисленное решение, должен был бы уведомлять, что решение найдено, но ограничение по Tolerance не выполнено. Этого, однако, не происходит. Мы еще столкнемся с этой ситуацией при рассмотрении следующей задачи.

Сохранить модель (Save Model) - командная кнопка; позволяет открыть диалоговое окно, где можно указать имя сохраняемой модели. Имеет смысл использовать эту возможность, когда на рабочем листе несколько моделей, так как единственная модель запоминается автоматически.

Загрузить модель (Load Model) - позволяет загрузить одну из сохраненных моделей.

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

2.2 Решение транспортной задачи в Delphi