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

Условие задачи.

Требуется перевезти товары с трёх складов в четыре магазина. Дан­ные о наличии товаров на складе, спрос на него в магазинах, а также стои­мости перевозки единицы груза между складами и магазинами приведены в таблице. Составить план перевозки, чтобы затраты были минимальными.

 

 

Построение математической модели.

Пусть X ij – количество деталей, отправленных со склада i в магазин j, а C ij – стоимость перевозки одной детали со склада i в магазин j. Очевидно, что X ij > 0 и C ij > 0.

В силу ограничений на возможность поставки товара со склада и спрос в магазинах величина X ij должна удовлетворять следующим условиям:

 

X 11 + X 12 + X 13 + X 14 = 25

X 21 + X 22 + X 23 + X 24 = 45                      (1)

X 31 + X 32 + X 33 + X 34 = 30

 

X 11 + X 21 + X 31 = 30

X 12 + X 22 + X 32 = 10                                  (2)

X 13 + X 23 + X 33 = 30

X 14 + X 24 + X 34 = 30

 

Общая стоимость перевозок равна:

Z = C ij X ij = 21* X 11 + 36* X 12 + 28* X 13 + 21* X 14 + 25* X 21 +

 

35* X 22 + 26* X 23 + 25* X 24 + 23* X 31 + 21* X 32 + 27* X 33 + 21* X 34,        

т.е. Z = C ij X ij.                                 (3)

Необходимо определить такие неотрицательные значения переменных X ij, которые удовлетворяют ограничениям (1) и (2) и обращают в минимум целевую функцию Z (3). В такой постановке задача является транспортной задачей линейного программирования.

Необходимым и достаточным условием разрешимости транспортной задачи является условие баланса:

 

                                S i = M j   

Где,  S i = X ij – cуммарное количество деталей на складах;

 

M j = X ij – суммарное количество деталей, требуемое в

 

магазинах.

В данной задаче S i = M j = 100,

 

Следовательно, задача с балансом.

 

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

 

Решение задачи состоит из двух этапов:

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

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

 

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

На основе исходной таблицы построим вспомогательную таблицу (в

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

 

Определим наименьшую стоимость перевозки:

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;

                                      V 3 = 26;            U 3 = -2.

                                      V 4 = 23;

Занесём данные в таблицу выше.

3. Для всех небазисных переменных, т. е. для X ij = 0 (для пустых клеток), определим невязки:

G ij = C ij – S ij,   где S ij = U i + V j.

 

 G 11 = C 11 – U 1 – V 1;           G 11 = 27 – (-2) – 25 = 4;

G 12 = C 12 – U 1 – V 2;           G 12 = 36 – (-2) – 23 = 15;

             G 13 = C 13 – U 1 – V 3;           G 13 = 28 – (-2) – 26 = 4;       (6)

             G 22 = C 22 – U 2 – V 2;           G 22 =35 – 0 – 23 = 12;

             G 24 = C 24 – U 2 – V 4;           G 24 = 25 – 0 – 23 = 2;

  G 33 = C 33 – U 3 – V 3;           G 33 = 27 – (-2) – 26 = 3.

 

Отрицательных невязок нет, значит найденный план (см. таблицу выше) оптимален и значение целевой функции является минимальным.

Таким образом, минимальная стоимость перевозок Z равна 2340 усл. ед. и достигается при объёмах перевозок:

 

X 14 = 25, X 21 = 15, X 23 = 30, X 31 = 15, X 32 = 10, X 34 = 5.

 

ЗАДАЧА 3

Условие задачи.

Фирма должна наладить перевозку продуктов с базы в 7 магазинов. Сеть дорог, связывающая базу и магазины между собой, а также длины участков дороги между каждой парой соседних пунктов представлены на рисунке.

Определить кратчайшие пути от базы до каждого из магазинов.

 

                                     Х 4

 

               Х 1                Х 7                                   Х 5                                                                                                                            

 

                             Х 3

    Х 2

                                        

                                                                Х 8 

 

                                         

                                     Х 6