20. Исследование плана (варианта) решения задачи на оптимальность.

Теорема об оптимальности: вариант решения задачи будет оптимальным, если найдется такая система абстрактных чисел, называемая потенциалами поставщиков Ui и потенциалами потребителей Vj, при которой для занятых клеток таблицы будет выполняться условие

Vj – Ui Cij (Z min)

или

Vj – Ui Cij (Z max)

причем для занятых клеток Vj – Ui = Cij.

На основании этой теоремы исследование на оптимальность проводится в 2 этапа.

На первом этапе для каждой занятой клетки составляется уравнение Vj – Ui = Cij и получаем систему из ( таких уравнений. Далее решаем эту систему относительно потенциалов, то есть находим значения всех потенциалов. Для удобства расчетов присваиваем любому потенциалу любое числовое значение и в зависимости от него рассчитываем значения остальных. Это необходимо в связи с тем, что количество неизвестных на единицу больше количества уравнений. Чаще всего берут Ui =0 и от него считают все остальные.

На втором этапе для свободных клеток таблицы проверяется условие Vj – Ui Cij (Z min) или Vj – Ui Cij (Z max). Вариант будет оптимальным, если для всех свободных клеток это условие будет выполняться.

Для тех клеток, для которых условие не выполняется, рассчитывается их оценка:

= ǀ (Vj – Ui )- Cijǀ.

Клетка называется «плохой», от плохих клеток необходимо избавляться, перераспределив груз и получив новый вариант.

Смысл перераспределения заключается в том, чтобы в самую плохую клетку ( где наибольшая) перераспределить какое-то количество груза.

Перераспределение груза должно отвечать следующим требованиям:

3. должны выполняться требования системы ограничений модели;

4. вариант решения задачи должен остаться ациклическим, то есть не должна появиться лишняя заполненная клетка, то есть должно выполняться условие неотрицательности в модели, то есть

21. Алгоритм перераспределения грузов.

Смысл перераспределения груза заключается в том, чтобы в самую плохую клетку (где - наибольшая) перераспределить какое-то количество груза.

Перераспределение груза должно отвечать следующим требованиям:

1. должны выполняться требования системы ограничений модели;

2. 2) вариант решения задачи должен остаться ациклическим, то есть не должна появиться лишняя заполненная клетка, то есть должно выполняться условие неотрицательности в модели, то есть .

Алгоритм перераспределения груза

1. наметить маршрут перераспределения груза – для самой плохой клетки строится замкнутый контур таким образом, чтобы все вершины контура, кроме исходной, находились в занятых клетках и все углы при этом были прямые. При вершине свободной клетки ставим знак «+», в остальных вершинах знаки чередуем в любых направлениях. Конфигурация контуров может быть самая различная.

Цепью называется последовательный набор клеток, в котором каждые 2 соседние клетки расположены в одном ряду (строке или столбце) причем никакие 3 клетки в 1 ряду не располагаются. Если последняя клетка цепи расположена в 1 ряду с первой клеткой, то такая замкнутая цепь называется цикл.

2. выбрать количество груза для перераспределения – из отрицательных вершин контура выбрать наименьшее значение . В новой рабочей таблице получаем следующий вариант решения задачи: выбранное количество из отрицательных вершин контура предыдущей таблицы отнимаем, а к положительным – прибавляем. Клетки, не являющиеся вершинами контура свое значение не меняют.

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