1. Введение 3
2. Постановка классической транспортной задачи 5
3. Методы нахождения начального опорного плана 7
4. Метод потенциалов 11
5. Постановка неоднородной транспортной задачи (задачи с фиксированными
доплатами) 14
6. Приближенные методы решения неоднородной транспортной задачи
6.1 .метод на основе перебора опорных планов 17
6.2. метод на основе искусственного создания вырожденности 19
6.3 .метод Балинского 21
7. Программная реализация методов 23
8. Описание примеров 28
9. Выводы 30
10. Литература 31
Транспортная задача получила в настоящее время широкое распространение в теоретических обработках и практическом применении в транспорте и промышленности. Особенно большое значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработан специальный метод. Этот метод, как и симплексный метод, позволяет найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
Целью транспортной задачи является обеспечение получения (доставки) продукции (товара) потребителю в нужное время и место при минимально возможных совокупных затратах трудовых, материальных, финансовых ресурсов.
Если в классической транспортной задаче считаемое СуХу в целевой функции увеличивается на неотрицательное значение dy, задача усложняется. Такая задача носит название неоднородной транспортной задачи или задачи с фиксированными доплатами. К задачам такого вида классические методы решения не применимы. Для неоднородных транспортных задач существуют лишь приближенные методы решения.
Цель данной работы - изучение и сравнение между собой приближенных методов решения неоднородной транспортной задачи (задачи с фиксированными доплатами). С этой целью программно реализованы три известных приближенных метода решения указанной задачи. Этими методами решено много примеров различной размерности. На основании решенных примеров сделаны выводы об эффективности исследуемых методов.
В результате тестирования многочисленных примеров неоднородных транспортных задач разной размерности всеми тремя методами был сделан следующий вывод. В абсолютном большинстве задач наиболее точное решение дает метод Балинского. И эта точность зависит от размерности задачи. А именно, чем больше размерность, тем точнее решение.
В неоднородных транспортных задачах с фиксированными доплатами, где размерность задачи не превосходит трех поставщиков и потребителей, приемлем второй метод, основанный на искусственном создании вырожденности. Таким образом, с задачами маленьких размерностей второй метод работает лучше Других.
Отметим, что методы на основе перебора и Балинского дают близкие, мало отличающиеся суммарные затраты, но, при решении всех тестовых примеров, точность методом Балинского достигается быстрее. Поэтому при решении транспортных задач с фиксированными доплатами в качестве рекомендуемого предлагается выбрать именно метод Балинского.
