33. Теорема об эквивалентных преобразованиях матрицы затрат.

Добавление ко всем элементам любой строки или столбца матрицы затрат одного и того же числа, не меняет оценок свободных клеток.

Эти числа Ui, где i=1,p Vk, где k=1,q добавляют ко всем элементам соответствующей строки или столбца. Выбирают их или находят из условия (1) Ci k + Ui+ Vk=0 для всех занятых клеток. Т.к в этой системе p+q неизвестных, а занятых клеток p+q-1, то для определения чисел Ui; Vk одной из переменных можно придать произвольное значение, тогда остальные неизвестные определяться однозначно, тогда от матрицы затрат легко перейти к матрице, элементы которой находятся по формуле: ∆ st=Cst'= Cst+ Us+Vt Для того, чтобы некоторое опорное решение X={Xik} i=1,p k=1,q было оптимальным, необходимым и достаточно, чтобы существовала система p +q чисел Ui и Vk , которые удовлетворяли бы условиям (1) Ci k + Ui+ Vk=0 где i=1,p k=1,q для всех занятых клеток и (2) Ci k + Ui+ Vk ≥0 где i=1,p k=1,q для всех свободных клеток. Эти два условия и есть критерии оптимальности опорного решения ТЗ. Эти условия (1) и(2) называются условиями потенциальности, сами числа Ui и Vk называются потенциалами, а сам метод называется методом потенциалов.

Приращение целевой функции ТЗ

Рассмотрим какое изменение целевой функции Z вызывает перемещение по циклу, начинающее со свободной клетки(S;T) числа λ.

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

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

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

35. Оценка свободной клетки.

Потенциал Ui u Vj находят из равенства Ui+Vj=Cij, справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например U1=0, тогда остальные потенциалы определяются однозначно. Так, если известен потенциал Ui, то Vj = Cij -Ui ; если известен потенциал Vj, то Ui = Cij –Vj. Обозначим ∆ij= Ui+Vj-Cij. Эту оценку называют оценкой свободных клеток. Если ∆≤0, то опорное решение является оптимальным. Если хотя бы одна из оценок ∆>0, то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому.

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

Переход к новому опорному решению. Пусть выбрана свободная клетка(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).