Транспортная несбалансированная задача

Самостоятельная работа №1

Задача формализации

Требуется формализовать приведенную ниже задачу.

Производственная мощность цеха сборки некоторого изделия составляет 120 шт. типа и 360 шт. типа в смену. Технический контроль может пропустить в сутки не более 200 изделий того и другого типа. Доход от реализации изделий в 4 раза выше, чем от реализации . Определить план выпуска изделий, при котором будет обеспечена наибольшая прибыль.

Решение:

у=Р1+4Р2 max

 

P1<=120

P2<=360

P1+P2<=200

 

Самостоятельная работа №2

Графическое решение ЗЛП

Найти графическим методом решение следующей ЗЛП:

f = 3x₁+x_2, f min

2x₁+x₂ <=16 (1) x₁ + 2x₂>=8(4)

-7x₁+2x₂ <=14(2) x₁, x₂ >=0

4x₁+6x₂ <=24 (3)

 

 

x1
x2

2x₁ +x₂<=16

 

 

x1	-2
x2

 

 

-7x₁ +2x₂<=14

 

4x₁ +6x₂<=24

x1
x2

 

 

 

x1
x2

 

x₁ +2x₂>=8

 

 

Точка была получена в результате пересечения прямых (3) и (4)

4x₁ +6x₂<=24

x₁ +2x₂>=8

 

x₁ >=8- 2x₂

4(8- 2x₂) + 6x₂-24<=0

32-8x₂ +6x₂ – 24<=0

8-2x₂ <=0

x₂ <=4

x₁>=8-2x4, x₁>=0

x₁>=0, x₂ =4

y=3x₁ + x₂

y=3x0 + 4=4

Ответ: 4

 

Самостоятельная работа №3

Симплекс-метод

Преобразовать следующую ЗЛП к канонической форме и решить ее симплекс-методом.

y = x₁-3x₂+x₃ inf

3x₁-x₂+2x₃ ≤ 1

-2x₁+4x₂ ≤ 12

-4x₁+3x₂+8x₃ ≤ 10

x_i ≥ 0, i = 1,3

 

ЦФ min

Следовательно, нет необходимости преобразовывать ЦФ.

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

1-3х₁+х₂-2х₃ ≥ 0

12+2х₁-4х₂ ≥ 0

10+4х₁-3х₂-8х₃ ≥ 0

x_i ≥ 0, i = 1,3

Вводим дополнительные переменные: х₄, х₅, х₆

х₄ = 1-3х₁+х₂-2х₃

х₅ = 12+2х₁-4х₂

х₆ = 10+4х₁-3х₂-8х₃

 

1. Строим симплекс-таблицу.

 

В строке, соответствующей ЦФ, находим максимальное значение коэффициента при х, равном 4. Столбец, в котором располагается максимальное значение, будем считать ведущим.

2. Перерисовываем симплекс-таблицу.

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

1Повторяем операции, пока в строке, соответствующей ЦФ, все коэффициенты не будут меньше 0 или для единственно оставшегося коэффициента со знаком «+» все α/β не будут меньше 0.

 

 

В строке, соответствующей ЦФ, все числа – отрицательные. Следовательно, решение закончено.

х₁ = 8/5 х₅=0

х₂ = 19/5 х₆=5

х₃ = 0

х₄ = 0

 

 

Самостоятельная работа №4

Транспортная сбалансированная задача

Найти оптимальный план перевозок.

Строим систему уравнений: Пусть U₁=0, тогда

U₁+V₁=7 V₁=7

U₁+V₂=8 V₂=8

U₂+V₂=5 U₂ =-3

U₂+V₃=9 V₃=12

U₃+V₃=3 U₃=-9

U₃+V₄=6 V₄=15

Вычисляем псевдо-стоимости: Сравниваем их с реальными:

С _ij= U_i+V_j 12>1 12-1=11

С ₁₃=0+12 = 12 15>2 15-2= 13

С ₁₄=0+15 = 15 4=4

С ₂₁=-3+7 = 4 12>8 12-8=4

С ₂₄=-3+15 = 12 -2<9

С ₃₁=-9+7 = -2 -1<2

С ₃₂=-9+8 = -1

Из узлов со знаком «-» выбираем наименьшее значение – 40.

U₁+V₁=7 U₁=0 С₁₂= -5

U₁+V₄=2 V₁=7 С₁₃= -1

U₂+V₂=5 V₄=2 С₂₁= 17

U₂+V₃=9 U₃=4 С₂₄= 12

U₃+V₃=3 V₃=-1 С₃₁=11

U₃+V₄=6 U₂=10 С₃₂= -1

V₂=-5

Наименьшее значение – 70.

U₁+V₁=7 U₁=0 С₁₂= 8

U₁+V₄=2 V₁=7 С₁₃= 12 12-1= 11

U₂+V₁=4 V₄=2 С₂₄= 10 10-8=2

U₂+V₂=5 U₂=-3 С₃₁= -2

U₂+V₃=9 V₂=8 С₃₂=-1

U₃+V₃=3 V₃=12 С₃₄= -7

U₃=-9

Наименьшее значение – 20.

 

U₁+V₁=7 U₁=0 С₁₂= 8

U₁+V₃=1 V₁=7 С₂₃= -2

U₁+V₄=2 V₃=1 С₂₄= -1

U₂+V₁=4 V₄=2 С₃₁= 9

U₂+V₂=5 U₂=-3 С₃₂= 10

U₃+V₃=3 V₂=8 С₃₄= 4

U₃=2

Наименьшее значение – 20.

U₁+V₁=7 U₁=0 С₁₁= -1 -1<7

U₁+V₄=2 V₃=1 С₁₂= 0 0<8

U₂+V₁=4 V₄=2 С₂₃= 6 6<9

U₂+V₂=5 U₃=2 С₂₄= 7 7<8

U₃+V₂=2 V₂=0 С₃₁= 1 1<9

U₃+V₃=3 U₂=5 С₃₄= 4 4<6

V₁=-1

Минимальные затраты составят:

y = 1*50+2*110+4*120+5*20+2*30+3*140=1330

Самостоятельная работа №5

Транспортная несбалансированная задача

Найти решение несбалансированной ТЗ, представленной соответствующей таблицей из предыдущего задания. Запас груза увеличен на 5 ед., а заявки уменьшены на 8 ед.

U₁+V₁=7 U₁=0 С₁₄= 4 4-2=2

U₁+V₂=8 V₁=7 С_1*= -2

U₁+V₃=1 V₂=8 С₂₁= 15 15-4= 11

U₂+V₃=9 V₃=1 С₂₂= 16 16-5=11

U₃+V₃=3 U₂=8 С₂₄=12 12-8=4

U₃+V₄=6 U₃=2 С_2*= 6 6-0=6

U₃+V_*=0 V₄=4 С₃₁=9

V_*=-2 С₃₂=10 10-2=8

Наименьшее значение – 120.

U₁+V₂=8 U₁=0 С₁₁= -4

U₁+V₃=1 V₂=8 С₁₄= 4 4-2=2

U₂+V₁=4 V₃=1 С_1*= -2

U₂+V₃=9 U₂=8 С₂₂= 16 16-5= 11

U₃+V₃=3 V₁=-4 С₂₄=12 12-8=4

U₃+V₄=6 U₃=2 С_2*= 6 6-0=6

U₃+V_*=0 V₄=4 С₃₁=9

V_*=-2 С₃₂=10 10-2=8

Наименьшее значение –20.

U₁+V₂=8 U₁=0 С₁₁= 7

U₁+V₃=1 V₂=8 С₁₄= 4 4-2=2

U₂+V₁=4 V₃=1 С_1*= -2

U₂+V₂=5 U₂=-3 С₂₃= -2

U₃+V₃=3 V₁=7 С₂₄=1

U₃+V₄=6 U₃=2 С_2*= -5

U₃+V_*=0 V₄=4 С₃₁=9

V_*=-2 С₃₂=10 10-2= 8

Наименьшее значение –22.

 

U₁+V₃=1 U₁=0 С₁₁= -1

U₂+V₁=4 V₃=1 С₁₂= 0

U₂+V₁=4 U₃=2 С₁₄= 4 4-2=2

U₃+V₂=2 V₂=0 С_1*= -2

U₃+V₃=3 U₂=5 С₂₃=6

U₃+V₄=6 V₁=-1 С₂₄= 9 9-8=1

U₃+V_*=0 V₄=4 С_2*=3 3-0= 3

V_*=-2 С₃₁=1

Наименьшее значение –13.

 

U₁+V₃=1 U₁=0 С₁₁= -1

U₂+V₁=4 V₃=1 С₁₂= 0

U₂+V₂=5 U₃=2 С₁₄= 4 4-2= 2

U₂+V_*=0 V₂=0 С_1*= -2

U₃+V₂=2 U₂=5 С₂₃=6

U₃+V₃=3 V₁=-1 С₂₄= 9 9-8=1

U₃+V_*=6 V₄=4 С₃₁=1

V_*=-5 С_3*=-3

Наименьшее значение –110.

U₁+V₃=1 U₁=0 С₁₁= -1 -1<7

U₁+V₄=2 V₃=1 С₁₂= 0 0<8

U₂+V₁=4 V₄=2 С_1*= -5 -5<0

U₂+V₂=5 U₃=2 С₂₃= 6 6<9

U₂+V_*=0 V₂=0 С₂₄=7 7<8

U₃+V₂=2 U₂=5 С₃₁= 1 1<9

U₃+V₃=3 V₁=-1 С₃₄=4 4<6

V_*=-5 С_3*=-3 -3<0

Опорный план является оптимальным, так как все оценки свободных клеток удовлетворяют условию U_i+V_j ≤ C_ij.

Минимальные заработные затраты составят:

y =1*55+2*110+4*120+5*7+0*13+2*35+3*135=1265