СодержаниеВведение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1 Теоретическая часть. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1 Метод частичного (неявного) перебора. . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.1 Основные понятия . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .6
1.1.2 Алгоритм частичного перебора . . . . . . . . . . . . . . . . . . . . . . . . . . . .10
1.2 Алгоритм частичного перебора для нелинейной задачи . . . . . . . . .11
2 Практическая часть . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14
2.1 Постановка задачи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14
2.2 Решение задачи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19
Список используемой литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Приложения А . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21
Приложение Б . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28ВведениеИсследование операций – это наука, занимающаяся разработкой и практическим применением методов наиболее эффективного (или оптимального) управления организационными системами.
Предмет исследование операций – это системы организационного управления (организации), которые состоят из большого числа взаимодействующих между собой подразделений, причем интересы подразделений не всегда согласуются между собой и могут быть противоположны.
Целью исследования операций является количественное обоснование принимаемых решений по управлению организациями.
Решение, которое оказывается наиболее выгодным для всей организации, называется оптимальным, а решение, наиболее выгодное одному или нескольким подразделениям, будет субоптимальным.
Модели целочисленного программирования находят ограничительное применение на практике. Одна из причин, объясняющая такое положение, заключается в том, что в моделях целочисленного программирования часто не учитываются некоторые важные условия. Другая причина – вычислительные трудности, т.е. затраты, связанные с получением решений для моделей реальной размерности, превышают эффект, достигаемый за счет реализации найденного решения.
Еще одна особенность, свойственная задачам целочисленного программирования, заключается в том, что нет простого способа позволяющего определить, является ли данное допустимое решение оптимальным. В этом одно из важных отличительных различий между задачами целочисленного и линейного программирования.
Практический опыт реализации алгоритма частичного перебора (при условии его надлежащей модификации путем добавления сложных составных ограничений и при разработке эффективной программы для быстродействующей ЭВМ) показывает, что с его помощью можно решать некоторые практические задачи, содержащие до 100 переменных и до 50 ограничений. Такая размерность задач выглядит весьма скромной по сравнению с имеющейся возможностью решения задач линейного программирования, включающих несколько сотен переменны и ограничений. Однако наблюдается бурный прогресс в разработке методов решения целочисленных задач. Поэтому в ближайшем будущем можно ожидать, что удастся решать целочисленные задачи, также содержащие несколько сотен переменных.Литература1. Вагнер Г. Основы исследования операций, том2, М: Мир, 1973г., 488с.
2. Зайченко Ю.П. Исследования операций, Высшая школа, 1975г., 319с.
3. Зайченко Ю.П., Шумилова С.А. Исследования операций, Высшая школа, 1984г., 224с.
|
