Тесты. Транспортные задачи

Заявки Запасы

1. Критерий оптимизации транспортной задачи:

а) минимум затрат на продукцию;

б) удовлетворение всех затрат потребителей;

в) максимум прибыли;

г) минимум затрат на доставку продукции.

2. Необходимое и достаточное условие решения транспортной задачи в области допустимых решений:

а) сумма запасов больше суммы заявок;

б) количество пунктов запаса равно количеству пунктов потребителей;

в) сумма запасов равна сумме заявок;

г) ацикличность.

3. Транспортная задача

Заявки Запасы		300+в
к+в

закрыта при к равном: а) 100; б) 300; в) 600; г) 400.

4. В транспортной задаче m поставщиков n потребителей, тогда число переменных равно:

а) m + n; б) m × n; в) m + n - 1; г) n.

5. Если в транспортной задаче, то для ее решения следует ввести: а) фиктивного поставщика; б) фиктивного потребителя;

в) фиктивного поставщика и потребителя; г) с_ij=0.

6. В транспортной задаче m поставщиков и n потребителей, тогда ограничения по запасам:

а) ; б) ;

в) ;

г) .

7. В транспортной задаче (m поставщиков и n потребителей) вводят фиктивного поставщика, если:

а) ; б) ;

в) ; г) .

8. В транспортной задаче (m поставщиков и n потребителей) вводят фиктивного потребителя, если:

а) ; б) ;

в) ; г) .

9. Если в транспортной задаче (m поставщиков и n потребителей) ограничения по потребностям имеют вид , то:

а) суммарных запасов больше, чем суммарных потребностей;

б) суммарных запасов меньше, чем суммарных потребностей;

в) суммарных запасов не меньше, чем суммарных потребностей;

г) суммарных запасов не больше, чем суммарных потребностей.

10. В транспортной задаче (m – число поставщиков n – число потребителей) ранг системы ограничений равен:

а) m + n; б) m × n; в) m + n - 1; г) n.

11. Опорное решение системы ограничений транспортной задачи должно иметь базисных переменных:

а) m + n; б) m + n - 1; в) m × n; г) mn - 1.

12. Особенности системы ограничений математической модели закрытой транспортной задачи:

а) коэффициенты при всех неизвестных по 1;

б) каждая переменная встречается только в двух уравнениях;

в) система уравнений транспортной задачи симметрична относительно всех переменных ;

г) матрица, составленная из коэффициентов при переменных , состоит из единиц и нулей, причем каждый столбец матрицы содержит два элемента равных 1, а остальные – 0;

д) все ответы верны;

13. Метод нахождения оптимального плана закрытой транспортной задачи:

а) Фогеля; б) северо-западного угла;

в) потенциалов; г) минимального элемента.

14. Опорный план закрытой транспортной задачи содержит свободных переменных:

а) m + n - 1; б) mn - 1; в) mn; г) mn - (m + n - 1).

15. Математическая модель, соответствующая транспортной таблице

Заявки Запасы

имеет вид:

а)

б)

в)

г) .

16. Математической модели транспортной задачи

соответствует транспортная таблица:

а)

б)

Заявки Запасы

в)

Заявки Запасы

г) а, в – верно; д) б, в – верно.

17. Количество занятых клеток поставщиками в оптимальном плане транспортной задачи (m поставщиков и n потребителей) равно:

а) m + n; б) m × n; в) m + n - 1; г) количеству поставщиков.

18. Условия оптимальности плана закрытой транспортной задачи:

а) сумма платежей за доставку единицы груза не больше тарифа в свободных клетках транспортной таблицы;

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

в) сумма платежей за доставку единицы груза равна тарифу в занятых и не больше в свободных клетках транспортной таблицы;

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

19. План транспортной задачи (m поставщиков и n потребителей) оптимальный, если в транспортной таблице:

а)

б)

в)

г)

20. Цикл транспортной таблицы (m поставщиков и n потребителей) в закрытой транспортной задаче -

а) замкнутая ломаная, вершины которой в занятых клетках;

б) замкнутая ломанная, в вершинах которой поворот на 90^o;

в) замкнутая ломанная, с вершинами в занятых клетках, в которых совершается поворот на 90^o;

г) нет верного ответа.

21. Цикл перепоставки необходим в транспортной задаче (m поставщиков и n потребителей), если:

а) переплата в свободных клетках;

б) занято поставками клеток m + n -1;

в) ; г) .

22. В транспортной задаче на сети из n пунктов количество базисных ребер равно:

а) m + n; б) m + n - 1; в) (n - 1)(m - 1); г) n - 1.

23. План поставок в транспортной таблице

Заявки Запасы				u_i




v_j

является: а) оптимальным; б) вырожденным;

в) опорным; г) недопустимым.

24. По заданным в таблице значениям потенциалов

Заявки Запасы	u_i




		-2

v_j

опорное решение равно: а) ; б) ;

в) ; г) .

25. В транспортной задаче на сети цикл перепоставок строится по ребрам:

а) свободным; б) базисным; в) занятым;

г) б, в – верно; д) а,б – верно.

26. В транспортной задаче на сети (m поставщиков и n потребителей) решение оптимально, если оценки свободных ребер:

а) больше 0; б) не больше 0; в) меньше 0; г) равны 0.

27. Необходимое условие разрешимости транспортной задачи (m поставщиков и n потребителей) с ограничениями на пропускную способность:

а) б)

в) г)

28. Достаточное условие разрешимости транспортной задачи (m поставщиков и n потребителей) с ограничениями на пропускную способность:

а) б)

в) ;

г) существование хотя бы одного допустимого решения.

29. Для оптимального решения транспортной задачи с ограничениями на пропускную способность необходимо и достаточно существование потенциалов u_i (i= ) и v_j (j= ) таких, что выполняются условия

для клеток:

а)

б)

в)

г)

30. Оптимальный план транспортной задачи

Заявки Запасы	u_i


		-2

		-1

v_j

равен:

а) ; б) ; в) .

ПРАКТИКУМ

Задание 1. Составить базу данных ТЗ, состоящей из четырех пунктов производства с а_i количеством запаса, пяти пунктов потребления с b _j количеством заявок и C_ij транспортными расходами на перевозку из A_i пункта отправления в B_j пункт назначения.

Составить математическую модель ТЗ, двойственную к ней. Решить исходную ТЗ вручную методом потенциалов. Объяснить экономический смысл двойственных оценок.

Задание 2. Пиломатериал (a_i) необходимо перевезти с трех разных баз четырем клиентам (b_j) с минимальными затратами на доставку, если известна стоимость доставки единицы груза – числитель от i –той базы j – тому клиенту и ограничения на пропускную способность транспортных средств - знаменатель . Решить задачу методом потенциалов.

Варианты заданий


b_j a_i					b_j a_i
	15/15	20/13	16/14	18/13		22/14	27/15	23/14	26/16
	32/13	45/16	30/17	32/15		30/15	29/16	28/17	30/16
	19/14	22/16	21/15	23/17		31/16	35/14	33/17	32/15


b_j a_i					b_j a_i
	17/13	19/13	21/14	18/15		20/14	25/15	23/14	24/16
	23/15	27/14	28/16	30/15		33/15	30/16	28/17	31/16
	29/15	32/16	30/15	33/16		32/16	33/14	30/17	31/15


b_j a_i					b_j a_i
	16/15	22/17	18/15	19/16		22/15	26/15	25/14	25/16
	30/13	45/16	30/17	30/15		25/15	28/16	27/17	31/16
	20/14	22/16	22/15	24/17		30/16	33/14	33/16	34/15

b_j a_i					b_j a_i
	13/15	18/16	20/17	15/19		20/15	26/14	21/17	25/16
	28/14	35/18	30/17	30/15		30/15	29/16	28/17	29/16
	17/13	21/16	20/15	24/17		31/16	35/14	30/17	33/13


b_j a_i					b_j a_i
	17/15	21/13	15/14	19/13		27/14	28/15	25/14	25/16
	32/14	47/16	30/17	33/15		31/15	30/16	28/16	30/16
	19/13	22/17	20/15	23/17		16/16	40/14	33/17	32/15


b_j a_i					b_j a_i
	13/15	19/13	16/13	18/13		19/14	27/16	23/14	26/17
	30/13	43/17	30/16	31/14		30/15	28/16	28/17	30/15
	25/18	21/16	21/17	23/16		31/16	35/14	33/19	32/13


b_j a_i					b_j a_i
	17/14	21/13	15/14	19/14		28/16	28/15	25/14	25/16
	32/12	47/16	31/17	32/15		31/14	29/16	28/16	30/16
	19/15	22/17	20/16	23/17		16/16	40/13	33/17	29/15


b_j a_i					b_j a_i
	13/14	19/13	15/14	19/13		27/14	28/15	23/4	25/7
	31/14	43/16	30/17	32/15		31/15	30/16	28/7	30/14
	19/13	22/17	20/15	21/18		16/16	40/15	33/16	32/13


b_j a_i					b_j a_i
	17/15	21/13	15/14	19/13		27/14	28/15	25/14	25/16
	32/14	47/16	30/17	33/15		31/15	30/16	28/16	30/16
	19/13	22/17	20/15	23/17		16/16	40/14	33/17	32/15

b_j a_i					b_j a_i
	20/15	21/12	23/14	21/17		30/14	28/15	21/14	25/16
	33/14	45/16	32/17	36/19		33/15	29/16	28/16	24/16
	21/17	25/15	26/19	25/21		16/20	40/15	33/22	32/15

МОДУЛЬ 6. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

Динамическое программирование – это метод, приспособленный для решения оптимизационных задач, связанных с многошаговыми, поэтапными процессами.

Многошаговый процесс можно интерпретировать так: весь цикл разбивается на этапы и на каждом этапе требуется принять то или иное решение.

При решении задач методом ДП вводят функцию Беллмана f_k, которая представляет собой максимальную эффективность многошагового процесса, состоящего из k шагов.

Для вычисления функции Беллмана составляется, так называемое, функциональное уравнение Беллмана, позволяющее находить значение функции Беллмана f_k₊₁, если известно f_k.

При выводе уравнения Беллмана используется та или иная форма принципа оптимальности. Одной из наиболее общих формулировок является: если на первом шаге принято решение, то дальнейшее решение принимается таким образом, чтобы за оставшееся число шагов достичь максимального (минимального) результата.