Имеющих некоторые усложнения в их постановке

1. При некоторых реальных условиях перевозки груза из определенного пункта A_i в пункт назначения B_j не могут быть осуществлены. Для определения оптимальных планов таких задач предполагают, что стоимость перевозки единицы груза из пункта A_i в пункт B_j является сколь угодно большой величиной М и при этом условии известными методами находят решение ТЗ. Такой подход к нахождению решения ТЗ называется запрещением перевозок.

2. В отдельных ТЗ дополнительным условием является обеспечение перевозки по соответствующим маршрутам определенного количества груза. Пусть, например, из A_i в B_j требуется обязательно перевезти α _ij единиц груза. Тогда в соответствующую клетку таблицы, находящуюся на пересечении строки A_i и столбца B_j, записывают указанное число α _ij и в дальнейшем считают эту клетку свободной со сколь угодно большой стоимостью перевозки М. Для полученной таким образом новой ТЗ находят оптимальный план, который определяет оптимальный план исходной задачи.

3. Иногда требуется найти решение ТЗ, при котором из A_i в B_j должно быть перевезено не менее заданного количества груза α _ij. Для определения оптимального плана такой задачи считают, что запасы A_i и потребности B_j меньше фактических на α _ij единиц. После этого находят оптимальный план новой ТЗ, на основании которого и определяют решение исходной задачи.

Примечание: При целых a_i (i = 1,..., m) и b_j (j = 1,..., n), в силу специфики ограничений ТЗ, любое базисное допустимое решение является целочисленным.

Домашнее задание №17

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

1.Составить оптимальное распределение специалистов четырех профилей, имеющихся в количествах 60, 30, 45, 25 между пятью видами работ, потребности в специалистах для каждой работы соответственно равны 20, 40, 25, 45, 30 и матрица

7 5 2 0 4

4 0 8 6 3

С =

5 6 0 9 8

6 4 5 7 6

характеризует эффективность использования специалиста на данной работе.

2. Выпуск продукции на трех заводах составляет 500, 700 и 600, причем затраты на производство единицы равны 9, 8 и 2 соответственно. Потребности четырех потребителей на эту продукцию составляют 350, 200, 450 и 100. Матрица С транспортных расходов на доставку единицы продукции с i - го завода j - му потребителю:

3 4 6 1

C = 5 1 2 3

4 5 8 1

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

3. Строительный песок добывается в трех карьерах с производительностью за день 46, 34 и 40 т. и затратами на добычу одной тонны 1, 2 и 3 руб. соответственно; песок доставляется на четыре строительные площадки, потребность которых составляет 40, 35, 30, 45 т. Транспортные расходы на перевозку одной тонны песка заданы матрицей:

4 3 2 5

C = 1 1 6 4

3 5 9 4

Недостающее количество песка - 30 т. в день можно обеспечить двумя путями: увеличением производительности а) 1 - го карьера, что повлечет дополнительные затраты в 3 руб. на добычу 1 т.; б) 2 - го с дополнительными затратами в 2 руб. / т.

Определить оптимальный план закрепления строительных площадок за карьерами и оптимальный вариант расширения поставок песка.

4.Имеется три сорта бумаги в количествах 10, 8 и 5 т., которую необходимо использовать на издание четырех книг тиражом в 8000, 6000, 15000 и 10000 экз. Расход бумаги на одну книгу составляет 0,6; 0,8; 0,4 и 0,5 кг,а себестоимость (в коп.) печатания книги при использовании i - го сорта бумаги задается матрицей:

24 16 32 25

C = 8 24 24 20

30 24 16 20

Определить оптимальное распределение бумажных ресурсов.

5. Четыре ремонтные мастерские могут за год отремонтировать соответственно 700, 500, 450 и 550 машин при себестоимости ремонта одной машины в 500, 700, 650 и 600 рублей. Планируется годовая потребность в ремонте пяти автобаз: 350, 350, 300, 300 и 200 машин.

Избыточные мощности 1-й и 2-й мастерских могут быть использованы для обслуживания других видов работ.

Дана матрица

40 20 60 10 20

Cij = 10 80 30 40 30

70 30 30 50 10

50 10 40 50 40,

характеризующая транспортные расходы на доставку машины с j-й автобазы в i-ю ремонтную мастерскую. Определить минимальную годовую потребность в кредитах на выполнение указанного объема ремонтных работ по всем автобазам. Составить программу ремонтных работ, имеющую минимальную стоимость.

6.Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А1 в В 2 и из А 3 в В 5 перевозки не могут быть осуществлены, а из А2 в В4 будет завезено 60 единиц груза.

Пункты	Пункты назначения	Запасы
Отправления	В1	В2	В3	В4	В5
А1
А2
А3
Потребности

7. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А2 в В4 и из А 3 в В 1 перевозки не могут быть осуществлены, а из А 4 в В 2 будет завезено 40 единиц груза.

Пункты	Пункты назначения	Запасы
Отправления	В1	В2	В3	В4	В5
А1
А2
А3
Потребности

8. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А 3 в В 2 и из А 4 в В 5 перевозки не могут быть осуществлены, а из А1 в В 3 будет завезено 35 единиц груза.

Пункты	Пункты назначения	Запасы
Отправления	В1	В2	В3	В4	В5
А1
А2
А3
Потребности

9. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А1 в В 2 и из А2 в В5 перевозки не могут быть осуществлены, а из А2 в В4 будет завезено 45 единиц груза.

Пункты	Пункты назначения	Запасы
Отправления	В1	В2	В3	В4	В5
А1
А2
А3
Потребности

10.Найти решение транспортной задачи, исходные данные которой приведены в табл., при дополнительных условиях: из А1 и В1 и из А2 и В5 перевозки не могут быть осуществлены, а из А2 и В1 будет завезено 60 единиц груза.

Пункты отправления	Пункты назначения	Запасы
	В1 В2 В3 В4 В5
А1	1 2 3 1 4
А2	6 3 4 5 2
А3	8 2 1 9 3
Потребности	120 80 160 90 50

11.Составить оптимальное распределение специалистов четырех профилей, имеющихся в количествах 50, 40, 45, 35 между пятью видами работ, потребности в специалистах для каждой работы соответственно равны 30, 30, 45, 25, 30 и матрица

3 5 9 0 4

4 0 7 6 3

С =

6 6 0 5 8

6 4 5 9 6

характеризует эффективность использования специалиста на данной работе.

12. Выпуск продукции на трех заводах составляет 600, 700 и 500, причем затраты на производство единицы равны 8, 6 и 3 соответственно. Потребности четырех потребителей на эту продукцию составляют 450, 300, 150 и 100. Матрица С транспортных расходов на доставку единицы продукции с i - го завода j -му потребителю:

2 5 6 4

C = 5 7 2 3

4 5 8 1

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

13. Строительный песок добывается в трех карьерах с производительностью за день 56, 44 и 50 т. и затратами на добычу одной тонны 1, 2 и 3 руб. соответственно; песок доставляется на четыре строительные площадки, потребность которых составляет 60, 25, 20, 25 т. Транспортные расходы на перевозку одной тонны песка заданы матрицей:

5 2 2 7

C = 1 2 6 4

3 5 8 4

Недостающее количество песка можно обеспечить двумя путями: увеличением производительности а) 1 - го карьера, что повлечет дополнительные затраты в 2 руб. на добычу 1 т.; б) 2 - го с дополнительными затратами в 1 руб. / т.

Определить оптимальный план закрепления строительных площадок за карьерами и оптимальный вариант расширения поставок песка.

14.Имеется три сорта бумаги в количествах 10, 9 и 6 т., которую необходимо использовать на издание четырех книг тиражом в 6000, 5000, 13000 и 11000 экз. Расход бумаги на одну книгу составляет 0,5; 0,8; 0,7 и 0,5 кг,а себестоимость (в коп.) печатания книги при использовании i - го сорта бумаги задается матрицей:

14 26 32 25

C = 8 34 24 20

20 24 16 20

Определить оптимальное распределение бумажных ресурсов.

15. Четыре ремонтные мастерские могут за год отремонтировать соответственно 800, 600, 350 и 450 машин при себестоимости ремонта одной машины в 600, 700, 650 и 500 рублей. Планируется годовая потребность в ремонте пяти автобаз: 350, 450, 100, 400 и 200 машин.

Избыточные мощности 1-й и 2-й мастерских могут быть использованы для обслуживания других видов работ.

Дана матрица

50 20 60 10 20

Cij = 10 70 30 40 10

70 30 30 50 10

50 10 20 50 40,

характеризующая транспортные расходы на доставку машины с j-й автобазы в i-ю ремонтную мастерскую. Определить минимальную годовую потребность в кредитах на выполнение указанного объема ремонтных работ по всем автобазам. Составить программу ремонтных работ, имеющую минимальную стоимость.

16.Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А1 в В 2 и из А 3 в В 5 перевозки не могут быть осуществлены, а из А2 в В4 будет завезено 50 единиц груза.

Пункты	Пункты назначения	Запасы
Отправления	В1	В2	В3	В4	В5
А1
А2
А3
Потребности

17. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А2 в В4 и из А 3 в В 1 перевозки не могут быть осуществлены, а из А 4 в В 2 будет завезено 40 единиц груза.

Пункты	Пункты назначения	Запасы
Отправления	В1	В2	В3	В4	В5
А1
А2
А3
Потребности

18. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А 3 в В 2 и из А 4 в В 5 перевозки не могут быть осуществлены, а из А1 в В 3 будет завезено 45 единиц груза.

Пункты	Пункты назначения	Запасы
Отправления	В1	В2	В3	В4	В5
А1
А2
А3
Потребности

19. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А1 в В 2 и из А2 в В5 перевозки не могут быть осуществлены, а из А2 в В4 будет завезено 40 единиц груза.

Пункты	Пункты назначения	Запасы
Отправления	В1	В2	В3	В4	В5
А1
А2
А3
Потребности

20.Найти решение транспортной задачи, исходные данные которой приведены в табл., при дополнительных условиях: из А1 и В1 и из А2 и В5 перевозки не могут быть осуществлены, а из А2 и В1 будет завезено 50 единиц груза.

Пункты отправления	Пункты назначения	Запасы
	В1 В2 В3 В4 В5
А1	2 3 3 1 4
А2	6 3 4 5 2
А3	8 2 1 9 4
Потребности	110 80 160 90 60

21.Составить оптимальное распределение специалистов четырех профилей, имеющихся в количествах 360, 40, 45, 35 между пятью видами работ, потребности в специалистах для каждой работы соответственно равны 20, 40, 35, 35, 30 и матрица

9 7 2 0 5

4 0 6 6 3

С =

3 6 0 7 8

6 4 5 7 6

характеризует эффективность использования специалиста на данной работе.

22. Выпуск продукции на трех заводах составляет 600, 500 и 600, причем затраты на производство единицы равны 11, 7 и 4 соответственно. Потребности четырех потребителей на эту продукцию составляют 450, 100, 450 и 100. Матрица С транспортных расходов на доставку единицы продукции с i - го завода j - му потребителю:

2 5 6 1

C = 7 1 2 3

4 4 8 1

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

23. Строительный песок добывается в трех карьерах с производительностью за день 47, 35 и 50 т. и затратами на добычу одной тонны 1, 2 и 3 руб. соответственно; песок доставляется на четыре строительные площадки, потребность которых составляет 50, 25, 30, 45 т. Транспортные расходы на перевозку одной тонны песка заданы матрицей:

7 4 2 5

C = 1 2 5 4

3 5 9 4

Недостающее количество песка можно обеспечить двумя путями: увеличением производительности а) 1 - го карьера, что повлечет дополнительные затраты в 3 руб. на добычу 1 т.; б) 2 - го с дополнительными затратами в 2 руб. / т.

Определить оптимальный план закрепления строительных площадок за карьерами и оптимальный вариант расширения поставок песка.

24.Имеется три сорта бумаги в количествах 11, 9 и 5 т., которую необходимо использовать на издание четырех книг тиражом в 9000, 5000, 10000 и 12000 экз. Расход бумаги на одну книгу составляет 0,5; 0,8; 0,3 и 0,5 кг,а себестоимость (в коп.) печатания книги при использовании i - го сорта бумаги задается матрицей:

20 16 30 25

C = 15 25 24 30

30 20 16 20

Определить оптимальное распределение бумажных ресурсов.

25. Четыре ремонтные мастерские могут за год отремонтировать соответственно 600, 500, 350 и 550 машин при себестоимости ремонта одной машины в 300, 600, 650 и 500 рублей. Планируется годовая потребность в ремонте пяти автобаз: 450, 350, 200, 300 и 200 машин.

Избыточные мощности 1-й и 2-й мастерских могут быть использованы для обслуживания других видов работ.

Дана матрица

30 10 50 10 20

Cij = 10 70 30 40 30

50 30 20 50 10

50 20 40 50 40,

характеризующая транспортные расходы на доставку машины с j-й автобазы в i-ю ремонтную мастерскую. Определить минимальную годовую потребность в кредитах на выполнение указанного объема ремонтных работ по всем автобазам. Составить программу ремонтных работ, имеющую минимальную стоимость.