Применение математических методов в экономических исследованиях и планировании

 

В таблице (кроме строки Z) cнова есть отрицательные свободные члены, значит, наш исходный вариант опять недопустим.

Выбираем разрешающий  элемент:

1) разрешающая строка: среди  отрицательных свободных членов, кроме строки Z, выбираем наибольший по абсолютной величине, в нашем случае это -7/4=-1,75; т.к. остальные 3/4=0,75; -1/2=-0,5;

2) разрешающий столбец:  поделим свободные члены разрешающей  строки на каждый ее коэффициент  (т.е. -7/4 : -14/4=0,5; -7/4 : 1/4=-7; -7/4 : -3/4=2,33) наименьшее из положительных отношений укажет на столбец (в нашем примере -7/4 : -14/4).

На пересечении разрешающей  строки и разрешающего столбца находится  разрешающий элемент а₁₁=-14/4.

1 : (-14/4) = - 55/14

Заполняем строчку соответствующую  разрешающему элементу, каждый элемент  строки разделить на разрешающий  элемент.

Заполняем столбец: каждый элемент  столбца разделить на разрешающий  элемент и умножить на -1.

Далее заполняем таблицу  по правилу прямоугольника.

Делая шаг МЖИ, получаем таблицу  3.

Таблица 3. – Симплекс таблица  после второй итерации.

	-y1	- y2	-x3	Свободные члены
x1	-2/7	-1/14	3/14	1/2
x2	1/7	-3/14	-19/4	2/4
y3	4/7	-5/14		-6/4
Z	-5/7	-15/14	-59/14	14/4

 

В таблице (кроме строки Z) опять есть отрицательные свободные члены, значит, наш исходный вариант снова недопустим.

Выбираем разрешающий  элемент:

1) разрешающая строка: среди  отрицательных свободных членов, кроме строки Z, выбираем наибольший по абсолютной величине, в нашем случае это    -6/4;

2) разрешающий столбец:  поделим свободные члены разрешающей  строки на каждый ее коэффициент  (т.е. -6/4 : -55/14=0,39; -6/4 : -5/14=4,17; -6/4 : 4/7=-2,63) наименьшее из положительных отношений укажет на столбец (в нашем примере -6/4 : -55/14).

На пересечении разрешающей  строки и разрешающего столбца находится  разрешающий элемент а₃₃=-55/14.

1 : (-55/14) = - 14/55

Заполняем строчку соответствующую  разрешающему элементу, каждый элемент  строки разделить на разрешающий  элемент.

Заполняем столбец: каждый элемент  столбца разделить на разрешающий  элемент и умножить на -1.

Далее заполняем таблицу  по правилу прямоугольника.

Делая шаг МЖИ, получаем таблицу  4.

Таблица 4. – Симплекс таблица  после третьей итерации.

	-y1	- y2	-y3	Свободные члены
x1	-107/385	-1/11	3/55	23/55
x2	-21/385	-7/77	-19/55	56/55
x3	-8/55	1/11		21/55
Z	-511/385	-6/11	-59/55	281/55

 

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

 

Ответ: Базисные переменные равны соответствующим свободным членам, поэтому Z = 281/55 или 5,11; x1 =23/55 или 0,42; x2 = 56/55 или 1,02;  x3 = 21/55 или 0,38; y3 = 0; y2 =0; y₁ =0.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Задача №  2.

Решить транспортную задачу:

b1 = 100          a1 = 50 4  3  5  6

b2 = 150          a2 = 100                            C =  2  1  8  3

b3 = 50            a3 = 70     7  3  9  10 

                        а4 = 80

 на min.

Решение:

Пусть A1 , A2 , A3, А4 - магазины, которым требуется соответственно 50, 100, 70, 80 единиц однотипной продукции, а B1 , B2 , B3 - поставщики, которым необходимо доставить эту продукцию по минимальным затратам на перевозку (на складах имеется 100, 150, 50 единиц соответственно).

Стоимость доставки единицы  продукции от поставщика В1 к указанным потребителям равна 4 , 3 , 5 , 6 ден.ед соответственно.

Стоимость доставки единицы  продукции от поставщика В2 к указанным потребителям равна 2, 1, 8, 3 ден.ед.

Стоимость доставки единицы  продукции от поставщика A3 к указанным  потребителям равна 7 , 3 , 9, 10 ден.ед.

Требуется найти оптимальное  решение доставки продукции от поставщиков  к потребителям.

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

В нашем случае, потребность  всех магазинов - 300 единиц продукции равна запасам всех поставщиков.

₃

∑ bi = 100+150+50 = 300

       ^{i =1}

 ₄

∑ aj = 50+100+70+80 = 300,

       ^{j =1}

следовательно задача закрытого типа.

 

1) Z = 4*x₁₁+3*x₁₂+5*x₁₃+6*x₁₄₊2*x₂₁+1*x₂₂+8*x₂₃+3*x₂₄+7*x₃₁+3*x₃₂+9*x₃₃+10*x₃₄→min

2) 1) x₁₁+ x₁₂+ x₁₃+ x₁₄=100                            2) x₁₁+ x₂₁+ x₃₁=50

         x₂₁+ x₂₂+ x₂₃+ x₂₄=150                                x₁₂+ x₂₂+ x₃₂=100

         x₃₁+ x₃₂+ x₃₃+ x₃₄=50                                  x₁₃+ x₂₃+ x₃₃=70

                                                                          x₁₄+ x₂₄+ x₃₄=80

3) i = 1, 3; j = 1, 4

 

Найдем начальное решение  методом северо-западного угла.

Поставщики, i	Магазины, j				Запасы, i
	а1	а2	а3	а4
b1	50 4	3	5	50       6	100
b2	2	100 1	50        8	3	150
b3	7	3	20 9	30    10	50
Потребность, j	50	100	70	80

 

Zфакт = 4 * 50 + 6 * 50 + 1 * 100 + 8 * 50 + 9 * 20 +10 * 30 = 1480 ден. ед.

 

Метод потенциалов:

1) Проверка на вырожденность:

N = 6 (количество заполненных клеток) = m+n-1, где m - количество строк в таблице, n - количество столбцов в таблице = 3+4-1 = 6, следовательно вариант невырожденный.

2) Рассчитываем потенциалы  поставщиков и потенциалы потребителей:

Vj – Ui = Cij, где Vj – потенциалы потребителей, Ui – потенциалы поставщиков, Cij – цена перевозки, это уравнение справедливо для заполненных клеток.

V1 – U1 = C11     пусть U1=0, тогда     V1 – 0 = 4                  V1 = 4

V2 – U2 = C22                                        V2 – (-3) = 1              V3 = -2

V3 – U2 = C23                                        5 – U2 = 8                  U2 = -3

V3 – U3 = C33                                      V3 – (-4) = 9                  U2 = 5

V4 – U1 = C14                                      V4 – 0 = 6                      V4 = 3

V4 – U3 = C34                                       6 – U3 = 10                   U3 = -4

3) Для пустых клеток: Vj – Ui ≤ Cij, тогда

V1 – U2 ≤ C21                                     4 – (-3)  ≤ 2 – не верное неравенство

V1 – U3 ≤ C31                                 4 – (-4) ≤ 7 – не верное неравенство

V2 – U1 ≤ C12                                -2 – 0 ≤ 3 – верное неравенство

V2 – U3 ≤ C32                                -2 – (-4) ≤ 7 – верное неравенство

V3 – U1 ≤ C13                                 5 – 0 ≤ 5 – верное неравенство

V4 – U2 ≤ C24                                   6 – (– 3) ≤ 3 – не верное неравенство

4) £ij = [Vj – Ui - Cij]

    £13 = [8 – 7] = 1, поставим £ в клетку 13.

Поставщики, i	Магазины, j				Запасы, i
	а1	а2	а3	а4
b1	50 4	3	20    5	30       6	100
b2	2	100 1	8	50          3	150
b3	7	3	50 9	10	50
Потребность, j	50	100	70	80

Zфакт = 4 * 50 + 5 * 20 + 6 * 30 + 1 * 100 + 3 * 50 + 9 * 50 = 1300 ден. ед.

Фактические затраты значительно  ниже, но проверяем дальше на оптимальность:

Снова находим 2 неоптимальных  решения неравенств

  

 

 

 

 

 

 £32 = поставим £ в клетку 32.

Поставщики, i	Магазины, j				Запасы, i
	а1	а2	а3	а4
b1	50 4	3	50    5	6	100
b2	2	70 1	8	80          3	150
b3	7	30 3	20 9	10	50
Потребность, j	50	100	70	80

 

Zфакт = 4 * 50 + 5 * 50 + 1 * 70 + 3 * 80 + 3 * 30 + 9 * 20 = 1030 ден. ед.

Фактические затраты значительно  опять ниже, но проверяем дальше на оптимальность:

Снова находим 2 неоптимальных  решения неравенств

    £31 = поставим £ в клетку 31.

Поставщики, i	Магазины, j				Запасы, i
	а1	а2	а3	а4
b1	30 4	3	70    5	6	100
b2	20    2	50 1	8	80          3	150
b3	7	50 3	9	10	50
Потребность, j	50	100	70	80

 

Zфакт = 4 * 30 + 5 * 70 + 2 * 20 + 3 * 80 + 3 * 50 = 990 ден. Ед.

 

Получили оптимальный  вариант.

Ответ: Сумма расстояний на перевозку будет минимальной  и равна 990, если 1-ый поставщик перевезет 1-ому и 3-ому магазинам по 30 и 70 единиц продукции соответственно, 2-ой поставщик перевезет 1-ому магазину, 2-ому магазину, 4-ому магазину 20, 50 и 80 единиц продукции соответственно, а 3-ий поставщик 2-ому магазину – 50 единиц продукции.