Контрольная работа по "Эконометрике"

Условие задачи:

На заводах А1, A2 производится однородная продукция в количестве  250, 250 единиц. Трем потребителям В1, В2, В3 требуется соответственно 150, 150, 200 единиц готовой продукции. Известны расходы с11=3, с12=4, с13=8, с21=4, с22=1, с23=4 ден. ед. по перевозке единицы готовой продукции с завода Аi потребителю Вj.

Необходимо найти план перевозок, минимизирующий общие затраты по изготовлению продукции на заводах А1, A2 и ее доставке потребителям В1, В2, В3.

 

Решение:

 

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

F = ∑∑c_ijx_ij,    (1)

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

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

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

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

 

	1	2	3	Запасы
1	3	4	8	250
2	4	1	4	250
Потребности	150	150	200

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

∑a = 250 + 250 = 500

∑b = 150 + 150 + 200 = 500

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

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

 

	1	2	3	Запасы
1	3	4	8	250
2	4	1	4	250
Потребности	150	150	200

 

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

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

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

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

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

x₁₁ = min(250,150) = 150.

 

3	4	8	250 - 150 = 100
x	1	4	250
150 - 150 = 0	150	200	0

 

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

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

x₁₂ = min(100,150) = 100.

 

3	4	x	100 - 100 = 0
x	1	4	250
0	150 - 100 = 50	200	0

 

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

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

x₂₂ = min(250,50) = 50.

 

3	4	x	0
x	1	4	250 - 50 = 200
0	50 - 50 = 0	200	0

 

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

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

x₂₃ = min(200,200) = 200.

 

3	4	x	0
x	1	4	200 - 200 = 0
0	0	200 - 200 = 0	0

 

 

	1	2	3	Запасы
1	3[150]	4[100]	8	250
2	4	1[50]	4[200]	250
Потребности	150	150	200

 

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

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

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

F(x) = 3*150 + 4*100 + 1*50 + 4*200  = 1700

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

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

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

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

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

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

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

x₂₂ = min(250,150) = 150.

 

 

 

3	x	8	250
4	1	4	250 - 150 = 100
150	150 - 150 = 0	200	0

 

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

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

x₁₁ = min(250,150) = 150.

 

3	x	8	250 - 150 = 100
x	1	4	100
150 - 150 = 0	0	200	0

 

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

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

x₂₃ = min(100,200) = 100.

 

3	x	8	100
x	1	4	100 - 100 = 0
0	0	200 - 100 = 100	0

 

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

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

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

 

3	x	8	100 - 100 = 0
x	1	4	0
0	0	100 - 100 = 0	0

 

 

	1	2	3	Запасы
1	3[150]	4	8[100]	250
2	4	1[150]	4[100]	250
Потребности	150	150	200

 

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

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

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

F(x) = 3*150 + 8*100 + 1*150 + 4*100  = 1800

 

Таким образом, опорный план, построенный методом «северо-западного  угла» является лучшим. Теперь перейдем к следующему этапу.

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

 

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

u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3

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

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

u₂ + v₃ = 4; -3 + v₃ = 4; v₃ = 7

 

	v1=3	v2=4	v3=7
u1=0	3[150]	4[100]	8
u2=-3	4	1[50]	4[200]

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

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

F(x) = 3*150 + 4*100 + 1*50 + 4*200  = 1700

 

Вывод:

Из 1-го склада необходимо груз направить в 1-й магазин (150) при этом затраты составят 450, в 2-й магазин (100) и затраты будут равны 400.

Из 2-го склада необходимо груз направить в 2-й магазин (50) и затраты равны 50, в 3-й магазин (200), при этом затраты составят 800.