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

Краткая теория

Примеры решения задач

Пример 1

Пример 2

Пример 3

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

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

Краткая теория
Примеры решения задач

Транспортную задачу по критерию стоимости представим в виде таблицы:

В таблице указаны поставщики , ,…, , у которых имеется в наличии соответственно , ,…, единиц однородного груза. Данный груз должен быть доставлен потребителям , ,…, в количествах , ,…, единиц. Заданы стоимости перевозок единицы груза от i-го поставщика j-му потребителю. Требуется спланировать перевозки, то есть указать, сколько единиц груза должно быть отправлено от i-го поставщика j-му потребителю так, чтобы максимально удовлетворить спрос потребителей и чтобы суммарные транспортные затраты на перевозки были при этом минимальными.

Задачи, где суммарные запасы грузов поставщиков равны суммарным потребностям:

называются закрытыми, а задачи с отсутствием баланса между ресурсами и потребностями:

называются открытыми.

Для составления математической модели задачи введем переменные обозначающие количество единиц груза, перевозимого от i-го поставщика j-му потребителю. Очевидно, что таких переменных и что они должны удовлетворять следующим условиям:

1) Ограничения по запасам:

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

3) Условия неотрицательности:

Суммарные транспортные затраты на перевозки:

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

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

При решении транспортной задачи важное значение имеет теорема о ранге матрицы: ранг матрицы транспортной задачи на единицу меньше числа уравнений:

где m - число поставщиков, n - число потребителей.

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

Если число занятых клеток удовлетворяет условию , то план перевозок называют невырожденным, а если число занятых клеток не удовлетворяет этому условию, то план перевозок называют вырожденным.

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

1) определение исходного опорного плана;

2) оценка этого плана;

3) переход к следующему плану путем однократной замены одной из базисных переменных на свободную.

Существуют различные способы реализации приведенных этапов решения транспортной задачи. Сюда можно отнести правило «северо-западного угла», правило «минимального элемента», метод Фогеля, метод потенциалов и др.

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

где - потенциал i-го поставщика; -потенциал k-го потребителя; - тариф базисной клетки.

Решив систему из уравнений вида , получим значения потенциалов и соответственно i-го поставщика и k-го потребителя. Далее вычислим оценки свободных клеток по формуле:

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

Например, цикл имеет вид, показанный на рисунке, где клетка - свободная.

Свободной клетке условно приписываем знак "+", тогда следующей клетке по ходу часовой или против часовой стрелки - знак "-" и так далее; знаки чередуются. В отрицательных вершинах цикла определяем наименьшую загрузку клетки, то есть единиц.

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

Смежные темы решебника:

Заказать решение задач, узнать цену help100task@yandex.ru, или шлите свои условия сюда: - на 100task.ru делать работы удобнее, надежнее, аккуратнее, быстрее, безопаснее и дешевле чем в агенствах и на биржах.
Или подписаться на телеграм-канал, чтобы не потерять контакты:

Скачать пример 1 в формате pdf

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

Требуется:

1) Составить математическую модель задачи;

2) Найти оптимальное решение транспортной задачи методом потенциалов.

Решение

Обозначим через количество груза, перевозимого от i-го поставщика j-му потребителю. Тогда общая стоимость перевозок равна:

Ограничения для поставщиков:

Ограничения для потребителей:

Объем суммарных поставок любого поставщика к потребителю не может быть отрицательным числом, поэтому справедливы ограничения

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

В нашем случае:

Модель транспортной задачи закрытая.

Построим начальный опорный план по правилу минимального элемента.

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

Далее 4-й столбец в расчет уже не принимается.

Просматриваем оставшиеся таблицы клетки. Наименьший тариф имеет клетка (1,3).

Далее, действуя по аналогичной схеме, получаем:

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

Вычислим оценки свободных клеток по формуле .

Для клетки (2,3), оценка которой является неположительной и минимальной, строим цикл.

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

Потенциалы:

Оценки свободных клеток:

Для клетки (3,3), оценка которой является неположительной и минимальной, строим цикл.

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

Потенциалы:

Оценки свободных клеток:

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

Оптимальный план перевозок:

Оптимальные издержки:

Ответ:

Пункт поставляет 8 единиц груза в пункт и 15 единиц груза в пункт

Пункт поставляет 14 единиц груза в пункт , 1 единицу груза в пункт и 10 единиц груза в пункт .

Пункт поставляет 10 единиц груза в пункт и 7 единиц груза в пункт

При этом стоимость перевозки будет минимальной и составит 170 ден.ед.

Скачать пример 2 в формате pdf

В пункте (i =1, 2, 3) находится однородная продукция в количестве единиц. Себестоимость единицы продукции в пункте равна Готовая продукция поставляется в пункт (j=1,2,3), потребности которого составляют единиц. Стоимость перевозки единицы продукции из пункта в пункт известна. Требуется:

- составить математическую модель задачи, позволяющую найти план перевозки готовой продукции из пункта производства в пункт потребления при полном удовлетворении спроса на продукцию в этих пунктах, обеспечивающего минимальные суммарные затраты, вызванные производством и доставкой продукции;

- найти оптимальный план перевозки продукции при дополнительном условии, что продукция пункта , в котором себестоимость ее производства наименьшая, должна быть распределена полностью;

- вычислить величину минимальных суммарных затрат на производство и доставку продукции;

- назвать пункты, в которых останется нераспределенная продукция, и указать объемы такой продукции.

; ;

Решение

Составим матрицу затрат на производство и транспортировку продукции.

Получаем:


9	11	8	140
13	8	11	180
6	9	11	240
180	360	90

Обозначим через (; ) количество груза, перевозимого от i-го поставщика j-му потребителю. Тогда общая стоимость перевозок равна:

Ограничения для поставщиков:

Ограничения для потребителей:

Объем суммарных поставок любого поставщика к потребителю не может быть отрицательным числом, поэтому справедливы ограничения: .

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

В нашем случае:

Модель транспортной задачи открытая.

Добавим фиктивного поставщика , у которого находится 630-560=70 единиц груза.

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

Построим начальный опорный план по правилу минимального элемента.

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

Далее 4-я строка в расчет уже не принимается.

Просматриваем оставшиеся таблицы клетки. Наименьший тариф имеет клетка (3,1).

Далее, действуя по аналогичной схеме, получаем:

Вычислим оценки свободных клеток по формуле .

Для клетки (4,2), оценка которой является неположительной и минимальной, строим цикл.

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

Потенциалы:

Оценки свободных клеток:

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

Оптимальный план перевозок:

Минимальные издержки:

При реализации оптимального плана 2-му потребителю не хватит груза в размере 70 ед.

Пункты\Заказчики

Скачать пример 3 в формате pdf

Филиалы банка , , выделяют клиентам , , кредиты на расширение производства сроком на один год. Процентная ставка , , устанавливаются индивидуально каждому клиенту. Суммы , , которые филиалы могут выделить клиентам, потребность , клиентов в кредитах и процентные ставки , приведены.

Требуется:

1) составить экономико-математическую модель задачи, которая позволила бы банку распределить кредиты между клиентами и получить при этом максимальную прибыль;

2) методом потенциалов найти оптимальный план данной задачи при дополнительном условии, что филиал не выделяет кредит клиенту , но потребность данного клиента в кредите должна быть удовлетворена;

3) найти величину максимальной прибыли ;

4) указать клиентов, которые недополучат кредит, а также его сумму.

;

; ; ;

;

Решение

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

Ограничения для филиалов:

Ограничения для клиентов:

Объем суммарных поставок любого поставщика к потребителю не может быть отрицательным числом, поэтому справедливы ограничения:

2) Решим задачу методом потенциалов:

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

В нашем случае:

Модель транспортной задачи открытая.

Добавим фиктивного поставщика , у которого находится 690-640=50 единиц груза.

Учтем дополнительное условие, что филиал не выделяет кредит клиенту , но потребность данного клиента в кредите должна быть удовлетворена. Для этого клетку (3,4) и клетку, соответствующую фиктивному филиалу (5,4) заблокируем тарифом "М".

Построим начальный опорный план по правилу максимального элемента.

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

Далее 4-й столбец в расчет уже не принимается.

Просматриваем оставшиеся таблицы клетки. Наименьший тариф имеет клетка (2,1).

Далее, действуя по аналогичной схеме, получаем:

Вычислим оценки свободных клеток по формуле .

Для клетки (2,2), оценка которой является неотрицательной и максимальной, строим цикл.

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

Потенциалы:

Оценки свободных клеток:

Для клетки (5,3), оценка которой является неотрицательной и максимальной, строим цикл.

Потенциалы:

Оценки свободных клеток:

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

Оптимальный план:

3) Прибыль, полученная банками:

При реализации оптимального плана клиенту не достанется кредита в размере 50 ден.ед.

Краткая теория
Примеры решения задач