Транспортная задача. Метод потенциала

7 ТРАНСПОРТНАЯ ЗАДАЧА. МЕТОД ПОТЕНЦИАЛА

Цель лекции: рассмотреть метод потенциалов для решения транспортных задач.

КЛ. слова: транспортная таблица, метод "северо-западного угла", потенциалы, характеристики решеток.

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

Различия транспортных отчетов:

• ограничения записываются в виде уравнения;
• каждая переменная входит только в два уравнения;
• коэффициенты переменных, входящих в ограничения, равны 1;
• значения размеров переменных одинаковы.

Методы для решения транспортных задач: метод распределения, метод потенциала, метод дифференциальной ренты.

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

Отчет. Четыре фермы должны перевозить сено с трех полей. В первой долине находится 400 тонн сена, во второй-700 тонн, в третьей-1200 тонн сена. Потребности ферм следующие: первая – 700 тонн, вторая – 200 тонн, третья – 600 тонн и четвертая - 800 тонн. Расстояния от полей до ферм приведены в следующей таблице.

Расстояния от полей до ферм, км

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

Пункт выдачи груза называется поставщиком, а пункт приема груза-потребителем. В этом отчете в качестве поставщиков будут поля, а в качестве потребителей – фермы.

В отчете указывается, что общий объем сена на полях равен общему объему потребностей ферм (2300 тонн).

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

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

Транспортный учет

Экономико-математическая модель задачи

Целевая функция:

Z = 18 х11 + 12 х12 + 13 х13 + 7 х14 + 17 х21 + 10 х22 + 11 х23 +

+ 13 х24 + 15 х31 + 11 х32 + 10 х33 + 9 х34 → min

Ограничения:

1. Сено, расположенное на полях, необходимо вывезти в количестве, имеющем:

х11 + х12 + х13 + х14 = 400

х21 + х22 + х23 + х24 = 700

х31 + х32 + х33 + х34 = 1200

1. Необходимо заполнить необходимые объемы ферм:

х11 + х21 + х31 = 700

х12 + х22 + х32 = 200

х13 + х23 + х33 = 600

х14 + х24 + х34 = 800

1. Переменные не должны быть отрицательным числом:

Составляем первый базисный план методом «северо-западного угла". Далее улучшаем план методом потенции.