Типы задач дискретного программирования

из "Математические исследования операций в экономике "

Как нетрудно заметить, представленная математическая модель носит универсальный характер, и к ней могут быть сведены многие экономические задачи. Ярким подтверждением этому служит и тот факт, что в литературе она также известна как задача о загрузке судна. [c.139]
Каждый такой маршрут можно отождествить с перестановкой п чисел (упорядоченной выборкой из п элементов по п). В свою очередь, таким перестановкам взаимно однозначно соответствуют матрицы X, у которых в каждой строке и каждом столбце содержится точно одна единица. [c.140]
Отдельно следует остановиться на том, что задача коммивояжера имеет большое количество содержательных аналогов. Скажем, к аналогичной модели приведет задача разработки графика переналадки оборудования, которое может выпускать разные типы изделий, но требует определенных затрат (временных или материальных) при переходе с одного технологического режима на другой. [c.141]
Действительно, если уц =0, то переменные /,, =0, а при уч= неравенства (4.15) становятся несущественными, поскольку они и так справедливы для любого опорного плана. Следовательно, задача (4.16) эквивалентна исходной задаче (4.13). В силу характера ограничений (4.14)-(4.15) задача (4.16) является задачей частично-целочисленного программирования. [c.142]
Перечисленные примеры далеко не исчерпывают всего многообразия задач дискретного программирования. Однако более подробное их рассмотрение требует привлечения достаточно сложного математического аппарата и выходит за рамки данной книги. [c.142]
В последующих параграфах мы остановимся на способах решения наиболее известных и хорошо изученных дискретных задач. Излагаемые ниже методы не имеют универсального характера, с каждым из них связаны определенные ограничения и, соответственно, ответ на вопрос о выборе того или иного из них зависит от конкретных особенностей решаемой задачи. Более того, цель изложения состоит в том, чтобы создать у читателя общие представления об основных идеях и подходах, не углубляясь далеко в вычислительные и математические тонкости, которыми буквально изобилуют алгоритмы дискретного программирования. Заметим также, что достаточно эффективный и широко применяемый подход к решению целочисленных задач основан на сведении их к задачам транспортного типа. Это объясняется тем, что если в условиях транспортной задачи значения запасов (а,.) и потребностей ( .) являются целочисленными, то целочисленным будет и оптимальный план. [c.142]

Вернуться к основной статье