 |
 |
 |
 |
|
 |
 |
75
3.5. Что положено в основу метода потенциалов?
3.6. Из чего вытекает критерий оптимальности допустимого плана транспортной задачи?
3.7. Перечислите основные этапы метода потенциалов.
3.8. Какие условия должны быть соблюдены при построении цепочки преобразования плана в методе
потенциалов?
3.9. Что следует делать при возникновении ситуации вырожденности текущего плана в транспортной
задаче?
3.10. Приведите формулировку линейной сетевой задачи.
3.11. Покажите, что транспортная задача в матричной постановке является частным случаем
транспортной задачи в сетевой постановке.
3.12. Дайте определение понятия «остов сети». Какая связь существует между остовом сети и
базисом транспортной задачи в сетевой постановке?
3.13. Какой поток называют невырожденным?
3.14. Перечислите основные этапы метода потенциалов для транспортной задачи в сетевой
постановке.
3.15. Каким способом можно получить допустимый поток в транспортной сети?
3.16. В чем состоит задача о кратчайшем пути?
3.17. Перечислите основные этапы метода Минти.
ГЛАВА 4. ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ
4.1. ТИПЫ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ
4.1.1. Основные понятия. Многие экономические задачи характеризуются тем, что объемы
управляемых ресурсов (в силу тех или иных объективных свойств) могут принимать только целые
значения. Математическая формализация данных ситуаций приводит к моделям дискретного
программирования. В общем виде задача дискретного программирования может быть сформулирована
как задача нахождения максимума (или минимума) целевой функции
f(x1, x2,...,x
n
) на множестве
D,
определяемом системой ограничений
где
?
— некоторое конечное, или счетное*, множество. Условие х??. называется условием
дискретности. Особое место среди дискретных задач занимает целочисленная задача линейного
программирования в канонической форме (ЦКЗЛП):
* Напомним, что примерами счетных множеств являются множества натуральных, целых и рациональных чисел.
где Z
+
={0; 1; 2; ...} — множество неотрицательных целых чисел.
Заметим, что в некоторых ситуациях требование «целочисленности» может быть наложено лишь на
некоторые переменные x
j
, что кардинально не меняет характера задачи.