Контрольная работа по «Логистике»

Задание№1.3

Предприятию нужно перевести  со склада по железной дороге изделие  трех различных видов: Изделий I-го вида не более р₁, Изделий II-го вида не более р₂, Изделий III-го вида не более р₃.

Подразделение железной дороги может для этой перевозки выделить специально оборудованные вагоны двух типов А и В. Для полной загрузки вагона следует помещать в него изделия всех трех видов. При этом вагон типа А входят b₁ изделий I-го вида, b₂ изделий II-го вида, b₃ изделий III-го вида.

Экономия от перевозки  груза в вагоне типа А составляет α руб., в вагоне типа В-β руб.

Сколько вагонов каждого  типа следует выделить для перевозки, чтобы суммарная экономия от перевозки  груза была наибольшей?

Задачу решить симплекс методом  путем преобразования симплекс-таблиц т геометрическим методом.

Сведем условие задачи а таблицу:

Вид изделия	Тип вагона		Вместимость вагона
	А	В
I	1	4	640
II	5	2	800
III	3	5	860
Экономия, руб	20	13

Составим математическую модель задачи.

Обозначим х₁-колличество вагонов типа А; х₂-колличество вагонов типа В. Тогда ограничения в по вместимости дают ограничения на х₁ и х₂ вида:

   1х₁+4х₂≤640

  5х₁+2х₂≤800

  3х₁+5х₂≤860

  Х₁≥0

  Х₂≥0

Экономия F предприятия при выделении вагонов х₁, х₂ равна

 F=20х₁+13х₂ max.

1. Решим задачу симплекс методом.

Приведем стандартную  задачу к каноническому виду.

Введем дополнительные переменные х₃,х₄,х₅, равные разностям правых и левых частей неравенств. Получим задачу:

1х₁+4х₂+х₃=640

5х₁+2х₂+х₄=800

3х₁+5х₂+х₅=860

Х_i≥0

F=20х₁+13х₂+max.

Система уравнений приведена  к единичному базису : х₃, х₄, х₅-базисные переменные, х₁, х₂-свободные.

Составим исходную симплекс-таблицу:

 

Базисные неизвестные	Х1	Х2	Х3	Х4	Х5	Свободные члены	Симплексное отношение
Х3	1	4	1	0	0	640	640/1=640
Х4	5	2	0	1	0	800	800/5=160
Х5	3	5	0	0	1	860	860/3=286,66
F	-20	-13	0	0	0	0

                                                                                                                                

  Первый опорный план: (0,0,800,860) не оптимальный, так как в F –строке есть отрицательный элемент.

Выбираем разрешающий  элемент 5( элемент второй строки первого  столбца) и строим вторую симплекс –таблицу:

Базисные неизвестные	Х1	Х2	Х3	Х4	Х5	Свободные члены	Симплекс отношение
Х3	0	3.6	1	-0.2	0	480	133.33
Х1	1	0.4	0	0.2	0	160	400
Х5	0	3.8	0	-0.6	1	380	100
F	0	-5	0	4	0	3200

 Второй опорный план: (160,0,480,0,380) не оптимальный, так  как в F- строке есть отрицательный элемент.

Выбираем разрешающий  элемент 3,8 (элемент третий строки второго  столбца) и строим третью симплекс-таблицу:

 

 

Базисные неизвестные	Х1	Х2	Х3	Х4	Х5	Свободные члены
Х3	0	0	1	0,368	-0,947	120
Х1	1	0	0	0.263	-0,105	120
Х2	0	1	0	-0.158	0,263	100
F	0	0	0	3,211	1,316	3700

 Этой таблице соответствует  опорное решение: (120,100,120,0,0). Оно является оптимальным, так как все коэффициенты F- строки в таблице неотрицательны. Максимальное значение целевой функции F_max=3700 руб. Оно достигается при х₁=120, х₂=100.

2. Решим задачу геометрическим методом.

Для каждого ограничения  строим граничную прямую, соответствующую равенству:

L1:х₁+4х₂=640; L2: 5х₁+2х₂=800; L3: 3х₁+5х₂=860;  L4:х₁=0;  L5: х₂=0.

         L4

    600

    550

    500

    450

    400

    350    L2

    300

    250

    200

    150B  C                      10 grad(F)

    100 D

      50  A                            L3                                       L1                        

       0                     E                                                                                        L5 X1

 Область допустимых значений х_{1 ,}х₂-многоугольник ABCDE. Вектор grad(F)=, перпендикулярный линиям уровня F=20х₁+13х₂=const слишком мал в выбранном масштабе, поэтому строим вектор                         10 grad(F)=  . перемещая линию уровня (обозначенную на графике пунктиром) F=const в направлении вектора 10 grad(F) определим точку «выхода» из области, в которой функция Fпринимает наибольшее значение. Это точка D, лежащая на пересечении прямых L2 и L3. Определим ее кординаты, решая систему уравнений:

  5х₁+2х₂=800

  3х₁+5х₂=860

Откуда D(120,100). Вычислим значение функции Fв точке D: F_max=20*120+13*100=3700.

Вывод: предприятию выгодно  выделить для перевозки 120 вагонов  типа А, и 100 вагонов типа В. При этом наибольшая экономия от перевозки груза состоит 3700 руб.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание № 2.3

Имеется три пункта постановки однородного груза А₁, А₂, А₃ и пять пунктов потребления груза В₁,В₂, В₃, В₄, В₅. На пунктах А₁, А₂, А₃ находится груз соответственно в количестве а₁, а₂, а₃ тонн. В пунктах В₁, В₂, В₃, В₄, В₅ требуется доставить соответственно b₁,b₂,b₃,b₄,b₅ тонн груза. Затраты на перевозку 1т. груза между пунктами поставки и пунктами потребления приведены в матрице С (в тыс. руб.).

Необходимо найти такой план закрепления  потребителей за поставщиками, чтобы  общие затраты по перевозки были минимальными

                                                    12  8  21  10  15

                                        С =       13  4  15  13  21

                                                     19  16  26  17  20

 

а₁=250, а₂=200, а₃=150.

b₁=180, b₂=120, b₃=90, b₄=105, b₅=105.

Условие задачи запишем в  виде таблицы:

Поставщики	Потребители					Запасы
	В1	В2	В3	В4	В5
А1	12	8	21	10	15	250
А2	13	4	15	13	21	200
А3	19	16	26	17	20	150
Потребности	180	120	90	105	105

 

Данная транспортная задача является задачей закрытого типа, поскольку общее количество груза _i=600 совпадает с общими потребностями потребителей _j=600.

Найдем первоначальный опорных  план методом наименьшей стоимости  перевозок.

 

 

Поставщики	Потребители					Запасы
	В1	В2	В3	В4	В5
А1	12   145	8	21	10          105	15	250
А2	- 13 35	4 120	+15            45	13	21	200
А3	+ 19	16	-26 45	17	20     105	150
Потребности	180	120	90	105	105

 

Проверим, число заполненных  клеток должно быть равно m+n-1=3+5-1=7. Это условие выполняется.

Стоимость перевозок для  данного опорного плана составит:

F145*12+105*10+35*13+120*4+45*15+45*26+105*20=7670

Проверим первоначальный опорный план, на оптимальность метода потенциалов. Для этого для каждого из пунктов отправления α_i иβ_j. Эти числа находятся из уравнений α_i+β_j=с_ij, где с_ij- тарифы, стоящие в заполненных клетках таблицы.

Если первоначальный опорный план является оптимальным, то для каждой незанятой клетки должно выполнятся условие ∆_ij=c_ij –α_i –β_j ≥0. Если хотя бы одна незанятая клетка не удовлетворяет этому условию, то опорный план не является оптимальным. Поэтому для каждой свободной клетки найдем ∆_ij. Полагаем α₁=0 и определим остальные потенциалы.

  α₁+β₁=12                                                        α₁=0        β₁=12

  α₁+β₄=10                                                        α₂=1        β₂=3

  α₂+β₁=13                                                        α₃=12      β₃=14

  α₂+β₂=4                     если α₁=0, тогда                         β₄=10

  α₂+β₃=15                                                                        β₅=8

  α₃+β₃=26                                                      

  α₃+β₅=20                                                      

 

вычислим оценки ∆_ij  для получения клеток:

∆₁₂=8-0-3=5; ∆₁₃=7; ∆₁₅=7; ∆₂₄=2; ∆₂₅ =12;∆₃₁ =-5; ∆₃₂ =1; ∆₃₄=-5.

поскольку имеются клетки с ∆ij < 0, то полученный опорный план не является оптимальным. Улучшим первоначальный опорный план методом циклов. Для свободной клетки с отрицательной оценкой строим цикл. Делаем перерасчет по циклу. Пометим вершины цикла знаками «+» и «-» поочередно, начиная с «+» в свободной клетке. Минимальное содержание клеток, помеченных знаком «-», равно 35. Из всех клеток, помеченных знаком «-», вычтем по 35; во все клетки, помеченные знаком «+», добавим по 35. При этом баланс по строкам и столбцам таблицы сохранен. В результате получим новый опорный план.

 

Поставщики	Потребители					Запасы
	В1	В2	В3	В4	В5
А1	12   145	8	21	10          105	15	250
А2	13	4 120	15            80	13	21	200
А3	19 35	16	26 10	17	20     105	150
Потребности	180	120	90	105	105

 

Стоимость перевозок для  данного опорного плана составит:

F=145*12+105*10+120*4+80*15+35*19+10*26+105*20=7495

Определяем потенциалы:

  α₁+β₁=12                                                        α₁=0       β₁=12

  α₁+β₄=10                                                        α₂=-4        β₂=8

  α₂+β₂=4                                                          α₃=7         β₃=19

  α₂+β₃=15                     если α₁=0, тогда                       β₄=10

  α₃+β₁=19                                                                        β₅=13

  α₃+β₃=26                                                      

  α₃+β₅=20                                                      

вычислим оценки ∆_ij для свободных клеток: