КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Проверка опорного плана на оптимальность
Начальный опорный план - в левом нижнем углу клеток. Нахождение начального опорного плана (угловой точки). Следуем вышеприведенному алгоритму. Транспортная задача закрытая. Используем метод минимальной стоимости. Его суть: а) находим клетку с минимальной стоимостью и в максимально возможной степени удовлетворяем спрос соответствующего потребителя. Результат записываем в левый нижний угол клетки. (табл. 2) Табл. 2
б) правило: “там, где 0 вычеркиваем” в) среди всех невычеркнутых клеток вновь находим клетку с минимальной стоимостью и вновь повторяем алгоритм. г) контроль: общее число занятых клеток должно быть равно m + n – 1. У нас 3+ 3- 1= 5. Проверка на оптимальность осуществляется с помощью потенциалов во вновь составленной таблице (табл. 3) Табл. 3
ПРАВИЛО 1: для всех занятых клеток должно быть: u i + v j = c i j (1) (сумма потенциалов равна стоимости). Это правило- для заполнения столбцов U, V. ПРАВИЛО 2: для всех свободных клеток должно быть: u i + v j ≤ c i j (2) Это правило проверки оптимальности. Условие оптимальности нарушено в наибольшей степени клетке (1, 2)! Итак, полученный опорный план не оптимален!
Дата добавления: 2015-06-04; Просмотров: 365; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |