Методы оптимальных решений

 

Проверим данный план на оптимальность:

∆13= 19-8-10=1,

∆21= 19-7-12=0,

∆21 = 19-7-12=0,

∆22 = 20-8-12=0,

∆23 = 19-5-12=2,

∆25 =17-6-12=-1,

∆31 = 19-5-17=-3,

∆34 =15-2-17=-4,

∆35 = 17-5-17=-5,

∆41 =19-0-17=2,

∆43 =19-17-0=2,

∆44 =15-17-0=-2.

Данный план не оптимален, производим его корректировку:

Аi /Вj	20	60	42	13	65	Ui
78	9 20	10       - 10	8 -	5         13	7           + 35	10
2	7 -	8           -	5         2	3          -	6 -	14
90	5 -	3          50	2        40	2         -	5           -	17
30	0 -	0        + -	0 -	0 -	0         - 30	17
Vj	19	20	19	15	17

 

Проверим данный план на оптимальность:

∆13= 19-8-10=1,

∆21= 19-7-14=-2,

∆22 = 20-8-14= -2,

∆24 = 15-3-14= -2,

∆25 = 17-6-14= -3,

∆31 =19-5-17=-3,

∆34 = 15-2-17=-4,

∆35 =17-5-17=-5,

∆41 =19-0-17=2,

∆42 =20-0-17=3,

∆43 =19-17-0=2,

∆44 =15-17-0=-2.

Данный план не оптимален, производим его корректировку:

Аi /Вj	20	60	42	13	65	Ui
78	9       - 20	10       -	8 -	5         13	7           + 45	10
2	7 -	8           -	5         2	3          -	6 -	11
90	5 -	3          50	2        40	2         -	5           -	14
30	0       + -	0        10	0 -	0 -	0        - 20	17
Vj	19	17	16	15	17

 

Проверим данный план на оптимальность:

∆12= 17-10-10=-3,

∆13= 16-8-10=-2,

∆21 = 19-7-11=1,

∆22 = 17-8-11= -2,

∆24 = 15-3-11= 1,

∆25 =17-6-11=0,

∆31 = 19-5-14=0,

∆34 =15-2-14=-1,

∆35 =17-5-14=-2,

∆41 =19-0-17=2,

∆43 =16-17-0=-1,

∆44 =15-17-0=-2.

Данный план не оптимален, производим его корректировку:

Аi /Вj	20	60	42	13	65	Ui
78	9       -	10       -	8 -	5         - 13	7           + 65	10
2	7 -	8           -	5         2	3          -	6 -	11
90	5 -	3          - 50	2        40	2         + -	5           -	14
30	0       20	0        + 10	0 -	0 -	0          - 0	17
Vj	17	17	16	15	17

 

 

Проверим данный план на оптимальность:

∆11= 17-9-10=-2,

∆12= 17-10-10=-3,

∆13 = 16-8-10=-2,

∆21 = 17-7-11= -1,

∆22 = 17-8-11= -2,

∆24 =15-3-11=1,

∆25 = 17-6-11=0,

∆31 =17-5-14=-2,

∆34 =15-2-14=-1,

∆35 =16-0-17=-1,

∆43 =16-17-0=-1,

∆44 =15-17-0=-2.

Данный план не оптимален, производим его корректировку:

Аi /Вj	20	60	42	13	65	Ui
78	9       -	10       -	8 -	5         13	7           65	10
2	7 -	8           -	5         - 2	3          + -	6 -	10
90	5 -	3          50	2        + 40	2         - 0	5           -	13
30	0       20	0        10	0 -	0 -	0          -	16
Vj	16	16	15	15	17

 

∆11= 16-9-10=-3,

∆12= 16-10-10=-4,

∆13 = 15-8-10=-3,

∆21 = 16-7-10= -1,

∆22 = 16-8-10= -2,

∆24 =15-3-10=2,

∆25 = 17-6-10=1,

∆31 =16-5-13=-2,

∆35 =17-5-13=-1,

∆43 =15-16-0=-1,

∆44 =15-16-0=-1,

∆45 =17-16-0=1

Данный план не оптимален, производим его корректировку:

Аi /Вj	20	60	42	13	65	Ui
78	9       -	10       -	8 -	5         13	7           65	10
2	7 -	8           -	5         2	3          0	6 -	12
90	5 -	3          50	2        40	2         -	5           -	15
30	0       20	0        10	0 -	0 -	0          -	18
Vj	18	18	17	15	17

 

∆11= 18-9-10=-1,

∆12= 18-10-10=-2,

∆13 = 17-8-10=-1,

∆21 = 18-7-12= -1,

∆22 = 18-8-12= -2,

∆25 =17-6-12=-1,

∆31 =18-5-15=-2,

∆34= 15-2-15=-5,

∆35 =17-5-15=-3,

∆43 =17-18-0=-1,

∆44 =15-18-0=-3,

∆45 =17-18-0=-1

 

Все значения ∆ij для свободных клеток получились неположительными (∆ij ≤ 0). Следовательно, этот план является оптимальным.

Ответ:

                                  –    –     –     13   65                   

                     X *  =     –     –     2      0      –       ,  S* = 760.

                                  –      50  40      –    –  

                                 20    10      –    –    –    

Экономическая интерпретация оптимального плана поставок продукции

В результате решения транспортной задачи получен оптимальный план перевозок X *, в который входят:

1. от первого поставщика отправлены две поставки: четвертому потребителю – 13 единиц, пятому потребителю – 65 единиц;
2. поставкой от второго поставщика удовлетворяется спрос третьего потребителя в размере 2 единиц;
3. от третьего поставщика отправлены две поставки: второму потребителю – 50 единиц и третьему потребителю – 40 единиц
4. поставки x41 = 20 и х42=10 единиц размещается в строке фиктивного четвертого поставщика, т.е. этих поставок фактически не существует.

Транспортные затраты S* на этом плане равны  760 денежных единиц.