Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Транспортного типа.




 

На трех складах оптовой базы имеется груз в количествах соответственно 40, 80, 80 единиц. Этот груз необходимо перевезти в четыре магазина, каждый из которых заявил соответственно на 70, 20, 60 и 60 единиц. Стоимость доставки единицы груза (тарифы) из каждого склада Аi во все магазины Вj представляется матрицей:

 

5 4 2 1

C = 4 3 2 3 i

4 3 3 6

 
 


1 опорный план j

 
 


9 10 22 8 7 100

12 6 15 12 8 35

10 11 8 5 9 100

7 9 6 4 5 130


80 40 80 90 90

Составить оптимальный план перевозок грузов с минимальными транспортными затратами.

Решение:

1) Проверяем условия разрешимости задачи

3

å ai = 40+80+80=200

I=1

4

å bj =70+20+60+60=210

j=1

 

Суммарная потребность в грузе превышает его запасы на 210-200=10 единиц. Для получения закрытой модели введем дополнительный (фиктивный) склад А4 с запасом груза равным a4=10 единиц с нулевым тарифом перевозок.

1. Формирование первого опорного плана (10П) методом минимальной стоимости.

10П (1 опорный план)

Vi Uj V1 -16 V2-15 V3-O5 V4-12 Запасы аi
  Ai Bj B1 B2 B3 B4
U1 A1 0 40
U2 -24 A2 -3 3
U3 -53 A3 3 - 6
U4 13 A4 0 (10)
Потребности BJ

 

 

Расклад груза по клеткам:

1) Cmin=C14=1 сюда весь груз а1=40

Остальные клетки Аi обнуляем.

2) Следующая Cmin =C2/3=20 Сюда полностью потребность b3=60 Оставшиеся 80-60=20 запишем требующиеся b2=20

3)Окончательно формируем столбец В4, т.е. в клетку 44 вносим дефицит А4=10 и в клетку 34 недостающие А3=10.

4)Остался столбец В1 с клеткой А3, в которую записываем требующиеся в В1=70

Для оценки рентабельности полученного опорного плана перевозок. 10П применим метод “потенциалов” занятых клеток: разность “потенциалов” должна быть меньше расценки, т.е. V - U C или в свободных V -U -C 0.Так как при балансе – всё “закольцовано“, поэтому всё равно откуда начать проверки и заполнения всех потенциалов. Принято начинать с” северо-восточного узла “, задавший исходной любой цифрой, например, нулём.

 

1) U =0. Остальные находим из условия баланса V -U =C .

2) В строке U заполнения столбец V , поэтому V =C +U =1+0=1

3) Зная V можно определить в этом столбце U и U .

-U =C -V =6-1=5; U =-5

-U =C -V =0-1=-1; U =1

4) Чтобы перейти к следующей строке (U ) воспользуемся промежуточно-пустым известным столбцом (V ). C =3.

Т.о. -U =C -V =3-1=2; U =-2

5) Теперь, зная U , определим в этой строке V и V .

V =C +U =3-2=1

V =C +U =2-2=0

6) Зная U =-5(см.п3) определим для занятой клетки 31 (С =4) значение V =C +U =4-5=-1. Определяем резервы в незанятых клетках .

 

Баланс д.б. <0 и резерв там, где он >0 (!)

 

7) Для клетки 11.

V -U -C =-1-0-5= -6<0

8) Для клетки 12.

V -U -C =1-0-4=-3<0

9) Для клетки 13

V3 - U1 – C13 =0-0–2=-2<0

10) Для клетки 21

V1 – U2 – C21 =-1+2-4=-3<0

11) Для клетки 24

V4 – U2 – C24 =1+2-3=0

12) Для клетки 32

V2 – U3 – C32 =1+5-3=+3>0 (!!!)

13) Для клетки 33

V3 – U3 – C33 =0+5-3=+2>0

14) Для клетки 41

V1 – U4 – C41 =-1-1-0=-2<0

15) Для клетки 42

V2– U4 – C42 =1-1-0=0

16) Для клетки 43

V3 – U4 – C43 = 0-1-0=-1<0

Получаем резервы(>0) в клетках 32 и 33

(п.п.12 и 13).Однако больше в клетке 32

 

Формирование второго опорного плана (20П)

 

Осуществляем перемещением грузов по следующему правилу:

Строим исходный многоугольник, в одной из вершин которого стоит клетка 32.Против нее ставим +, что значит перенесение сюда груза. Затем по периметру многоугольника поочередно в углах ставим – и +, считая начало + с клетки 32.В соответствии со знаками перемещаем грузы, сохраняя балансы по строчкам и столбцам.

 

1ОП 2ОП

 


 

  20П (2опорный план)  
Vj Ui     V126   V213   V304   V411   Запасы   ai
  Bj Ai   B1   B2   B3   B4
U1 01   A1  
U2 -22   A2 4 3 10 - 3  
U3 -25 A3 -4 3  
U4 17   A4 0 -0  
Потребности bj          
               

 

Повторяем туже работу с 20П , что и с 10П (можно бы было работать только с изменными клетками 22, 24, 32 и 34, а так же с теми потенциалами, которые от них зависят через Cij, но лучше – слошь, пусть с повторами, чтобы не пропустить):

 

Занятые клетки

 

1) Кл. 14 неизменно V4=1

2) Кл. 24 - U2 = C24 – V4 =3 – 1 = 2; U2= -2

3) Кл. 22 V2 = C22 + U2 = 3 – 2 = 1

4) Кл. 23 неизменно V3 = 0

5)Кл.32 → -U3=C32-V2=3-1=2; U3=-2 (было -5)

6)Кл.31 → V1=C31+U3=4-2=2; V1=2 (было -1)

7)Кл.44 → неизменно U4=1

Резервы свободных:

8)Кл.11 → V1 -U1-C11 =2-0-5=-3<0

9)Кл.12 → V2 -U1-C12 =1-0-4=-3<0

10)Кл.13 →V3 -U1-C13 =0-0-2=-2<0

11)Кл.21 → V1 –U2-C21 =2+2-4=0

12)Кл.33 → V3 –U3-C33 =0+2-3=-1<0

13)Кл.34 → V4 –U3-C34 =1+2-6=-3<0

14)Кл.41 → V1 –U4-C41 =2-1-0= 1>0

15)Кл.42 → V2 –U4-C42 =1-1-0=0

16)Кл.43 → V3 –U4-C43 =0-1-0=-1<0

Т.о. исходный многоугольник с исходным углом в Кл.41 и знаком , а чередование знаков должно замкнуться, то углов д.б. четное количество.

 

3)Формирование третьего опорного плана (30П)

Для занятых клеток:

1) Кл.14 → неизменно V4 =1

2) Кл.24 → -U2=C24 – V4=-3-1=2; U2=-2

3) Кл.23 →V3 = C23 +U2- =2-2=0; V3=0

 

      зоп (3опорный план)      
U1 Vj   V1 15 V2 O5 V3 O3 V4 14 Запасы
  Ai Bj В1 В2 В3 В4 ai
U1 O   А1 0 40  
U2 -22   А2 -3 3  
U3 -34 А3 -4 3  
U4 17   А4 0 10   -0  
Потребности  
bj

 

4) Кл.33→ -U3=C33-V3=3-0=3; U3= -3

5) Кл.31→ V1=C31=U3=4-3=1; V1=1

6) Кл.32→ V2=C32+U3=3-3=0; V2=0

7) Кл.41→-U4=C41-V1=0-1= -1; U4=1

Для незанятых:

8) Кл.11→V1-U1-C11=1-0-5= -4<0

9) Кл.12→V2-U1-C12=0-0-4= -4<0

10) Кл.13→V3-U1-C13=0-0-2= -2<0

11) Кл.21→V1-U2-C21=1+2-4= -1<0

12) Кл.22→V2-U2-C22=0+2-3= -1<0

13) Кл.33→V3-U3-C33=0+3-3=0

14) Кл.34→V4-U3-C34=1+3-6= -2<0

15) Кл.42→V2-U4-C42=0-1-0= -1<0

16) Кл.43→V3-U4-C43=0-1-0= -1<0

17) Кл.44→V4-U4-C44=1-1-0=0

ЗОП является оптимальным, т.к. все оценки резервов £ 0

Анализ работы с опорными планами:

1ОП Y(x)=

 

2ОП Y(x)=

 

3ОП Y(x)=

 

Анализ полученного ЗОП.

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

1)С I склада А1 весь груз 40ед. направить в IV магазин B4

2)Cо II склада А2 60 ед. отвезти в III магазин и 20 ед. отвезти в IV магазин В4

3)С III склада А3 60 ед. отвезти в I магазин В1 и 20 ед. отвезти во II магазин В2

4)Весь груз будет развезен, но I магазин недополучит 10 ед. (дефицит).

 


Поделиться:

Дата добавления: 2015-01-05; просмотров: 133; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты