а) и б) упражнения 15.
Тема 6
1. Рассмотрите задачу коммивояжера с пятью городами, но допустите, что
коммивояжер должен вернуться в город 1, побывав в двух других городах, а
затем посетить два оставшихся города. Определите число возможных
последовательностей.
2. Определите число возможных последовательностей обработки трех
деталей на одном станке, трех деталей на двух станках, двух деталей на трех
станках, двух деталей на четырех станках. Покажите, как изменится результат,
если детали должны обрабатываться в одном и том же порядке на каждом
станке.
3. Рассмотрите задачу выбора номенклатуры продукции на одном
интервале времени, в которой каждой операции х
j
, j = 1, 2,..., n, соответствуют
затраты К
j
на подготовку производства. Подсчитайте, сколько различных
вариантов подготовки производства существует (предполагая, что равенство
всех х
j
нулю является одной из возможностей).
4. Рассмотрите ограничение х
1
+ х
2
+ х
3
+ … + х
п
= N, где любая величина х
j
должна быть неотрицательным целым. Определите число различных
допустимых решений при следующих условиях:
n = 6, N = 1; n = 7, N = 1; n = 6, N = 2; n = 6, N = 6; n = 7, N = 6; n = 6, N = 6
и ограничение задано в виде неравенства ≤; п = 6, N = 1 и ограничение задано
в виде неравенства ≤; п = 6, N = 2 и ограничение задано в виде неравенства ≤.
5. Рассмотрите задачу распределения капиталовложений, в которой
фигурируют 3 группы проектов. В группе 1 имеется восемь проектов и нужно
выбрать два, в группе 2 — десять проектов и нужно выбрать четыре, в группе
3 — семь проектов и нужно выбрать пять. Определите общее число
возможных комбинаций выбора проектов. Покажите, как изменится это число,
если заданное число проектов, выбираемых в каждой группе, является лишь
верхней оценкой допустимого выбора.
148