Специальные задачи линейного программирования
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Вµди ограничений задачи есть линейно-зависимое ограничение. Следовательно, число линейно-независимых ограничений равно m+n-1 и базис задачи состоит из m+n-1 компонент. Теорема доказана.
В силу специфики содержательной постановки транспортной задачи допустимое решение называется планом, базисное допустимое решение называется опорным планом, оптимальное решение называется оптимальным планом.
Теорема 2. Оптимальный план закрытой модели транспортной задачи существует всегда.
Доказательство. Оптимальное решение задачи ЛП существует, если, во-первых, существует допустимое решение и, во-вторых, целевая функция ограничена на этом допустимом решении.
Покажем существование допустимого решения. Так как суммарные запасы совпадают с суммарными потребностями то всегда можно найти такой план перевозок, который будет допустимым решением (все запасы вывозятся и все потребности выполняются в силу балансового равенства).
Покажем ограниченность целевой функции. Так как
Следовательно, L ограничена снизу нулем для всех допустимых решений. Теорема доказана.
Глава 2. Практическая часть
.1 Построение первоначального опорного плана
Базисное решение закрытой модели транспортной задачи
Данная модель является открытой, так как А>В в этом случае нам надо добавить столбец, в стоимость мы поставим 0, а в запасы нужно добавить не достающие значение. В нашем случае 50.
Будет иметь следующий вид:
Теперь расставим значения, начнем с наименьшей стоимости.
Проверка занятых клеток (m+n-1) если окажется что число занятых клеток меньше (m+n-1), то дополним их до (m+n-1) нулями. Теперь найдем сумму занятых клеток, S = значение*стоимость.
=70+10+180+210+40=510 (Данный план не оптимален.)
.2 Построение системы потенциалов (для значений)
Используя первое условие оптимального плана, найдем m+n чисел, так чтобы сумма потенциалов для занятых клеток была ровна стоимости.
= большему числу занятых клеток.
.3 Проверка плана на оптимальность
Проверяем второе условие оптимального плана, т.е. сравниваем суммы потенциалов со стоимостями. Если эти суммы не больше стоимости, то план оптимальный, в противном случае неоптимальный. Следует перейти к улучшению.
2.4 Улучшение плана
Рассмотрим все свободные клетки, где произошло нарушение оптимального плана, и выберем ту в которой разность (Ai+Bj)-Cij наибольшее поставим (+), затем для этой клетки согласно утверждению о циклах стоимости единицы цикла, отметим эти клетки по переменно.