Постановка и решение транспортной параметрической задачи (стр. 2 из 4)
где Xij – объем поставок груза,
при ограничениях:
Xij≥0,
Пользуясь методом потенциалов, (Фогеля) решаем задачу при k=δ до получения оптимального решения. Признаком оптимальности является условие:
для незанятых клетоки
для занятых клеток,где
– потенциалы строк, столбцов распределительной таблицы.Условие совместимости транспортной задачи запишется в виде
Значения aij и Bij определяются из условия
где
определяются из систем уравнений 
Значения k находятся в пределах k1≤k≤k2:
если существует хотя бы одно Bij>0;
если все Bij≥0
если существует хотя бы одно Bij>0;
если все Bij≤0.
Алгоритм решения.
1) Задачу решаем при конкретном значении параметра k=δ до получения оптимального решения.
2) Определяем aijи Bij.
3) Вычисляем значение параметра k.
4) Если k>δ, производим перераспределение поставок и получаем новое оптимальное решение. Если k = δ, то процесс решения окончен [1].
3 Метод решения задачи об оптимальных перевозках средствами MsExcel
Нахождение оптимального плана перевозок с применением компьютерной программы MsExcelосуществляется посредством функции "Поиск решения".
Схема выполнения:
1. Для удобства расчетов необходимо отдельно создать матрицу, отображающую стоимость перевозок (Cij) (рис 3.1.), а также матрицу, которая должна будет отображать искомый план перевозок (рис. 3.2.).
Рис. 3.1. Фрагмент окна программы MsExcel: Модель таблицы «Стоимость перевозок».
2. В таблице «Стоимость перевозок» в ячейках запасов поставщиков и потребностей потребителей записать количество запасов поставщиков и потребностей потребителей соответственно, указанное в условии задачи.
3. Таблицу "План перевозок" создать с пустыми полями (заполненными единицами), заранее заданного числового формата. В ячейках запасов (потребностей) каждого поставщика (потребителя) ввести формулу, выполняющую суммирование всех возможных поставок этого поставщика (потребителя).
Рис. 3.2. Фрагмент окна программы MsExcel: Модель таблицы «План перевозок».
4. В ячейке целевой функции ввести формулу, высчитывающую сумму произведений элементов матрицы "Стоимость перевозок" и соответствующих элементов матрицы "План перевозок".
5. В диалоговом окне функции "Поиск решения" установить необходимые ограничения, в целевой ячейке указать адрес ячейки с формулой целевой функции и установить ее равной минимальному значению, в качестве изменяемых ячеек выбрать диапазон всех элементов матрицы "План перевозок". Ограничения в "Поиске решений" заключаются в необходимости равенства запасов (потребностей), в матрице "План перевозок" соответствующим запасам и потребностям, указанным в матрице "Стоимость перевозок". Также все элементы матрицы "План перевозок" должны быть неотрицательными и целочисленными.
6. В диалоговом окне "Параметры поиска решения" установить параметр "Линейная модель" и число итераций, равное 100.
7. Выполнить функцию "Поиск решения" нажатием на кнопку "Выполнить". В качестве отчета по результатам выбрать необходимый пункт в списке "Тип отчета" диалогового окна «Результаты поиска решения».
После выполнения вышеуказанных действий при условии, что задача имеет решение, в матрице «План перевозок» запишется оптимальное решение задачи, т.е. оптимальный план перевозок с указанием объемов поставок в каждой ячейке. В ячейке с целевой функцией запишутся совокупные затраты поставок.
4. Решение параметрической транспортной задачи
4.1 Постановка параметрической транспортной задачи
Имеется четыре поставщика однородного груза с объемами поставок 100, 70, 70, 20 т. и три потребителя с объемами потребления 120, 80, 60 т. Стоимость транспортных расходов задана матрицей
причем стоимость перевозки груза от четвертого поставщика до третьего потребителя изменяется в диапазоне 0≤k≤9.
Определить оптимальный план перевозок, обеспечивающий минимальные транспортные расходы.
Изобразим матричную запись задачи (табл. 4.1.1)
Табл. 4.1.1. Матричная запись задачи
| BjAi | B1 | B2 | B3 | |
| 120 | 80 | 60 | ||
| A1 | 100 | 2 | 4 | 2 |
| X11 | X12 | X13 | ||
| A2 | 70 | 5 | 5 | 6 |
| X21 | X22 | X23 | ||
| A3 | 70 | 4 | 7 | 3 |
| X31 | X32 | X33 | ||
| A4 | 20 | 6 | 8 | 1+k |
| X41 | X42 | X43 | ||
4.2 Математическая модель задачи
Целевая функция
.где Xij – объем поставок груза,
при ограничениях:
Xij≥0,
Подробные ограничения по потребностям и запасам каждого потребителя и поставщика соответственно отражены в Таблице 4.2.1.
Табл. 4.2.1. Ограничения по потребностям и запасам
| По потребностям | По запасам | ||
| B1 | X11+X21+X31+X41=120 | A1 | X11+X12+X13=100 |
| B2 | X12+X22+X32+X42=80 | A2 | X21+X22+X23=70 |
| B3 | X13+X23+X33+X43=60 | A3 | X31+X32+X33=70 |
| A4 | X41+X42+X43=70 | ||
4.3 Решение задачи аналитическим методом
Полагая k=0, по известному алгоритму составим опорное решение методом Фогеля. Полученный опорный план перевозок и алгоритм выполнения с нахождением минимальных разностей стоимостей перевозок (Cij) в каждом столбце и строке изображен на рисунке 4.3.1.
Рис. 4.3.1. Составление первого опорного решения задачи по методу Фогеля
Процесс выполнения получения опорного решения с последовательным назначением перевозок в ячейки: А4В3 - А3В3 - А3В1 - А1В1 - А1В2 - A2B2.
Проверка плана на вырожденность: m+n-1=6. План невырожденный.
Проверим опорное решение на оптимальность по методу потенциалов. Расчет потенциалов строк и столбцов для занятых из условия vi + uj = cijдля занятых клеток и проверка условия vi + uj ≤ cij для незанятых приведены в таблице 4.3.1.
Решение, полученное при k=0, является оптимальным для всех значений параметра k, удовлетворяющих условию
.Из условия для свободных клеток найдем:
∆13 = v3 + u1 - c'13 = -1 + 2 - 2 = -1
∆21 = v1 + u2 - c'21 = 0 + 3 - 5 = -2
∆23 = v3 + u2 - c'23 = -1 + 3 - 6 = -4
∆32 = v2 + u3 - c'32 = 2 + 4 - 7 = -1
∆41 = v1 + u4 - c'41 = 0 + 2+k - 6 = -4 + k
∆42 = v2 + u4 - c'42 = 2 + 2+k - 8 = -4 + k
Табл. 4.3.1. Проверка первого опорного решения на оптимальность методом потенциалов
| заполненные | незаполненные | ||||
| № | vi + uj = cij | значения | № | vi + uj ≤ cij | условие |
| А1В1 | v1+u1=2 | v1=0, u1=2 | А1В3 | v3+u1<=2 | соблюдается |
| А1В2 | v2+u1=4 | v2=2 | А2В1 | v1+u2<=5 | соблюдается |
| A2B2 | v2+u2=5 | u2=3 | А2В3 | v3+u2<=6 | соблюдается |
| A3B1 | v1+u3=4 | u3=4 | А3В2 | v2+u3<=7 | соблюдается |
| A3B3 | v3+u3=3 | v3= -1 | A4B1 | v1+u4<=6 | соблюдается |
| A4B3 | v3+u4=1+k | u4=2+k | A4B2 | v2+u4<=8 | соблюдается |
Определение значений k1 и k2: