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

 

Получим потенциальные уравнения (19):

С21-U2-V1=0	13-U2-V1=0
С31-U3-V1=0	10-U3-V1=0
С12-U1-V2=0	14-U1-V2=0
С13-U1-V3=0	11-U1-V3=0
С33-U3-V3=0	9-U3-V3=0
С24-U2-V4=0	12-U2-V4=0

 

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

U₁  = -1 V₁ = 13

U₂  = 0 V₂ = 15

U₃ = 3  V₃ = 12

V₄ = 12

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

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

Gij = Cij - Sij, где Sij = Ui + Vj              (20)

 

G11=C11-U1-V1	G11=16+1-13=4
G22=C22-U2-V2	G22=13,5-0-15=-1,5
G32=C32-U3-V2	G32=12,5+3-15=0,5
G23=C23-U2-V3	G23=15-0-15=3
G14=C14-U1-V4	G14=12,5+1-12=1,5
G34=C34-U3-V4	G34=14+3-12=5

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

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

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

 

 

 

Табл. 16

	Магазины
Склады	К1=50	К2 =30	К3 = 45	К4 = 40
S1= 50	16	14   (-) 30	11    (+) 20	12,5
S2 = 55	13     (-) 15	13,5     (+)	15	12 40
S3 = 60	10     (+)     35	12,5	9           (-) 25	14

 

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

Табл. 17

	Магазины
Склады	К1=50	К2 =30	К3 = 45	К4 = 40
S1= 50	16	14 15	11 35	12,5
S2 = 55	13	13,5 15	15	12 40
S3 = 60	10      50	12,5	9       10	14

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

Z= 50*10 + 15*14 + 15*13.5 + 35*11 + 10*9 + 40*12 = 1867,5.

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

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

10-U3-V1=0

14-U1-V2=0

13,5-U2-V2=0

11-U1-V3=0

9-U3-V3=0

12-U2-V4=0

 

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

U₁  = 0,5 V₁ = 11,5

U₂  = 0 V₂ = 13,5

U₃ = -1,5 V₃ = 10,5

V₄ = 12

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

Табл. 18

	Магазины
Склады	К1=50	К2 =30	К3 = 45	К4 = 40	Ui
S1= 50	16	14 15	11 35	12,5	U1 =0,5
S2 = 55	13	13,5 15	15	12 40	U2 =0
S3 = 60	10      50	12,5	9       10	14	U3 =-1,5
Vj	V1 =11,5	V2 =13,5	V3 =10,5	V4 =12

 

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

G11=16-0,5-11,5=4

G21=13-0-11,5=1,5

G32=12,5+1,5+-13,5=0,5

G23=15-0-10,5=4,5

G14=12,5-0,5-12=0

G34=14+1,5-12=3,5

 

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

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

, , , , ,

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

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

	A	B	C	D	E	F
1		ИСХОДНЫЕ ДАННЫЕ
2			Недельные портебности завода
3	Max отгрузка маш/нед.		Завод 1	Завод 2	Завод 3	Завод 4
4			50	30	45	40
5			Стоимости перевозки ед груза
6	Поставщик 1	50	1600	1400	1100	1250
7	Поставщик 2	55	1300	1350	1500	1200
8	Поставщик 3	60	1000	1250	900	1400
9
10			Требуется Получить
11	Требуется поставить		Завод 1	Завод 2	Завод 3	Завод 4
12			50	30	45	40
13	Поставщик 1	50	1	1	1	1
14	Поставщик 2	55	1	1	1	1
15	Поставщик 3	60	1	1	1	1
16	Стоимость перевозки	186 750

Рис. 1

	ИСХОДНЫЕ ДАННЫЕ
		Недельные портебности завода
Max отгрузка маш/нед.		Завод 1	Завод 2	Завод 3	Завод 4
		50	30	45	40
		Стоимости перевозки ед груза
Поставщик 1	50	1600	1400	1100	1250
Поставщик 2	55	1300	1350	1500	1200
Поставщик 3	60	1000	1250	900	1400
		Требуется Получить
Требуется поставить		Завод 1	Завод 2	Завод 3	Завод 4
		=СУММ(C13:C15)	=СУММ(D13:D15)	=СУММ(E13:E15)	=СУММ(F13:F15)
Поставщик 1	=СУММ(C13:F13)	1	1	1	1
Поставщик 2	=СУММ(C14:F14)	1	1	1	1
Поставщик 3	=СУММ(C15:F15)	1	1	1	1
Стоимость перевозки	=СУММПРОИЗВ(C6:F8;C13:F15)

Рис. 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 минимальное значение целевой функции.

 

	ИСХОДНЫЕ ДАННЫЕ
		Недельные портебности завода
Max отгрузка маш/нед.		Завод 1	Завод 2	Завод 3	Завод 4
		50	30	45	40
		Стоимости перевозки ед груза
Поставщик 1	50	1600	1400	1100	1250
Поставщик 2	55	1300	1350	1500	1200
Поставщик 3	60	1000	1250	900	1400
		Требуется Получить
Требуется поставить		Завод 1	Завод 2	Завод 3	Завод 4
		50	30	45	40
Поставщик 1	50	0	15	35	0
Поставщик 2	55	0	15	0	40
Поставщик 3	60	50	0	10	0
Стоимость перевозки	186 750