Обоснование перехода к новому опорному решению

Переход к новому опорному решению. Пусть выбрана свободная клетка(S;T) это значит, что Хst вводится в базис и для клетки (S;T) строится цикл. Клетки цикла мысленно нумеруют начиная с клетки (S;T). Заносится в свободную клетку неизвестное число λ. (λ>0). При этом значение переменных в нечетных клетках увеличиваются на величину λ, в четных-уменьшаются, такие преобразования называются перемещение по циклу числа λ. Выберем λ =min{Xik} стоящих в четных клетках цикла. Если при перемещении λ освободится сразу несколько клеток, оставляем свободную только одну, которой соответствует наибольшее значение Сik, а остальные клетки заполняем нулями. Рассмотрим какое изменение целевой функции Z вызывается перемещением по циклу начинающимся в свободной клетки (S;T) числа λ

∆Z=∑λCik-∑λCik=λ(∑Cik-∑Cik)

Неч четн неч четн

Величина в скобках не зависит от λ, а только от структуры цикла и величины Сik т к с любой свободной клеткой связан только один цикл. Эта величина однозначно определяется для выбранной свободной клетки. Т.е. называют оценкой свободной клетки и обозначается: ∆st=∑Cik-∑Cik => ∆Z=λ∆st т.к λ>0, то для уменьшения Z необходимо чтобы ∆st была меньше 0 (∆st<0).

36. Критерий оптимальности. Переход к оценочной матрице.

От матрицы затрат переходят к оценочной матрице C’, элементы которой- дельта st= C’st находят по формуле - Dst= C’st= Cst+Us+Vt.

Для того, чтобы некоторые опорные решения X= {Xik}, i=1,p, k=1,q транспортной задачи было оптимальным, необходимо и достаточно чтобы существовала система p+q чисел Ui и Vk, которые удовлетворяли бы критериям оптимальности:

Cik+Ui+Vk=0 - для всех занятых клеток.

Cik+Ui+Vk>0 - для всех свободных клеток.

37.Открытая модель транспортной задачи.

Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е. выполняется

условие i=1Sm ai=j=1Sn bj

Называется закрытой моделью;

в противном случае- открытой.

Для открытой модели может быть два случая:

а) суммарные запасы превышают суммарные потребности i=1Sm ai > j=1Sn bi;

b) суммарные потребности превышают суммарные запасы;

Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.

Найти минимальное значение линейной функции z = i=1Sm j=1Sn Cij Xij при ограничениях j=1Sn xij < ai, i=1,2,…,m,

i=1Sm xij=bj, j= 1,2,…,n; (случай а)

j=1Sn xij= ai, i= 1,2,…, m,

i=1Sm xij< bj, j= 1,2,…, n, (случай б)

Открытая модель решается привидением к закрытой модели.В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Вn+1, потребности которого bn+1 = i=1Sm ai – j=1Sn bi. В случае (b), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Аm+1, запасы которого

am+1 = j=1Sn bj – i=1Smai. Стоимость перевозки единицы груза как до фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, т.к. груз в обоих случаях не перевозится.

После преобразований задача принимает вид закрытой модели и решается обычным способом. При равных стоимостях перевозки единицы груза от поставщиков к фиктивному потребителю, затраты на перевозку груза реальным потребителям минимальны, а фиктивному потребителю будет направлен груз от наименее выгодны поставщиков. То же самое получаем и в отношении фиктивного поставщика.

Поиск по сайту: