Экономико-математические методы и модели в логистики

 

2. Решим систему уравнений (5), присвоив значение, равное нулю, потенциалу U₁. Если U₁ = 0, тогда:

U₁  = 0 

V₁ = 11

U₂  = 0 

V₂ = 8

U₃ = -2  

V₃ = 10

V₄ = 9

Занесем их в столбцы U_i и V_j табл. 15.

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

 

G_ij = C_ij - S_ij, где S_ij = U_i + V_j              (6)

G11=C11-U1-V1	G11=10,5-0-11=-0,5
G12=C12-U1-V2	G12=12-0-8=4
G23=C23-U2-V3	G23=13-0-10=3
G24=C24-U2-V4	G24=9,5-0-9=0,5
G31=C31-U3-V1	G31=9,5+2-11=0,5
G34=C34-U3-V4	G34=11+2-9=4

 

Имеем одну отрицательную  невязки G₁₁ = -0,5, поэтому найденный план не оптимален.

4. Найдем новое базисное решение.

Клетку (1,1), которая соответствует  отрицательная невязка, равная -0,5, отметим  знаком (+) (табл. 16). Одновременно установим  равновесие по всему многоугольнику: если в клетку (1,1) поставили (+), то в  клетку (1,3) поставим (-), если в клетку (3,3) - (+), в клетку (3,2) - (-), если в клетку (2,2) - (+), в клетку (2,1) - (-).

Табл. 16

	Магазины
Склады	К1=50	К2 =40	К3 = 45	К4 = 60
S1= 65	10,5 (+)	12	10     (-) 5	9 60
S2 = 60	11    (-) 50	8   (+) 10	13	9,5
S3 = 70	9,5	6    (-) 30	8      (+) 40	11

 

 

 

 

 

Наименьшим из чисел, находящихся  в клетках со знаком (-), является содержимое клетки (1,3), где Х₁₃ = 5, поэтому во всех клетках, помеченных знаком (+), надо увеличить перевозки на 5, а во всех клеток, помеченных знаком (-) уменьшить перевозки на 5 (табл. 17). Переменная Х₁₃ становится равной нулю, т.е. выводится из базиса.

 

 

 

Табл. 17

	Магазины
Склады	К1=50	К2 =40	К3 = 45	К4 = 60
S1= 65	10,5 5	12	10	9 60
S2 = 60	11 45	8 15	13	9,5
S3 = 70	9,5	6 25	8 45	11

 

Получим план перевозок (см. табл. 17), при котором значение целевой  функции равно:

Z= 10,5*5 + 9*60 + 11*45 + 8*15 + 6*25 + 8*45 =1717,5тыс.у.е.

Повторим действия, описанные  в пунктах 1- 4.

1. Для всех xij > 0 (см. табл. 17) составим потенциальные уравнения: (7)

10,5-U1-V1=0

9-U1-V4=0

11-U2-V1=0

8-U2-V2=0

6-U3-V2=0

8-U3-V3=0

 

2. Определим неизвестные потенциалы (7), присвоив значение, равное нулю, например, наиболее часто встречающемуся неизвестному индексу: U₁ = 0, тогда

U₁  = 0 

V₁ = 10,5

U₂  = 0,5

V₂ = 7,5

U₃ = -1,5 

V₃ = 9,5

V₄ = 9

Занесем вычисленные потенциалы в табл. 18

Табл. 18

	Магазины
Склады	К1=50	К2 =40	К3 = 45	К4 = 60	Ui
S1= 65	10,5 5	12	10	9 60	U1 =0
S2 = 60	11 45	8 15	13	9,5	U2 =0,5
S3 = 70	9,5	6 25	8       45	11	U3 =-1,5
Vj	V1 =10,5	V2 =7,5	V3 =9,5	V4 =9

 

Для всех небазисных клеток определим невязки:

G12=12-0-7,5=4,5

G13=10-0-9,5=0,5

G23=13-0,5-9,5=3

G24=9,5-0,5-9=0

G31=9,5+1,5-10,5=0,5

G34=11+1,5-9=3,5

 

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

Таким образом, минимальная  стоимость перевозок (с учетом принятой единицы измерения, равной 100 у.е.) Z=171750 у.е. и достигается она при значениях перевозок:

, , , , ,

 

 

 

РЕШЕНИЕ ЗАДАЧИ В EXCEL

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

Рис. 1

Рис. 1-а

Для работы в диалоговом окне Поиск решения следует выполнить:

1. Команду: Сервис - Поиск решения. На экране появится диалоговое окно Поиск решения.
2. В поле Установить целевую ячейку ввести адрес $В$16.

 

3. Выбрать направление изменения целевой функции: установить переключатель в положение Минимальному значению.
4. В поле Изменяя ячейки ввести адрес блока ячеек SC$13: $F$15.
5. Для ввода ограничений нажать кнопку Добавить. В диалоговом окне Добавление ограничения ввести: в левое поле - левую часть ограничения $В$13:$В$15, из раскрывающегося списка выбрать знак ограничения =, в правое поле - правую часть ограничения $В$6:$В$8; щелкнуть по кнопке Добавить; в диалоговое окно Добавление ограничения аналогично ввести второе ограничение $C$12:$F$12 = $C$4:$F$4; нажать кнопку ОК. На экране появится диалоговое окно Поиск решения с введенными ограничениями (рис. 2).

Рис. 2

 

6. Щелкнуть по кнопке Параметры. Появится диалоговое окно

Рис. 3

7. Оставить, предлагаемые по умолчанию, Максимальное время решения задачи (100 с) и Предельное число итераций (100).
8. Установить флажки Линейная модель и Неотрицательные значения.
9. Нажать кнопку ОК. Появится диалоговое окно Поиск решения.
10. Щелкните по кнопке Выполнить. Появится диалоговое окно Результаты поиска решения. Решение найдено.
11. В окне Результаты поиска решения в поле Тип отчета выделите названия всех трех отчетов: Результаты, Устойчивость, Пределы Появятся три новых листа с именами всех отчетов.
12. Нажать кнопку ОК. На экране появится исходная таблица (рис. 3), где в блоке ячеек C13:F15 находятся значения искомых переменных: Ху, а в ячейке В16 минимальное значение целевой функции.

Рис. 4

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

, , , , ,

Как видно, вычисления, выполненные  при ручном счете и средствами Excel, совпадают.

Определение разницы  между наилучшим и наихудшим  планами перевозок

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

Чтобы определить, насколько  полученный при оптимизации план лучше, чем другие возможные планы, надо найти план, приносящий максимум издержек. Для этого следует запустить Поиск решения еще раз и поменять цель поиска на максимум - выбрать направление изменения целевой функции: установить переключатель в положение Максимальному значению (рис. 5). Получим решение (рис. 6)

Рис.5

Рис. 6

В полученном решении суммарная  стоимость перевозок возрастет  на 53000 (у.е.). Таким образом, наихудший  план отличается от наилучшего на 30,8%.

ОТВЕТЫ НА ВОПРОСЫ.

а) Чтобы определить, имеет ли задача альтернативное решение, следует выполнить повторный поиск. Повторный поиск показал тот же план перевозок. По-видимому, других решений, приводящих к той же самой стоимости перевозок нет.

б) Определить, каким будет план перевозок, если Поставщик 2 сможет поставлять на 8 машин продукции больше, чем планировал.

Вычислим:

суммарное количество продукции  на складах:   (4)

 

суммарное количество продукции, заказанное клиентами:

 

Тогда  (5)

 

          И транспортная задача является открытой (без баланса). В этом случае задачу следует сбалансировать.

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

Затем решим задачу, используя Поиск решения (рис. 8).

Рис. 8

Решение задачи изменилось: минимальная стоимость перевозок  стала равной 162950 (у.е.)

в) Определить, каким будет  план перевозок, если Поставщик 2 не сможет поставлять на 8 машин продукции больше, чем планировал, а Поставщик 3 сможет поставлять на 6 машин меньше.

Вычислим:

суммарное количество продукции  на складах:  

 

суммарное количество продукции, заказанное клиентами:

 

Тогда

 

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

Так  как , в таблицу транспортных издержек и в таблицу

перевозок надо добавить по одной лишней строке, как будто  появился еще один фиктивный поставщик, заказ которого равнялся разности между  суммой всех заявок и суммой всех запасов, а издержки перевозок грузов от него к любому поставщику равны нулю (рис. 9).

 

Рис. 9

Рис.10

 Решение задачи изменилось: минимальная стоимость перевозок  в этом случае будет равной 203200 (у.е.), а перевозка от фиктивного  поставщика х₄₃ = 6. Недополучит 6 машин продукции Завод 3.

 

 

 

 

ЗАДАЧА 2

УСЛОВИЕ ЗАДАЧИ (Вариант 6)

 

Менеджеру транспортного  отдела поручено составить план перевозок  продукции со склада фирмы в четыре торговые точки области, обеспечивающий минимальные издержки на перевозки (известно, что издержки на перевозки пропорциональны длине пути).

Расстояния от базы до каждого  магазина и между магазинами приводятся в таб. 1:

Табл. 1

	база	Т2	Т3	Т4	Т5	Т6
база	-	15	3	27	9	11
Т2	15	-	10	12	21	14
Т3	3	10	-	15	18	14
Т4	27	12	15	-	24	20
Т5	9	21	18	21	-	26
Т6	11	14	14	20	26	-