Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата

3. Решение задачи.

Решение задачи состоит из двух этапов:
1. Определение допустимого решения.
2. Определение оптимального решения путём последовательного улучшения допустимого решения методом потенциалов.

Определение допустимого решения методом наименьшей стоимости.

На основе исходной таблицы построим вспомогательную таблицу (в верхнем правом углу каждой клетки будем записывать стоимости перевозки).
Введём в таблицу вспомогательную строку и столбец для записи остатков.

[pic]

Определим наименьшую стоимость перевозки:
X 14 = min (25, 30) = 25
X 32 = min (30, 10) = 10
X 34 = min (20, 5) = 5
X 31 = min (15, 15) = 15
X 21 = min (45, 15) = 15
X 23 = min (30, 30) = 30

Стоимость перевозки Z = 25*21 + 25*15 + 30*26 + 15*23 + 10*21 + 5*21 =
2340 усл. ед.

Последовательное улучшение допустимого решения методом потенциалов.

Выберем вспомагательные переменные U i и V j, обращающие в нули коэффициенты при базисных переменных, то есть

C ij – U i – V j = 0 (4)
Такие переменные называются потенциалами. Выполним следующие действия:
1. Для всех X ij > 0 (т. е. для всех занятых клеток) составим потенциальные уравнения:

C 14 – U 1 – V 4 = 0 21 – U 1 – V 4 = 0

C 21 – U 2 – V 1 = 0 25 – U 2 – V 1 = 0

C 23 – U 2 – V 3 = 0 26 – U 2 – V 3
= 0 (5)

C 31 – U 3 – V 1 = 0 23 – U 3 – V 1 = 0

C 32 – U 3 – V 2 = 0 21 – U 3 – V 2 = 0

C 34 – U 3 – V 4 = 0 21 – U 3 – V 4 = 0

Для определения m + n потенциалов необходимо, чтобы было m + n – 1 уравнений (где m – число строк, n – число столбцов). Тогда одному из потенциалов можно присвоить любое значение, например равное нулю, а значения других потенциалов получить, решая систему уравнений (5).

Для данной задачи m + n – 1 = 6 и число занятых клеток равно 6.

U 1 = -2

U 2 = 0

U 3 = -2

V 1 = 25 V 2 = 23 V 3 = 26 V 4 = 23

2. Решим систему уравнений 4, присвоив значение, равное нулю, наиболее часто встречающемуся неизвестному индексу: U 2 = 0, тогда

V 1 = 25; U 1 =
-2;

V 2 = 23; U 2 =
0;

Рекомендуем скачать другие рефераты по теме: сочинение по картине, антикризисное управление.





Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата