Курсовая работа: Постановка и решение транспортной параметрической задачи

x_m2

…

c_mj

x_mj

...

c_mn

x_mn

Математическая модель транспортной задачи имеет вид

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

Оптимальным решением задачи является матрица

удовлетворяющая системе ограничений и доставляющая минимум целевой функции [1].

2. Аналитический метод решения параметрической транспортной задачи

2.1 Методика нахождения исходного опорного решения задачи об оптимальных перевозках методом Фогеля

Алгоритм выполнения метода.

1. В каждой строке и каждом столбце распределительной таблицы вычислить разности между всеми парами элементов (C_ij ) и выбрать минимальную.

2. Среди всех выбранных минимальных разностей C_ij выбрать максимальное значение и выделить соответствующий столбец (строку).

3. В выбранном столбце (строке) найти минимальное значение C_ij и назначить необходимую перевозку, ориентируясь на наличие запасов (a_i ) данного поставщика (A_ij ) и потребностей (b_j ) данного потребителя (B_ij ).

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

Процесс распределения продолжают до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены. При распределении грузов может оказаться, что количество занятых клеток меньше, чем m+n-1. В этом случае задача считается вырожденной. В этом случае недостающее число занятых клеток заполняется нулевыми поставками, которые называются условно занятыми.

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≤φ где δ и φ – произвольные действительные числа, найти такие значения которые обращают в минимум функцию