Проверка полученного опорного плана на оптимальность

2.2 Проверка полученного опорного плана на оптимальность

Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система m+n действительных чисел u_i и v_j, удовлетворяющих условиям u_i+v_j=c_ij для занятых клеток и u_i + v_j –c_ij ≤ 0 для свободных клеток.

Числа u_i и v_j называют потенциалами. В распределительную таблицу добавляют строку v_j и столбец u_i.

Потенциалы u_i и v_j находят из равенства u_i + v_j = c_ij, справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например u₁ = 0, тогда остальные потенциалы определяются однозначно. Так, если известен потенциал u_i, то v_j=c_ij–u_i; если известен потенциал v_j, то u_i=cij-vj.

Обозначим ∆_ij=u_i+v_j–c_ij. Эту оценку называют оценкой свободных клеток. Если ∆_ij≤0, то опорное решение является оптимальным. Если хотя бы одна из оценок ∆_ij>0, то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому [1].

 

2.3 Методика решения параметрической транспортной задачи

Задача формулируется следующим образом: для всех значений параметра δ≤k≤φ где δ и φ – произвольные действительные числа, найти такие значения  которые обращают в минимум функцию

где X_ij – объем поставок груза,

при ограничениях:

Xij≥0,  

Пользуясь методом потенциалов, (Фогеля) решаем задачу при k=δ до получения оптимального решения. Признаком оптимальности является условие:

 для незанятых клеток

и  для занятых клеток,

где  – потенциалы строк, столбцов распределительной таблицы.

Условие совместимости транспортной задачи запишется в виде

Значения aij и Bij определяются из условия

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

Значения k находятся в пределах k₁≤k≤k₂:

если существует хотя бы одно B_ij>0;

если все B_ij≥0

если существует хотя бы одно B_ij>0;

если все B_ij≤0.

Алгоритм решения.

1)         Задачу решаем при конкретном значении параметра k=δ до получения оптимального решения.

2)         Определяем a_ij и B_ij.

3)         Вычисляем значение параметра k.

4)         Если k>δ, производим перераспределение поставок и получаем новое оптимальное решение. Если k = δ, то процесс решения окончен [1].

3 Метод решения задачи об оптимальных перевозках средствами Ms Excel

 

Нахождение оптимального плана перевозок с применением компьютерной программы Ms Excel осуществляется посредством функции "Поиск решения".

Схема выполнения:

1. Для удобства расчетов необходимо отдельно создать матрицу, отображающую стоимость перевозок (C_ij) (рис 3.1.), а также матрицу, которая должна будет отображать искомый план перевозок (рис. 3.2.).

Рис. 3.1. Фрагмент окна программы Ms Excel: Модель таблицы «Стоимость перевозок».

2. В таблице «Стоимость перевозок» в ячейках запасов поставщиков и потребностей потребителей записать количество запасов поставщиков и потребностей потребителей соответственно, указанное в условии задачи.

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

Рис. 3.2. Фрагмент окна программы Ms Excel: Модель таблицы «План перевозок».

4. В ячейке целевой функции ввести формулу, высчитывающую сумму произведений элементов матрицы "Стоимость перевозок" и соответствующих элементов матрицы "План перевозок".

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

6. В диалоговом окне "Параметры поиска решения" установить параметр "Линейная модель" и число итераций, равное 100.

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

После выполнения вышеуказанных действий при условии, что задача имеет решение, в матрице «План перевозок» запишется оптимальное решение задачи, т.е. оптимальный план перевозок с указанием объемов поставок в каждой ячейке. В ячейке с целевой функцией запишутся совокупные затраты поставок.