Билет.метод потенциалов.

Пусть получен первоначальный опорный план и пусть этот план невырожденный. После построения исходного опорного плана все переменные разбиты на 2 группы: базисные и свободные. Рассмотрим случай, когда m=n. для проверки плана на оптимальность выразим базисные переменные и функцию цели через свободные. Коэффициенты ∂ при свободной переменной в выражении ф-ии цели через свободные переменные называются оценками соотв. свободных клеток.

Теорема критерий оптимальности. Опорный план оптимален тогда и только тогда,когда оценки всех свободных клеток неотриц. док-во: Если ∂₁₂<0. То F можно увеличить за счет увеличения X₁₂. Если же наоборот ∂>0, то увеличение x₁₂ не уменьшит F, т.е. план оптимальный. Для нахождения коэффициента ∂₁₂ при свободных переменных составим каждому поставщику А некоторую величину U, которую назовем потенциалом поставщика. Каждому потребителю В поставим величину V- потенциал потребителя. Свяжем эти величины соотношением U+V=C. можно доказать,что совокупность уравнений U+V=C, составленных для всех базисных переменных явл совместной системой из m+n-1 уравнений с m+n неизвестными. значение одной из переменной можно задать произвольно, тогда остальные значения найдутся из системы однозначно. Составим систему потенциалов. Обозначим для свободных переменных x_pq сумму соотв.потенциалов через С_pq. Таким образом, для того,чтобы опорный план был оптимальным, необходимо и достаточно, чтобы 1) U+V≤C_pq(для всех свободных клеток) 2) U+V=0(для занятых клеток)

Если хотя бы одной из свободных клеток оценка отрицательна, то план неоптимален и его можно улучшить, вводя в базис переменную, соотв. Клетке с отриц. Оценкой. Для этого строят цикл пересчета, т.е цикл в таблице с опорным планом, одна из вершин которой лежит в свободной клетке с отриц.оценкой, а остальные в занятых клетках. Цикл, в вершинах которого проставлены знаки, называется означенным. Для каждой свободной клетки существует единственный план пересчета, причем операция означивания явл конкретной. Чтобы найти перераспределяемый объем перевозок, находим Ө₀=minx_ij. Где х- перевозки, стоящие в вершинах цикла, отмеченные знаком «– «. Значение Ө0 определяет сколько единиц можно распределить по найденному циклу.это значение записываем в свободную клетку со знаком + и далее, двигаяссь по циклу, вычитаем Ө0 из объемов, помеченный знаком – и прибавляет к объему со знаком +.

Алгоритм: 1) найдем опорный план методом северо-западного угла. 2) проверка на оптимальность- составим систему потенциалов 3) найдем оценки свободных клеток 4) перейдем к новому опорному плану

Дата добавления: 2015-08-20