Решение задач по экономике (Вариант 5)

Составить математическую модель, найти оптимальный план перевозок  и оптимальные издержки в транспортной задаче, заданной таблицами.

Поставщик	а i		Потребитель	b j		Транспортные издержки на маршруте на единицу груза
							j=1	j=2	j=3
i=1	90		j=1	140		i=1	2	5	2
i=2	400		j=2	300		i=2	4	1	5
i=3	110		j=3	160		i=3	3	6	8

Решение

1) Составим математическую модель транспортной задачи. Введем обозначения: А_i – поставщики; B_j – потребители. Представим исходные данные в виде транспортной таблицы:

Поставщики	Потребители			Запасы груза
	2	5	2	90
	4	1	5	400
	3	6	8	110
Потребности в грузе	140	300	160

  Обозначим через х_ij – объём перевозки груза от i-го поставщика к j-му потребителю. Тогда суммарные транспортные издержки на перевозку груза F(x) составят: Проверим тип представленной транспортной задачи: Так как , то суммарные запасы груза у поставщиков равны суммарной потребности потребителей, поэтому данная задача является закрытой. Заданные запасы груза у поставщиков и потребности потребителей накладывают ограничения на значения объемов перевозок груза x_ij. Ограничения по запасам груза у поставщиков: Ограничения по потребностям потребителей: Объемы перевозимого груза не могут быть отрицательными: Математическая модель представленной транспортной задачи составлена. 2) Построим опорный (базисный) план перевозок методом «минимальной стоимости» («минимального тарифа»). Выбираем клетку с минимальным тарифом. Искомый элемент равен c₂₂=1. Для этого элемента запасы равны 400, потребности 300. Поскольку минимальным является 300, то вычитаем его: x₂₂ = min(400, 300) = 300. Искомый элемент равен c₁₁=2. Для этого элемента запасы равны 90, потребности 140. Поскольку минимальным является 90, то вычитаем его: x₁₁ = min(90, 140) = 90. Аналогично определяем остальные элементы: x₃₁ = min(110, 50) = 50; x₂₃ = min(100, 160) = 100; x₃₃ = min(60, 60) = 60. В результате получен опорный план, который является допустимым, так как соответствует системе ограничений транспортной задачи:

Поставщики	Потребители			Запасы груза
	2[90]	5	2	90
	4	1[300]	5[100]	400
	3[50]	6	8[60]	110
Потребности в грузе	140	300	160

  Таким образом, опорный план перевозок груза имеет вид: Вычислим значение целевой функции (суммарные транспортные издержки на перевозку груза) для построенного плана: Число  занятых  клеток таблицы равно 5. Их должно быть m + n — 1 = 3 + 3 — 1 = 5, поэтому опорный план является невырожденным. 3) Найдем оптимальный план перевозок методом потенциалов. Итерация 1. Этап 1. Проверим оптимальность опорного плана. Для занятых клеток составим систему уравнений потенциалов: u₁ + v₁ = 2;                     u₁ = 0;                            v₁ = 2; u₃ + v₁ = 3;                     2 + u₃ = 3;                      u₃ = 1; u₃ + v₃ = 8;                     1 + v₃ = 8;                      v₃ = 7; u₂ + v₃ = 5;                     7 + u₂ = 5;                      u₂ = -2; u₂ + v₂ = 1;                     -2 + v₂ = 1;                     v₂ = 3.

	v1=2	v2=3	v3=7
u1=0	2[90]	5	2
u2=-2	4	1[300]	5[100]
u3=1	3[50]	6	8[60]

  Для каждой свободной клетки найдем оценку: ∆₁₂ = u₁ + v₂ — с₁₂ = 0 + 3 — 5 = -2 < 0; ∆₁₃ = u₁ + v₃ — с₁₃ = 0 + 7 — 2 = 5 > 0; ∆₂₁ = u₂ + v₁ — с₂₁ = -2 + 2 — 4 = -4 < 0; ∆₃₂ = u₃ + v₂ — с₃₂ = 1 + 3 — 6 = -2 < 0. Среди оценок есть положительная, поэтому решение не оптимально. Этап 2. Выполним переход к новому допустимому решению. 1) Выбираем клетку (1;3), так как данная клетка имеет положительное значение оценки ∆₁₃. 2) Для клетки (1;3) «организуем цикл»: соединим ее с помощью многоугольника с занятыми клетками: (1;1), (3;1), (3;3). 3) Расставляем в выделенных клетках «+» и «-»: в свободной клетке (1;3) «+», а в остальных по порядку «-», «+»:

Поставщики	Потребители			Запасы груза
	2[90][-]	5	2[+]	90
	4	1[300]	5[100]	400
	3[50][+]	6	8[60][-]	110
Потребности в грузе	140	300	160

  4) В клетках со знаком «-» выбираем наименьшее значение: min (90; 60) = 60. 5) Данное наименьшее значение прибавляем в клетки со знаком «+» к объемам перевозок и вычитаем в клетках со знаком «-». Свободная клетка становится занятой, а клетка с объемом перевозок 0 – свободной. В результате получаем новый план перевозок:

Поставщики	Потребители			Запасы груза
	2[30]	5	2[60]	90
	4	1[300]	5[100]	400
	3[110]	6	8	110
Потребности в грузе	140	300	160

  Матрица перевозок груза имеет вид: Вычислим значение целевой функции  для построенного плана: Возвращаемся к этапу 1. Итерация 2. Этап 1. Проверим оптимальность опорного плана. Для занятых клеток составим систему уравнений потенциалов: u₁ + v₁ = 2;                     u₁ = 0;                            v₁ = 2; u₃ + v₁ = 3;                     2 + u₃ = 3;                      u₃ = 1; u₁ + v₃ = 2;                     0 + v₃ = 2;                      v₃ = 2; u₂ + v₃ = 5;                     2 + u₂ = 5;                      u₂ = 3; u₂ + v₂ = 1;                     3 + v₂ = 1;                      v₂ = -2.

	v1=2	v2=-2	v3=2
u1=0	2[30]	5	2[60]
u2=3	4	1[300]	5[100]
u3=1	3[110]	6	8

  Для каждой свободной клетки найдем оценку: ∆₁₂ = u₁ + v₂ — с₁₂ = 0 — 2 — 5 = -7 < 0; ∆₂₁ = u₂ + v₁ — с₂₁ = 3 + 2 — 4 = 1 > 0; ∆₃₂ = u₃ + v₂ — с₃₂ = 1 — 2 — 6 = -7 < 0; ∆₃₃ = u₃ + v₃ — с₃₃ = 1 + 2 — 8 = -5 < 0. Среди оценок есть положительная, поэтому решение не оптимально. Этап 2. Выполним переход к новому допустимому решению. 1) Выбираем клетку (2;1). 2) Для клетки (2;1) «организуем цикл»: соединим ее с помощью многоугольника с занятыми клетками: (2;3), (1;3), (1;1). 3) Расставляем в выделенных клетках «+» и «-»: в свободной клетке (2;1) «+», а в остальных по порядку «-», «+»:

Поставщики	Потребители			Запасы груза
	2[30][-]	5	2[60][+]	90
	4[+]	1[300]	5[100][-]	400
	3[110]	6	8	110
Потребности в грузе	140	300	160

  4) В клетках со знаком «-» выбираем наименьшее значение: min (30; 100) = 30. 5) Данное наименьшее значение прибавляем в клетки со знаком «+» к объемам перевозок и вычитаем в клетках со знаком «-». Свободная клетка становится занятой, а клетка с объемом перевозок 0 – свободной. В результате получаем новый план перевозок:

Поставщики	Потребители			Запасы груза
	2	5	2[90]	90
	4[30]	1[300]	5[70]	400
	3[110]	6	8	110
Потребности в грузе	140	300	160

  Матрица перевозок груза имеет вид: Вычислим значение целевой функции  для построенного плана: Возвращаемся к этапу 1. Итерация 3. Этап 1. Проверим оптимальность опорного плана. Для занятых клеток составим систему уравнений потенциалов: u₁ + v₃ = 2;                     u₁ = 0;                            v₃ = 2; u₂ + v₃ = 5;                     2 + u₂ = 5;                      u₂ = 3; u₂ + v₁ = 4;                     3 + v₁ = 4;                      v₁ = 1; u₃ + v₁ = 3;                     1 + u₃ = 3;                      u₃ = 2; u₂ + v₂ = 1;                     3 + v₂ = 1;                      v₂ = -2.

	v1=1	v2=-2	v3=2
u1=0	2	5	2[90]
u2=3	4[30]	1[300]	5[70]
u3=2	3[110]	6	8

  Для каждой свободной клетки найдем оценку: ∆₁₁ = u₁ + v₁ — с₁₁ = 0 + 1 — 2 = -1 < 0; ∆₁₂ = u₁ + v₂ — с₁₂ = 0 — 2 — 5 = -7 < 0; ∆₃₂ = u₃ + v₂ — с₃₂ = 2 — 2 — 6 = -6 < 0; ∆₃₃ = u₃ + v₃ — с₃₃ = 2 + 2 — 8 = -4 < 0. Среди оценок нет положительных, поэтому решение оптимально. Таким образом, оптимальный план перевозок груза: Минимальные суммарные издержки на транспортировку груза составят: Ответ. Весь груз (90 единиц), который находится у первого поставщика, необходимо направить третьему потребителю. Груз, который находится у второго поставщика, необходимо направить первому потребителю в количестве 30 единиц, второму потребителю в количестве 300 единиц и третьему потребителю в количестве 70 единиц. Весь груз (110 единиц), который находится у третьего поставщика, необходимо направить первому потребителю. При использовании данного плана перевозок груза издержки на транспортировку груза  будут минимальными и составят 1280 денежных единиц.