Тесты. Транспортные задачи
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 потребителей) в закрытой транспортной задаче -
а) замкнутая ломаная, вершины которой в занятых клетках;
б) замкнутая ломанная, в вершинах которой поворот на 90o;
в) замкнутая ломанная, с вершинами в занятых клетках, в которых совершается поворот на 90o;
г) нет верного ответа.
21. Цикл перепоставки необходим в транспортной задаче (m поставщиков и n потребителей), если:
а) переплата в свободных клетках;
б) занято поставками клеток m + n -1;
в) ; г) .
22. В транспортной задаче на сети из n пунктов количество базисных ребер равно:
а) m + n; б) m + n - 1; в) (n - 1)(m - 1); г) n - 1.
23. План поставок в транспортной таблице
Заявки Запасы | ui | ||||||
vj |
является: а) оптимальным; б) вырожденным;
в) опорным; г) недопустимым.
24. По заданным в таблице значениям потенциалов
Заявки Запасы | ui | ||||||
-2 | |||||||
vj |
опорное решение равно: а) ; б) ;
в) ; г) .
25. В транспортной задаче на сети цикл перепоставок строится по ребрам:
а) свободным; б) базисным; в) занятым;
г) б, в – верно; д) а,б – верно.
26. В транспортной задаче на сети (m поставщиков и n потребителей) решение оптимально, если оценки свободных ребер:
а) больше 0; б) не больше 0; в) меньше 0; г) равны 0.
27. Необходимое условие разрешимости транспортной задачи (m поставщиков и n потребителей) с ограничениями на пропускную способность:
а) б)
в) г)
28. Достаточное условие разрешимости транспортной задачи (m поставщиков и n потребителей) с ограничениями на пропускную способность:
а) б)
в) ;
г) существование хотя бы одного допустимого решения.
29. Для оптимального решения транспортной задачи с ограничениями на пропускную способность необходимо и достаточно существование потенциалов ui (i= ) и vj (j= ) таких, что выполняются условия
для клеток:
а)
б)
в)
г)
30. Оптимальный план транспортной задачи
Заявки Запасы | ui | ||||||
-2 | |||||||
-1 | |||||||
vj |
равен:
а) ; б) ; в) .
ПРАКТИКУМ
Задание 1. Составить базу данных ТЗ, состоящей из четырех пунктов производства с аi количеством запаса, пяти пунктов потребления с bj количеством заявок и Cij транспортными расходами на перевозку из Ai пункта отправления в Bj пункт назначения.
Составить математическую модель ТЗ, двойственную к ней. Решить исходную ТЗ вручную методом потенциалов. Объяснить экономический смысл двойственных оценок.
Задание 2.Пиломатериал (ai) необходимо перевезти с трех разных баз четырем клиентам (bj) с минимальными затратами на доставку, если известна стоимость доставки единицы груза – числитель от i –той базы j – тому клиенту и ограничения на пропускную способность транспортных средств - знаменатель . Решить задачу методом потенциалов.
Варианты заданий
bj ai | bj ai | |||||||||
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 |
bj ai | bj ai | |||||||||
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 |
bj ai | bj ai | |||||||||
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 | |||
bj ai | bj ai | |||||||||
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 |
bj ai | bj ai | |||||||||
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 |
bj ai | bj ai | |||||||||
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 |
bj ai | bj ai | |||||||||
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 |
bj ai | bj ai | |||||||||
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 |
bj ai | bj ai | |||||||||
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 | |||
bj ai | bj ai | |||||||||
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. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
В задачах динамического программирования находится ряд оптимальных решений последовательно для каждого этапа, обеспечивающих оптимальное развитие всего процесса в целом.
Динамическое программирование – это метод, приспособленный для решения оптимизационных задач, связанных с многошаговыми, поэтапными процессами.
Многошаговый процесс можно интерпретировать так: весь цикл разбивается на этапы и на каждом этапе требуется принять то или иное решение.
При решении задач методом ДП вводят функцию Беллмана fk, которая представляет собой максимальную эффективность многошагового процесса, состоящего из k шагов.
Для вычисления функции Беллмана составляется, так называемое, функциональное уравнение Беллмана, позволяющее находить значение функции Беллмана fk+1, если известно fk.
При выводе уравнения Беллмана используется та или иная форма принципа оптимальности. Одной из наиболее общих формулировок является: если на первом шаге принято решение, то дальнейшее решение принимается таким образом, чтобы за оставшееся число шагов достичь максимального (минимального) результата.