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

Основные шаги при решении транспортной задачи:

1. Найти начальный допустимый план.

2. Выбрать из небазисных переменных ту, которая будет вводиться в базис. Если все небазисные переменные удовлетворяют условиям оптимальности, то закончить решение, иначе к след. шагу.

3. Выбрать выводимую из базиса переменную, найти новое базисное решение. Вернуться к шагу 2.

Всякое неотрицательное решение систем линейных уравнений (2) и (3), определяемое матрицей , называется планом транспортной задачи. Опорным (базисным) планом Т-задачи называют любое ее допустимое, базисное решение.

Обычно исходные данные транспортной задачи записывают в виде таблицы.

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

Число переменных в транспортной задаче с m пунктами отправления и n пунктами назначения равно m*n, а число уравнений в системах (2) и (3) равно m+n. Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно m+n–1. Следовательно, опорный план транспортной задачи может иметь не более m+n–1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности m+n–1, то план является невырожденным, а если меньше – то вырожденным.

Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.

Дата добавления: 2014-11-29