КАТЕГОРИИ: Архитектура-(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) |
Проверка найденного опорного решения на оптимальность
Определение эффективного варианта доставки изделий к потребителю Нахождение исходного опорного решения
Условия задачи и ее исходное опорное решение будем записывать в распределительную таблицу. Клетки, в которые поместим грузы, называются занятыми, им соответствуют базисные переменные опорного решения. Остальные клетки незанятые, или пустые, им соответствуют свободные переменные. В верхнем правом углу каждой клетки будем записывать тарифы. Существует несколько способов нахождения исходного опорного решения. Рассмотрим один из них — метод минимального тарифа (элемента). Согласно этому методу, грузы распределяются в первую очередь в те клетки, в которых находится минимальный тариф перевозок cij. Далее поставки распределяются в незанятые клетки с наименьшими тарифами с учетом оставшихся запасов у поставщиков и удовлетворения спроса потребителей. Процесс распределения продолжают до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены. При распределении грузов может оказаться, что количество занятых клеток меньше, чем т + п - 1. В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки называют условно занятыми. Нулевые поставки помещают в незанятые клетки с учетом наименьшего тарифа таким образом, чтобы в каждых строке и столбце было не менее чем по одной занятой клетке. Рассмотрим нахождение исходного опорного решения транспортной задачи на конкретном примере.
На складах A 1, А 2, А 3 имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители В 1, В 2, B 3 должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей (усл. ед.)
Проверим, является ли данная транспортная задача закрытой:
следовательно, данная транспортная задача закрытая. Найдем исходное опорное решение по методу минимального тарифа.
Число занятых клеток в табл. 23.2 равно т + п - 1 = 3 + 3 – 1 = 5, т.е. условие невырожденности выполнено. Получили исходное опорное решение, которое запишем в виде матрицы:
Стоимость перевозки при исходном опорном решении составляет
Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система т + п действительных чисел ui и vj, удовлетворяющих условиям ui + vj = cij для занятых клеток и ui + vj - сij ≤ 0 для свободных клеток. Числа ui и vj называют потенциалами. В распределительную таблицу добавляют строку vj и столбец ui. Потенциалы ui и vj находят из равенства ui + vj = cij, справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например и 1 = 0, тогда остальные потенциалы определяются однозначно. Так, если известен потенциал ui, то vj = сij — ui; если известен потенциал vj, то ui = cij – vj. Обозначим Δ ij = ui + vj - cij. Эту оценку называют оценкой свободных клеток. Если Δ ij ≤ 0, то опорное решение является оптимальным. Если хотя бы одна из оценок Δ ij > 0, то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому. Проверим найденное опорное решение на оптимальность, добавив в распределительную табл. 23.3 столбец ui и строку vj. Полагая u 1 = 0, запишем это значение в последнем столбце таблицы.
Рассмотрим занятую клетку первой строки, которая расположена в первом столбце (1,1), для нее выполняется условие и 1 + v 1 = 2, откуда v 1 = 2. Это значение запишем в последней строке таблицы. Далее надо рассматривать ту из занятых клеток таблицы, для которой один из потенциалов известен. Рассмотрим занятую клетку (3,1): и 3 + v 1 = 3, v 1 = 2, откуда и 3 = 1. Для клетки (3,3): и 3 + v 3 = 8, и 3 = 1, v 3 = 7. Для клетки (2,3): и 2 + v 3 = 5, v 3 = 7, и 2 = -2. Для клетки (2,2): u 2 + v 2 = 1, и 2 = -2, v 2 = 3. Найденные значения потенциалов заносим в таблицу. Вычисляем оценки свободных клеток:
Получили одну оценку Δ13 = 5 > 0, следовательно, исходное опорное решение не является оптимальным и его можно улучшить.
Дата добавления: 2014-10-15; Просмотров: 1096; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |