Задание 3. Трем поставщикам А1, А2, А3 поступил однородный груз в количестве: тонн – поставщику

Трем поставщикам А₁, А₂, А₃ поступил однородный груз в количестве: тонн – поставщику А₁; тонн – поставщику А₂; тонн – поставщику А₃. Полученный груз требуется перевести пяти потребителям: тонн – потребителю В₁; тонн – потребителю В₂; тонн – потребителю В₃; тонн – потребителю В₄; тонн – потребителю В₅. Расстояние между пунктами отправления и пунктами назначения указаны в таблице. Стоимость перевозок пропорциональна количеству груза и расстоянию, на которое этот груз перевозится.

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

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

№ 1

=200; =150; =150;

=90; =100; =70; =130; =110; .

Решение.

Объем продукции доставленный от поставщика потребителю зададим переменной . Тогда план перевозок груза можно записать в виде матрицы

Затраты на перевозку груза от i-го поставщика j-му потребителю можно записать как произведение , тогда суммарные затраты на реализацию плана перевозок равны:

=

.

Цель задачи – минимизировать эти транспортные издержки.

Проверим условие баланса: суммарные потребности потребителей 90+100+70+130+110=500, суммарные запасы продукции всех поставщиков 200+150+150=500. Суммарные потребности потребителей равны суммарным запасам продукции всех поставщиков. Т. е. имеем закрытую задачу.

Опорный план находим методом минимальной стоимости. Ячейки с тарифом 0 заполняем в последнюю очередь. Наименьшим тарифом является 8.

	В1	В2	В3	В4	В5	запасы
А1	12	9	-2	5
А2			+ 15 -10	- 11	2
А3	4	7	- 26	+ 12	0
потребности

Записываем в левый нижний угол клетки А₂В₂ – 100 ед. продукции. Потребности полностью удовлетворены, столбец В₂ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 11. Записываем в левый нижний угол клетки А₂В₄ – 50 ед. продукции. Запасы полностью исчерпаны, строку А₂ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 12. Записываем в левый нижний угол клетки А₁В₁ – 90 ед. продукции. Потребности полностью удовлетворены, столбец В₁ вычеркиваем. Записываем в левый нижний угол клетки А₃В₄ – 80 ед. продукции. Потребности полностью удовлетворены, столбец В₄ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 17. Записываем в левый нижний угол клетки А₁В₅ – 110 ед. продукции. Потребности полностью удовлетворены и запасы исчерпаны, столбец В₅ и строку А₁ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 26. Записываем в левый нижний угол клетки А₃В₃ – 70 ед. продукции. Запасы полностью исчерпаны и потребности полностью удовлетворены. Строку А₃ и столбец В₃ вычеркиваем.

Число занятых клеток должно быть равно . В нашем случае число занятых клеток равно 6. Имеем вырожденный план. Это произошло из-за того, что при заполнении клетки А₁В₅ были вычеркнуты две линии (под линией понимаем строку или столбец). Занимаем одну клетку, так чтобы она не составляла с другими занятыми клетками замкнутый цикл. Выбираем, А₂В₁.

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

Проверим полученный опорный план на оптимальность. Находим потенциалы: и . Для каждой базисной переменной потенциалы удовлетворяют условию + = . Имеем систему:

Пусть =0, тогда =12

=2 =6

=3 23

9

17

Теперь для небазисных клеток найдем оценки . Оценки запишем в левый нижний угол. Так как среди оценок есть отрицательные, то план не оптимален. Наибольшая по модулю отрицательная оценка -10 стоит в ячейке А₂В₃. Ячейка А₂В₃ становится опорной, строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки «+» и «-», начиная с опорной клетки, которой присваиваем знак «+».

Выбираем наименьшее значение из клеток со знаком «-» : прибавляем 50 к значениям в клетках со знаком «+» и вычитаем 50 из значений в клетках со знаком

«-».

	В1	В2	В3	В4	В5	запасы
А1	+ 12	9	8	15	- 17
А2	- 14		+ 15	10	2
А3	4	-3	- 26		+ 20 -10
потребности
				-1

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

Пусть =0, тогда =12

=2 =6

=13 13

-1

17

Теперь для небазисных клеток найдем оценки . Оценки запишем в левый нижний угол. Так как среди оценок есть отрицательные, то план не оптимален. Наибольшая по модулю отрицательная оценка -10 стоит в ячейке А₃В₅. Ячейка А₃В₅ становится опорной, строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки «+» и «-», начиная с опорной клетки, которой присваиваем знак «+».

Выбираем наименьшее значение из клеток со знаком «-» : прибавляем 0 к значениям в клетках со знаком «+» и вычитаем 0 из значений в клетках со знаком «-».

	В1	В2	В3	В4	В5	запасы
А1	12	-1	-2	5
А2	10	- 8	+ 15	10	12		-8
А3	4	+ 16 -3	- 26
потребности

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

Пусть =0, тогда =12

=-8 =16

=3 23

9

17

Теперь для небазисных клеток найдем оценки . Оценки запишем в левый нижний угол. Так как среди оценок есть отрицательные, то план не оптимален. Наибольшая по модулю отрицательная оценка -3 стоит в ячейке А₃В₂. Ячейка А₃В₂ становится опорной, строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки «+» и «-», начиная с опорной клетки, которой присваиваем знак «+».

Выбираем наименьшее значение из клеток со знаком «-» : прибавляем 20 к значениям в клетках со знаком «+» и вычитаем 20 из значений в клетках со знаком

«-».

	В1	В2	В3	В4	В5	запасы
А1	12	-2	1	5
А2	7			7	9		-5
А3	4		3
потребности

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

Пусть =0, тогда =12

=-5 =13

=3 20

9

17

Так как среди оценок для небазисных клеток нет отрицательных, то план оптимален.

Итак, 1-ый поставщик отправляет 90 тонн груза первому потребителю и 110 тонн груза пятому потребителю.

2-ой поставщик отправляет 80 тонн груза второму потребителю и 70 тонн груза третьему потребителю.

3-ий поставщик отправляет 20 тонн груза второму потребителю и 130 тонн груза четвертому потребителю.

Суммарные затраты при этом 6520 тонн-километров.

№ 2

=300; =280; =220;

=180; =140; =190; =120; =170; .

Решение.

Объем продукции доставленный от поставщика потребителю зададим переменной . Тогда план перевозок груза можно записать в виде матрицы

Затраты на перевозку груза от i-го поставщика j-му потребителю можно записать как произведение , тогда суммарные затраты на реализацию плана перевозок равны:

=

.

Цель задачи – минимизировать эти транспортные издержки.

Проверим условие баланса: суммарные потребности потребителей 180+140+190+120+170=800, суммарные запасы продукции всех поставщиков 300+280+220=800. Суммарные потребности потребителей равны суммарным запасам продукции всех поставщиков. Т. е. имеем закрытую задачу.

Опорный план находим методом минимальной стоимости. Ячейки с тарифом 0 заполняем в последнюю очередь. Наименьшим тарифом является 9.

	В1	В2	В3	В4	В5	запасы
А1	12 2	9	- 9	+ 10	10
А2		+ 15	-1	- 13	12
А3	-5	- 26	+ 12 -11	+ 17 -7
потребности

Записываем в левый нижний угол клетки А₁В₃ – 190 ед. продукции. Потребности полностью удовлетворены, столбец В₃ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 10. Записываем в левый нижний угол клетки А₁В₄ – 110 ед. продукции. Запасы полностью исчерпаны, строку А₁ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 13. Записываем в левый нижний угол клетки А₂В₁ – 180 ед. продукции. Потребности полностью удовлетворены, столбец В₁ вычеркиваем. Записываем в левый нижний угол клетки А₂В₄ – 10 ед. продукции. Потребности полностью удовлетворены, столбец В₄ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 15. Записываем в левый нижний угол клетки А₂В₂ – 90 ед. продукции. Запасы полностью исчерпаны, строку А₂ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 20. Записываем в левый нижний угол клетки А₃В₅ – 170 ед. продукции. Потребности полностью удовлетворены, столбец В₅ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 26. Записываем в левый нижний угол клетки А₃В₂ – 50 ед. продукции. Запасы полностью исчерпаны и потребности полностью удовлетворены. Строку А₃ и столбец В₂ вычеркиваем.

Число занятых клеток должно быть равно . В нашем случае число занятых клеток равно 7. Имеем не вырожденный план.

Проверим полученный опорный план на оптимальность. Находим потенциалы: и . Для каждой базисной переменной потенциалы удовлетворяют условию + = . Имеем систему:

Пусть =0, тогда =10

=3 =12

=14 9

10

6

Теперь для небазисных клеток найдем оценки . Оценки запишем в левый нижний угол. Так как среди оценок есть отрицательные, то план не оптимален. Наибольшая по модулю отрицательная оценка -11 стоит в ячейке А₃В₃. Ячейка А₃В₃ становится опорной, строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки «+» и «-», начиная с опорной клетки, которой присваиваем знак «+».

Выбираем наименьшее значение из клеток со знаком «-» : прибавляем 50 к значениям в клетках со знаком «+» и вычитаем 50 из значений в клетках со знаком

«-».

	В1	В2	В3	В4	В5	запасы
А1	+ 12 -9	-2	- 9		-1
А2	- 13	+ 15	10	11	12		-8
А3	-5	- 26	+ 12	4
потребности

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

Пусть =0, тогда =21

= -8 =23

=3 9

10

17

Теперь для небазисных клеток найдем оценки . Оценки запишем в левый нижний угол. Так как среди оценок есть отрицательные, то план не оптимален. Наибольшая по модулю отрицательная оценка -9 стоит в ячейке А₁В₁. Ячейка А₁В₁ становится опорной, строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки «+» и «-», начиная с опорной клетки, которой присваиваем знак «+».

Выбираем наименьшее значение из клеток со знаком «-» : прибавляем 40 к значениям в клетках со знаком «+» и вычитаем 40 из значений в клетках со знаком «-».

	В1	В2	В3	В4	В5	запасы
А1	12	7	- 9		+ 16 -1
А2			1	2	3
А3	4	9	+ 12	4	- 20
потребности

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

Пусть =0, тогда =12

=1 =14

=3 9

10

17

Теперь для небазисных клеток найдем оценки . Оценки запишем в левый нижний угол. Так как среди оценок есть отрицательные, то план не оптимален. Наибольшая по модулю отрицательная оценка -1 стоит в ячейке А₁В₅. Ячейка А₁В₅ становится опорной, строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки «+» и «-», начиная с опорной клетки, которой присваиваем знак «+».

Выбираем наименьшее значение из клеток со знаком «-» : прибавляем 140 к значениям в клетках со знаком «+» и вычитаем 140 из значений в клетках со знаком «-».

	В1	В2	В3	В4	В5	запасы
А1	12	7	1
А2			2	2	4
А3	3	8		3
потребности

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

Пусть =0, тогда =12

=1 =14

=4 8

10

16

Так как среди оценок для небазисных клеток нет отрицательных, то план оптимален.

Итак, 1-ый поставщик отправляет 40 тонн груза первому потребителю, 120 тонн груза четвертому потребителю и 140 тонн груза пятому потребителю.

2-ой поставщик отправляет 140 тонн груза первому потребителю и 140 тонн груза второму потребителю.

3-ий поставщик отправляет 190 тонн груза третьему потребителю и 30 тонн груза пятому потребителю.

Суммарные затраты при этом 10720 тонн-километров.

№ 3

=250; =200; =150;

=180; =120; =90; =105; =105; .

Решение.

Объем продукции доставленный от поставщика потребителю зададим переменной . Тогда план перевозок груза можно записать в виде матрицы

Затраты на перевозку груза от i-го поставщика j-му потребителю можно записать как произведение , тогда суммарные затраты на реализацию плана перевозок равны:

=

.

Цель задачи – минимизировать эти транспортные издержки.

Проверим условие баланса: суммарные потребности потребителей 180+120+90+105+105=600, суммарные запасы продукции всех поставщиков 250+200+150=600. Суммарные потребности потребителей равны суммарным запасам продукции всех поставщиков. Т. е. имеем закрытую задачу.

Опорный план находим методом минимальной стоимости. Ячейки с тарифом 0 заполняем в последнюю очередь. Наименьшим тарифом является 4.

	В1	В2	В3	В4	В5	запасы
А1	12	5	7		7
А2	- 13		+ 15	2	12
А3	+ 19 -5	1	- 26	-5
потребности

Записываем в левый нижний угол клетки А₂В₂ – 120 ед. продукции. Потребности полностью удовлетворены, столбец В₂ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 10. Записываем в левый нижний угол клетки А₁В₄ – 105 ед. продукции. Потребности полностью удовлетворены, столбец В₄ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 12. Записываем в левый нижний угол клетки А₁В₁ – 145 ед. продукции. Запасы полностью исчерпаны, строку А₁ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 13. Записываем в левый нижний угол клетки А₂В₁ – 35 ед. продукции. Потребности полностью удовлетворены, столбец В₁ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 15. Записываем в левый нижний угол клетки А₂В₃ – 45 ед. продукции. Запасы полностью исчерпаны, строку А₂ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 20. Записываем в левый нижний угол клетки А₃В₅ – 105 ед. продукции. Потребности полностью удовлетворены, столбец В₅ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 26. Записываем в левый нижний угол клетки А₃В₃ – 45 ед. продукции. Потребности полностью удовлетворены и запасы исчерпаны, столбец В₃ и строку А₃ вычеркиваем.

Число занятых клеток должно быть равно . В нашем случае число занятых клеток равно 7. Имеем не вырожденный план.

Проверим полученный опорный план на оптимальность. Находим потенциалы: и . Для каждой базисной переменной потенциалы удовлетворяют условию + = . Имеем систему:

Пусть =0, тогда =12

=1 =3

=12 14

10

8

Теперь для небазисных клеток найдем оценки . Оценки запишем в левый нижний угол. Так как среди оценок есть отрицательные, то план не оптимален. Наибольшая по модулю отрицательная оценка -5 стоит в ячейке А₃В₁. Ячейка А₃В₁ становится опорной, строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки «+» и «-», начиная с опорной клетки, которой присваиваем знак «+».

Выбираем наименьшее значение из клеток со знаком «-» : прибавляем 35 к значениям в клетках со знаком «+» и вычитаем 35 из значений в клетках со знаком «-».

	В1	В2	В3	В4	В5	запасы
А1	12	5	2		2
А2	5			7	12		-4
А3		1		0
потребности

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

Пусть =0, тогда =12

=-4 =8

=7 19

10

13

Так как среди оценок для небазисных клеток нет отрицательных, то план оптимален.

Итак, 1-ый поставщик отправляет 145 тонн груза первому потребителю и 105 тонн груза четвертому потребителю.

2-ой поставщик отправляет 120 тонн груза второму потребителю и 80 тонн груза третьему потребителю.

3-ий поставщик отправляет 35 тонн груза первому потребителю, 10 тонн груза третьему потребителю и 105 тонн груза пятому потребителю.

Суммарные затраты при этом 7495 тонн-километров.

№ 4

=400; =250; =350;

=200; =170; =230; =225; =175; .

Решение.

Объем продукции доставленный от поставщика потребителю зададим переменной . Тогда план перевозок груза можно записать в виде матрицы

Затраты на перевозку груза от i-го поставщика j-му потребителю можно записать как произведение , тогда суммарные затраты на реализацию плана перевозок равны:

=

.

Цель задачи – минимизировать эти транспортные издержки.

Проверим условие баланса: суммарные потребности потребителей 200+170+230+225+175=1000, суммарные запасы продукции всех поставщиков 400+250+350=1000. Суммарные потребности потребителей равны суммарным запасам продукции всех поставщиков. Т. е. имеем закрытую задачу.

Опорный план находим методом минимальной стоимости. Ячейки с тарифом 0 заполняем в последнюю очередь. Наименьшим тарифом является 5.

	В1	В2	В3	В4	В5	запасы
А1	13 0	5			3
А2			6	2	7
А3		6	1
потребности

Записываем в левый нижний угол клетки А₁В₃ – 230 ед. продукции. Потребности полностью удовлетворены, столбец В₃ вычеркиваем. Записываем в левый нижний угол клетки А₂В₂ – 170 ед. продукции. Потребности полностью удовлетворены, столбец В₂ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 11. Записываем в левый нижний угол клетки А₁В₄ – 170 ед. продукции. Запасы полностью исчерпаны, строку А₁ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 14. Записываем в левый нижний угол клетки А₂В₁ – 80 ед. продукции. Запасы полностью исчерпаны, строку А₂ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 18. Записываем в левый нижний угол клетки А₃В₄ – 55 ед. продукции. Потребности полностью удовлетворены, столбец В₄ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 20. Записываем в левый нижний угол клетки А₃В₁ – 120 ед. продукции. Потребности полностью удовлетворены, столбец В₁ вычеркиваем.

Из оставшихся ячеек наименьшим является тариф 21. Записываем в левый нижний угол клетки А₃В₅ – 175 ед. продукции. Потребности полностью удовлетворены и запасы исчерпаны, столбец В₅ и строку А₃ вычеркиваем.

Число занятых клеток должно быть равно . В нашем случае число занятых клеток равно 7. Имеем не вырожденный план.

Проверим полученный опорный план на оптимальность. Находим потенциалы: и . Для каждой базисной переменной потенциалы удовлетворяют условию + = . Имеем систему:

Пусть =0, тогда =13

=1 =4

=7 5

11

14.

Теперь для небазисных клеток найдем оценки . Оценки запишем в левый нижний угол. Так как среди оценок нет отрицательных, то план оптимален.

Итак, 1-ый поставщик отправляет 230 тонн груза третьему потребителю и 170 тонн груза четвертому потребителю.

2-ой поставщик отправляет 80 тонн груза первому потребителю и 170 тонн груза второму потребителю.

3-ий поставщик отправляет 120 тонн груза первому потребителю, 55 тонн груза четвертому потребителю и 175 тонн груза пятому потребителю.

Суммарные затраты при этом 12055 тонн-километров.

№ 5

=150; =200; =150;

=160; =70; =90; =80; =100; .

Решение.

Объем продукции доставленный от поставщика потребителю зададим переменной . Тогда план перевозок груза можно записать в виде матрицы

Дата добавления: 2015-07-14