Транспортная задача. Метод потенциала
Автор: Anelya7854 • Ноябрь 14, 2021 • Реферат • 1,241 Слов (5 Страниц) • 291 Просмотры
7 ТРАНСПОРТНАЯ ЗАДАЧА. МЕТОД ПОТЕНЦИАЛА
Цель лекции: рассмотреть метод потенциалов для решения транспортных задач.
КЛ. слова: транспортная таблица, метод "северо-западного угла", потенциалы, характеристики решеток.
Транспортный учет является важнейшим расчетом задач линейного программирования. По сравнению с другими отчетами, это просто. Для его производства разработано несколько методов.
Различия транспортных отчетов:
- ограничения записываются в виде уравнения;
- каждая переменная входит только в два уравнения;
- коэффициенты переменных, входящих в ограничения, равны 1;
- значения размеров переменных одинаковы.
Методы для решения транспортных задач: метод распределения, метод потенциала, метод дифференциальной ренты.
Для построения опорного (первого базисного) плана при решении транспортных задач можно использовать метод «северо-западного угла», метод минимального элемента, метод аппроксимации Фогеля и многое другое.
Отчет. Четыре фермы должны перевозить сено с трех полей. В первой долине находится 400 тонн сена, во второй-700 тонн, в третьей-1200 тонн сена. Потребности ферм следующие: первая – 700 тонн, вторая – 200 тонн, третья – 600 тонн и четвертая - 800 тонн. Расстояния от полей до ферм приведены в следующей таблице.
Расстояния от полей до ферм, км
Угодья | Фермы | |||
1 | 2 | 3 | 4 | |
1 | 18 | 12 | 13 | 7 |
2 | 17 | 10 | 11 | 13 |
3 | 15 | 11 | 10 | 9 |
Необходимо найти план, определяющий минимальный объем общих затрат на транспортировку сена.
Пункт выдачи груза называется поставщиком, а пункт приема груза-потребителем. В этом отчете в качестве поставщиков будут поля, а в качестве потребителей – фермы.
В отчете указывается, что общий объем сена на полях равен общему объему потребностей ферм (2300 тонн).
Такие отчеты называются закрытыми отчетами.
Обозначим груз, который доставляется с каждой долины на каждую ферму.
Транспортный учет
2300 | 700 | 200 | 600 | 800 |
400 | 18 х11 | 12 х12 | 13 х13 | 7 х14 |
700 | 17 х21 | 10 х22 | 11 х23 | 13 х24 |
1200 | 15 х31 | 11 х32 | 10 х33 | 9 х34 |
Экономико-математическая модель задачи
Целевая функция:
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
Ограничения:
- Сено, расположенное на полях, необходимо вывезти в количестве, имеющем:
х11 + х12 + х13 + х14 = 400
х21 + х22 + х23 + х24 = 700
х31 + х32 + х33 + х34 = 1200
- Необходимо заполнить необходимые объемы ферм:
х11 + х21 + х31 = 700
х12 + х22 + х32 = 200
х13 + х23 + х33 = 600
х14 + х24 + х34 = 800
- Переменные не должны быть отрицательным числом:
Составляем первый базисный план методом «северо-западного угла". Далее улучшаем план методом потенции.
...