Математическая модель задачи

Лекция 8. Транспортная задача линейного программирования

План:

1. Математическая модель задачи

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

Математическая модель задачи

Пусть имеется поставщиков (или пунктов отправления), располагающих некоторым однородным продуктом в объемах по единиц, и получателей (или пунктов назначения) с объемами потребления по единиц. Задана матрица где – стоимость перевозки единицы продукции от i -го поставщика j -му потребителю. Возникает задача определения плана перевозок где – количество единиц продукции, поставляемой по коммуникации (i, j), которая бы минимизировала суммарную стоимость всех перевозок. Математическая модель задачи будет иметь вид:

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

Если то задача называется закрытой (сбалансированной), в противном случае – открытой.

Переход к закрытой форме задачи. В случае, если запасы поставщиков больше потребностей потребителей вводят (n + 1)-го фиктивного потребителя, запросы которого равны излишку запаса, т.е.

Тарифы считаются равными нулю. Получим расширенную закрытую задачу. Поставки в оптимальном плане расширенной задачи покажут остатки продукции на складах поставщиков.

Если потребности превышают запасы то вводят -го фиктивного поставщика. Его запасы считают равными недостающей продукции:

Тарифы равны некоторому большому положительному числу. В расширенной задаче получим баланс потребностей и запасов. Поставки в оптимальном плане расширенной задачи покажут объемы недостачи продукции.

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

· коэффициенты при равны единице;

· каждая переменная встречается дважды;

· в случае баланса всегда имеется допустимое решение задачи;

· число переменных в транспортной задаче равно nm, а число уравнений в системе ограничений равно . Так как мы предполагаем, что транспортная задача является закрытой, то число линейно независимых уравнений равно . Следовательно, опорный план транспортной задачи может иметь не более отличных от нуля неизвестных переменных.

При любом методе решения транспортной задачи начинают с нахождения начального опорного плана.

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

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

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

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

Метод северо-западного угла. При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного х₁₁ («северо-западный угол») и заканчивается клеткой для неизвестного х_mn, т.е. идет как бы по диагонали таблицы.

Пример. На три базы А₁, А₂, А₃ поступил однородный груз в количествах, соответственно равных 140, 180 и 160 ед. Этот груз требуется перевезти в пять пунктов назначения В₁, В₂, В₃, В₄, В₅ соответственно в количествах 60, 70, 120, 130 и 100 ед. Тарифы перевозок единицы груза с каждого из пунктов отправления в соответствующие пункты назначения указаны в следующей таблице:

Таблица 8.1

Найти план перевозок данной транспортной задачи методом северо-западного угла.

Решение. Здесь число пунктов отправления , а число пунктов назначения . Следовательно, опорный план задачи определяется числами, стоящими в 5+3-1=7 заполненных клетках.

Заполнение таблицы начнем с клетки для неизвестного х₁₁, т.е. попытаемся удовлетворить потребности первого пункта назначения за счет запасов первого пункта отправления. Так как запасы пункта А₁ больше, чем потребности пункта В₁, то полагаем , записываем это значение в соответствующей клетке табл. 8.2 и временно исключаем из рассмотрения столбец В₁, считая при этом запасы пункта А₁ равными 80.

Таблица 8.2

Рассмотрим первые из оставшихся пунктов отправления А₁ и назначения В₂. Запасы пункта А₁ больше потребностей пункта В₂. Положим , запишем это значение в соответствующей клетке табл. 8.2 и временно исключим из рассмотрения столбец В₂. В пункте А₁ запасы считаем равными 10 ед. Снова рассмотрим первые из оставшихся пунктов отправления А₁ и назначения В₃. Потребности пункта В₃ больше оставшихся запасов пункта А₁. Положим и запишем в соответствующую клетку табл. 8.2 и считаем потребности пункта В₃ равными 110 ед.

Теперь перейдем к заполнению клетки для неизвестного х₂₃ и т.д. Через шесть шагов остается один пункт отправления А₃ с запасом груза 100 ед. и один пункт назначения В₅ с потребностью 100 ед. Соответственно имеется одна свободная клетка, которую и заполняем, полагая . В результате получаем опорный план

.

Согласно данному плану перевозок, общая стоимость перевозок всего груза составляет

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

Контрольные вопросы:

1. Приведите пример транспортной задачи.

2. Укажите отличия открытой транспортной задачи от закрытой.

3. Опишите метод северо-западного угла.

4. Опишите метод минимального элемента.

Лекция 9. Транспортная задача. Нахождение оптимального плана

План:

1. Метод потенциалов