Вариант 25. Контрольное задание по теме 3 Линейное программирование. 3

• Название: Контрольное задание по теме 3 Линейное программирование. 3
• Дата: 16.11.2018
• Размер: 1.21 Mb.
• Имя файла: Вариант 25.doc
• Тип: Документы; #56634
• страница: 2 из 13

Контрольное задание по теме 4.3.

«Задачи транспортного типа».

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

1. 
   Свести задачу к закрытому типу (при необходимости).
   
2. 
   Найти базисный план методом северо-западного угла.
   
3. 
   Проверить этот базисный план на оптимальность.
   
4. 
   Выполнить итерации по улучшению плана до получения оптимального решения (после каждой итерации вычислять значение целевой функции).
   

Таблица 25

Мощн/потр	B1= 75	B2 = 80	B3 = 15	B4 = 35
A1 = 10	4	2	3	2
A2 = 33	2	5	3	3
A3 = 100	4	4	6	7
A4 = 48	2	3	4	4

Решение
Математическая модель транспортной задачи:

F = ∑∑c_ijx_ij, (1)

при условиях:

∑x_ij = a_i, i = 1,2,…, m, (2)

∑x_ij = b_j, j = 1,2,…, n, (3)

x_ij ≥ 0

Запишем экономико-математическую модель для нашей задачи.

Ограничения по запасам:

x₁₁ + x₁₂ + x₁₃ + x₁₄ ≤ 10

x₂₁ + x₂₂ + x₂₃ + x₂₄ ≤ 33

x₃₁ + x₃₂ + x₃₃ + x₃₄ ≤ 100

x₄₁ + x₄₂ + x₄₃ + x₄₄ ≤ 48

Ограничения по потребностям:

x₁₁ + x₂₁ + x₃₁ + x₄₁ ≥ 75

x₁₂ + x₂₂ + x₃₂ + x₄₂ ≥ 80

x₁₃ + x₂₃ + x₃₃ + x₄₃ ≥ 15

x₁₄ + x₂₄ + x₃₄ + x₄₄ ≥ 35

Целевая функция:

4x₁₁ + 2x₁₂ + 3x₁₃ + 2x₁₄ + 2x₂₁ + 5x₂₂ + 3x₂₃ + 3x₂₄ + 4x₃₁ + 4x₃₂ +

+ 6x₃₃ + 7x₃₄ + 2x₄₁ + 3x₄₂ + 4x₄₃ + 4x₄₄ → min

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	1	2	3	4	Запасы
1	4	2	3	2	10
2	2	5	3	3	33
3	4	4	6	7	100
4	2	3	4	4	48
Потребности	75	80	15	35

Проверим необходимое и достаточное условие разрешимости задачи:

∑a = 10 + 33 + 100 + 48 = 191

∑b = 75 + 80 + 15 + 35 = 205

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 14 (205—191). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную таблицу:

	1	2	3	4	Запасы
1	4	2	3	2	10
2	2	5	3	3	33
3	4	4	6	7	100
4	2	3	4	4	48
5	0	0	0	0	14
Потребности	75	80	15	35

Этап I. Поиск первого опорного плана.

1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

План начинается заполняться с верхнего левого угла.

Искомый элемент равен 4

Для этого элемента запасы равны 10, потребности 75. Поскольку минимальным является 10, то вычитаем его.

x₁₁ = min(10,75) = 10.

4	x	x	x	10 - 10 = 0
2	5	3	3	33
4	4	6	7	100
2	3	4	4	48
0	0	0	0	14
75 - 10 = 65	80	15	35	0

Искомый элемент равен 2.

Для этого элемента запасы равны 33, потребности 65. Поскольку минимальным является 33, то вычитаем его.

x₂₁ = min(33,65) = 33.

4	x	x	x	0
2	x	x	x	33 - 33 = 0
4	4	6	7	100
2	3	4	4	48
0	0	0	0	14
65 - 33 = 32	80	15	35	0

Искомый элемент равен 4.

Для этого элемента запасы равны 100, потребности 32. Поскольку минимальным является 32, то вычитаем его.

x₃₁ = min(100,32) = 32.

4	x	x	x	0
2	x	x	x	0
4	4	6	7	100 - 32 = 68
x	3	4	4	48
0	0	0	0	14
32 - 32 = 0	80	15	35	0

Искомый элемент равен 4.

Для этого элемента запасы равны 68, потребности 80. Поскольку минимальным является 68, то вычитаем его.

x₃₂ = min(68,80) = 68.

4	x	x	x	0
2	x	x	x	0
4	4	x	x	68 - 68 = 0
x	3	4	4	48
0	0	0	0	14
0	80 - 68 = 12	15	35	0

Искомый элемент равен 3.

Для этого элемента запасы равны 48, потребности 12. Поскольку минимальным является 12, то вычитаем его.

x₄₂ = min(48,12) = 12.

4	x	x	x	0
2	x	x	x	0
4	4	x	x	0
x	3	4	4	48 - 12 = 36
0	0	0	0	14
0	12 - 12 = 0	15	35	0

Искомый элемент равен 4.

Для этого элемента запасы равны 36, потребности 15. Поскольку минимальным является 15, то вычитаем его.

x₄₃ = min(36,15) = 15.

4	x	x	x	0
2	x	x	x	0
4	4	x	x	0
x	3	4	4	36 - 15 = 21
0	0	0	0	14
0	0	15 - 15 = 0	35	0

Искомый элемент равен 4.

Для этого элемента запасы равны 21, потребности 35. Поскольку минимальным является 21, то вычитаем его.

x₄₄ = min(21,35) = 21.

4	x	x	x	0
2	x	x	x	0
4	4	x	x	0
x	3	4	4	21 - 21 = 0
0	0	0	0	14
0	0	0	35 - 21 = 14	0

Искомый элемент равен 0.

Для этого элемента запасы равны 14, потребности 14. Поскольку минимальным является 14, то вычитаем его.

x₅₄ = min(14,14) = 14.

4	x	x	x	0
2	x	x	x	0
4	4	x	x	0
x	3	4	4	0
0	0	0	0	14 - 14 = 0
0	0	0	14 - 14 = 0	0

	1	2	3	4	Запасы
1	4[10]	2	3	2	10
2	2[33]	5	3	3	33
3	4[32]	4[68]	6	7	100
4	2	3[12]	4[15]	4[21]	48
5	0	0	0	0[14]	14
Потребности	75	80	15	35

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 4*10 + 2*33 + 4*32 + 4*68 + 3*12 + 4*15 + 4*21 + 0*14 = 686

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 4; 0 + v₁ = 4; v₁ = 4

u₂ + v₁ = 2; 4 + u₂ = 2; u₂ = -2

u₃ + v₁ = 4; 4 + u₃ = 4; u₃ = 0

u₃ + v₂ = 4; 0 + v₂ = 4; v₂ = 4

u₄ + v₂ = 3; 4 + u₄ = 3; u₄ = -1

u₄ + v₃ = 4; -1 + v₃ = 4; v₃ = 5

u₄ + v₄ = 4; -1 + v₄ = 4; v₄ = 5

u₅ + v₄ = 0; 5 + u₅ = 0; u₅ = -5

	v1=4	v2=4	v3=5	v4=5
u1=0	4[10]	2	3	2
u2=-2	2[33]	5	3	3
u3=0	4[32]	4[68]	6	7
u4=-1	2	3[12]	4[15]	4[21]
u5=-5	0	0	0	0[14]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(1;2): 0 + 4 > 2; ∆₁₂ = 0 + 4 - 2 = 2

(1;3): 0 + 5 > 3; ∆₁₃ = 0 + 5 - 3 = 2

(1;4): 0 + 5 > 2; ∆₁₄ = 0 + 5 - 2 = 3

(4;1): -1 + 4 > 2; ∆₄₁ = -1 + 4 - 2 = 1

max(2,2,3,1) = 3

Выбираем максимальную оценку свободной клетки (1;4): 2.

Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	4[10][-]	2	3	2[+]	10
2	2[33]	5	3	3	33
3	4[32][+]	4[68][-]	6	7	100
4	2	3[12][+]	4[15]	4[21][-]	48
5	0	0	0	0[14]	14
Потребности	75	80	15	35

Цикл приведен в таблице (1,4 → 1,1 → 3,1 → 3,2 → 4,2 → 4,4).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	4	2	3	2[10]	10
2	2[33]	5	3	3	33
3	4[42]	4[58]	6	7	100
4	2	3[22]	4[15]	4[11]	48
5	0	0	0	0[14]	14
Потребности	75	80	15	35

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2

u₄ + v₄ = 4; 2 + u₄ = 4; u₄ = 2

u₄ + v₂ = 3; 2 + v₂ = 3; v₂ = 1

u₃ + v₂ = 4; 1 + u₃ = 4; u₃ = 3

u₃ + v₁ = 4; 3 + v₁ = 4; v₁ = 1

u₂ + v₁ = 2; 1 + u₂ = 2; u₂ = 1

u₄ + v₃ = 4; 2 + v₃ = 4; v₃ = 2

u₅ + v₄ = 0; 2 + u₅ = 0; u₅ = -2

	v1=1	v2=1	v3=2	v4=2
u1=0	4	2	3	2[10]
u2=1	2[33]	5	3	3
u3=3	4[42]	4[58]	6	7
u4=2	2	3[22]	4[15]	4[11]
u5=-2	0	0	0	0[14]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij.

(4;1): 2 + 1 > 2; ∆₄₁ = 2 + 1 - 2 = 1

Выбираем максимальную оценку свободной клетки (4;1): 2.

Для этого в перспективную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	4	2	3	2[10]	10
2	2[33]	5	3	3	33
3	4[42][-]	4[58][+]	6	7	100
4	2[+]	3[22][-]	4[15]	4[11]	48
5	0	0	0	0[14]	14
Потребности	75	80	15	35

Цикл приведен в таблице (4,1 → 4,2 → 3,2 → 3,1).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 2) = 22. Прибавляем 22 к объемам грузов, стоящих в плюсовых клетках и вычитаем 22 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	4	2	3	2[10]	10
2	2[33]	5	3	3	33
3	4[20]	4[80]	6	7	100
4	2[22]	3	4[15]	4[11]	48
5	0	0	0	0[14]	14
Потребности	75	80	15	35

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2

u₄ + v₄ = 4; 2 + u₄ = 4; u₄ = 2

u₄ + v₁ = 2; 2 + v₁ = 2; v₁ = 0

u₂ + v₁ = 2; 0 + u₂ = 2; u₂ = 2

u₃ + v₁ = 4; 0 + u₃ = 4; u₃ = 4

u₃ + v₂ = 4; 4 + v₂ = 4; v₂ = 0

u₄ + v₃ = 4; 2 + v₃ = 4; v₃ = 2

u₅ + v₄ = 0; 2 + u₅ = 0; u₅ = -2

	v1=0	v2=0	v3=2	v4=2
u1=0	4	2	3	2[10]
u2=2	2[33]	5	3	3
u3=4	4[20]	4[80]	6	7
u4=2	2[22]	3	4[15]	4[11]
u5=-2	0	0	0	0[14]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(2;3): 2 + 2 > 3; ∆₂₃ = 2 + 2 - 3 = 1

(2;4): 2 + 2 > 3; ∆₂₄ = 2 + 2 - 3 = 1

max(1,1) = 1

Выбираем максимальную оценку свободной клетки (2;3): 3.

Для этого в перспективную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	4	2	3	2[10]	10
2	2[33][-]	5	3[+]	3	33
3	4[20]	4[80]	6	7	100
4	2[22][+]	3	4[15][-]	4[11]	48
5	0	0	0	0[14]	14
Потребности	75	80	15	35

Цикл приведен в таблице (2,3 → 2,1 → 4,1 → 4,3).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 3) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	4	2	3	2[10]	10
2	2[18]	5	3[15]	3	33
3	4[20]	4[80]	6	7	100
4	2[37]	3	4	4[11]	48
5	0	0	0	0[14]	14
Потребности	75	80	15	35

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2

u₄ + v₄ = 4; 2 + u₄ = 4; u₄ = 2

u₄ + v₁ = 2; 2 + v₁ = 2; v₁ = 0

u₂ + v₁ = 2; 0 + u₂ = 2; u₂ = 2

u₂ + v₃ = 3; 2 + v₃ = 3; v₃ = 1

u₃ + v₁ = 4; 0 + u₃ = 4; u₃ = 4

u₃ + v₂ = 4; 4 + v₂ = 4; v₂ = 0

u₅ + v₄ = 0; 2 + u₅ = 0; u₅ = -2

	v1=0	v2=0	v3=1	v4=2
u1=0	4	2	3	2[10]
u2=2	2[18]	5	3[15]	3
u3=4	4[20]	4[80]	6	7
u4=2	2[37]	3	4	4[11]
u5=-2	0	0	0	0[14]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(2;4): 2 + 2 > 3; ∆₂₄ = 2 + 2 - 3 = 1

Выбираем максимальную оценку свободной клетки (2;4): 3.

Для этого в перспективную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	4	2	3	2[10]	10
2	2[18][-]	5	3[15]	3[+]	33
3	4[20]	4[80]	6	7	100
4	2[37][+]	3	4	4[11][-]	48
5	0	0	0	0[14]	14
Потребности	75	80	15	35

Цикл приведен в таблице (2,4 → 2,1 → 4,1 → 4,4).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 4) = 11. Прибавляем 11 к объемам грузов, стоящих в плюсовых клетках и вычитаем 11 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	4	2	3	2[10]	10
2	2[7]	5	3[15]	3[11]	33
3	4[20]	4[80]	6	7	100
4	2[48]	3	4	4	48
5	0	0	0	0[14]	14
Потребности	75	80	15	35

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2

u₂ + v₄ = 3; 2 + u₂ = 3; u₂ = 1

u₂ + v₁ = 2; 1 + v₁ = 2; v₁ = 1

u₃ + v₁ = 4; 1 + u₃ = 4; u₃ = 3

u₃ + v₂ = 4; 3 + v₂ = 4; v₂ = 1

u₄ + v₁ = 2; 1 + u₄ = 2; u₄ = 1

u₂ + v₃ = 3; 1 + v₃ = 3; v₃ = 2

u₅ + v₄ = 0; 2 + u₅ = 0; u₅ = -2

	v1=1	v2=1	v3=2	v4=2
u1=0	4	2	3	2[10]
u2=1	2[7]	5	3[15]	3[11]
u3=3	4[20]	4[80]	6	7
u4=1	2[48]	3	4	4
u5=-2	0	0	0	0[14]

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

Оптимальный план перевозок в виде графа

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

F(x) = 2*10 + 2*7 + 3*15 + 3*11 + 4*20 + 4*80 + 2*48 + 0*14 = 608.

Оптимальный план является вырожденным, так как базисная переменная x₅₄=0.

Ответ:

- из 1-го склада необходимо весь груз направить в 4-й магазин;

- из 2-го склада необходимо груз направить в 1-й магазин (7), в 3-й магазин (15), в 4-й магазин (11);

- из 3-го склада необходимо груз направить в 1-й магазин (20), в 2-й магазин (80);

- из 4-го склада необходимо весь груз направить в 1-й магазин.

Потребность 4-го магазина остается неудовлетворенной на 14 ед.

При этом минимальные затраты составят 608 ден. ед.