Транспортная задача (1 а л.) 1 Определение транспортной модели
Опорным решением будем называть такое, которое имеет m+n-1 перевозок, отличных от нуля. Это условие является условием допустимости
жүктеу/скачать 0.49 Mb.
|
- Бұл бет үшін навигация:
- 3.2 Алгоритм решения транспортной задачи
| Опорным решением будем называть такое, которое имеет m+n-1 перевозок, отличных от нуля. Это условие является условием допустимости решения транспортной задачи. Если в таблице число ненулевых переменных меньше, то такое решение называется вырожденным, но этот факт не влияет на вычислительный алгоритм. В этом случае в транспортной таблице значение одной переменной считается равной 0. Если в решении число отличных от нуля переменных в точности равно (m+n-1), то решение называется невырожденным.
Больше чем (m+n-1) не нулевых переменных в транспортной таблице быть не может, так как в противном случае такое решение не будет опорным. Это значит, что данный план перевозок не соответствует угловой точке области допустимых решений и не может быть ее оптимальным решением. Оптимальным решением будет одно из опорных решений, которое обеспечивает минимальную сумму затрат по всем перевозкам. Если при решении задачи линейного программирования симплексным методом требовалось на каждом шаге пересчитывать матрицу целиком, то при решении транспортной задачи одним из методов поиска оптимального решения пересчитывается только часть матрицы (замкнутый контур), что резко сокращает количество вычислений. Решение транспортной задачи, так же как и задача линейного программирования включает в себя три этапа: определение начального допустимого базисного решения; проверка полученного решения на оптимальность; получение нового решения, в случае, если предыдущее решение не было оптимальным. Для построения начального допустимого решения могут быть использованы следующие методы: метод "северо-западного угла"; метод наименьшего элемента; Для определения оптимального плана перевозок будем использовать метод потенциалов. 3.2 Алгоритм решения транспортной задачи Алгоритм решения транспортной задачи повторяет основные этапы симплекс-метода. Найти начальное допустимое решение. Выбрать из числа небазисных переменных переменную, вводимую в базис. Если все небазисные переменные удовлетворяют условию оптимальности, то закончить решение, в противном случае перейти к шагу 3. Выбрать выводимую из базиса переменную исходя из условия допустимости из числа переменных входящих в текущий базис. Затем найти новое базисное решение и перейти к шагу2. жүктеу/скачать 0.49 Mb. Достарыңызбен бөлісу:
|