Алгоритм решения транспортной задачи
1. Определяют модель задачи. В случае открытой модели вводят или фиктивного потребителя (если спрос меньше предложения), или фиктивного поставщика (если спрос больше предложения). Спрос фиктивного потребителя устанавливают равным превышению предложения над спросом, а мощность фиктивного поставщика — превышению спроса над предложением. Затраты на перевозки к фиктивному потребителю или от фиктивного поставщика считают равными нулю (или произвольными, но одинаковыми).
2. По тому или иному методу составляют исходный (первоначальный) план распределения поставок: по правилу «северо-западного угла» или с учетом наименьших затрат, заполняя при этом k +l - 1 клеток (k - число поставщиков, l - число потребителей). Если число заполненных клеток окажется меньше этого числа, то в недостающее число свободных клеток вводят нулевые поставки.
3. Оценивают полученное распределение поставок. Для этого в дополнительные строку и столбец таблицы вводят числа, приводящие к нулевым оценки заполненных клеток. Одно из этих чисел при этом выбирают произвольно (его принимают равным нулю), а остальные определяют однозначно. Подсчитывают оценки всех клеток, в том числе и свободных, как алгебраическую сумму показателя затрат клетки и соответствующих чисел из дополнительных строки и столбца. Полученные оценки записывают в следующую таблицу. Если среди оценок свободных клеток не окажется отрицательных, то полученное в предыдущей таблице распределение поставок является оптимальным. В противном случае (имеется хотя бы одна отрицательная оценка) оно не является оптимальным.
4. Для получения нового, улучшенного распределения поставок строят цикл перераспределения для клетки, имеющей наибольшую по абсолютной величине отрицательную оценку. Выполняют перераспределение поставок в цикле для этой клетки. По циклу перемещают наименьшую поставку четных клеток цикла. В ходе перераспределения поставок клетка, для которой образован цикл, получает поставку, а четная клетка, которой соответствовала наименьшая поставка, освобождается.
Если окажется, что освобождается несколько клеток (это происходит, если в несколько четных клетках цикла наименьшие поставки одинаковы), то освобождают только одну из таких клеток (любую), а остальные оставляют заполненными нулевыми поставками. Если наименьшая поставка в четных клетках цикла окажется равной нулю, то по циклу перераспределяют нулевую поставку. Это приводит к тому, что клетка, имевшая нулевую поставку, освобождается, а бывшая свободной клетка заполняется нулевой поставкой; поставки в остальных клетках такого цикла не изменятся. Новое распределение поставок записывают в таблицу, куда уже внесены оценки предыдущего распределения.
5. Производят пересчет оценок, обращая прежде всего в нуль оценку новой заполненной клетки. Если при этом «портятся» нулевые оценки в других заполненных клетках, то против соответствующих столбца или строки записывают специально подобранные числа.
6. Переходя от одной таблицы к другой, повторяют п. 3, 4, 5, пока на каком-то этапе в соответствующей таблице не окажется отрицательных оценок. Тогда распределение поставок в предыдущей таблице является оптимальным. Если в последней оценочной таблице нулевые оценки кроме заполненных клеток имеет хотя бы одна свободная клетка, то оптимальное распределение поставок не является единственным.
7. Вычисляют минимальные затраты на перевозки, для чего в итоговую таблицу записывают показатели затрат из таблицы, данной в условии задачи, и оптимальное распределение.
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Методы уточнения корней нелинейного уравнения.
2. Вычислительные особенности при уточнении корней нелинейного уравнения: скорость сходимости, априорная оценка числа итераций, трудоемкость.
3. Критерий окончания итерационного процесса.
4. Основные этапы отыскания решения нелинейных уравнений.
5. Метод половинного деления.
6. Метод простой итерации.
7. Метод ньютона (метод касательных)
8. Видоизменённый метод ньютона
9. Системы линейных алгебраических уравнений, основные сведения.
10. Норма вектора и норма матрицы.
11. Теоремы об обусловленности решений СЛАУ.
12. Прямые методы решения СЛАУ и их вычислительные особенности.
13. Метод простой итерации решения СЛАУ.
14. Метод Зейделя решения СЛАУ.
15. Варианты постановок задач об обработке экспериментальных данных по методу наименьших квадратов.
16. Вывод системы нормальных уравнений.
17. Линеаризация нелинейных зависимостей целью использования линейного МНК.
18. Постановка задачи интерполяции.
19. Теорема о существовании и единственности интерполяционного полинома.
20. Полином Лагранжа.
21. Метод последовательного исключения неизвестных.
22. Постановка задачи лнейного программирования.
23. Алгоритм симплексного мтода.
24. Сведение любой задачи линейного программирования.
25. Получение допустимого базисного решения.
26. Получение оптимального решения.
27. Геометрическая интерпретация задачи линейного програмирования.
28. Понятие прямой и двойственной задач.
29. Основные теоремы двойственности.
30. Схема построения двойственной задачи.
31. Объективно обусловленные оценки.
32. Постановка транспортной задачи.
33. Экономико-математическая модель транспортной задачи
34. Первоначальное распределение поставок.
35. Методы нахождения опорного решения.
36. Отыскание оптимального плана.
36. Перераспределение поставок
38. Оценки клеток при решение транспортной задачи.
39. Нахождение оптимального распределения поставок.
40. Открытая модель транспортной задачи
41. Метод потенциалов.
42. Алгоритм решения транспортной задачи