Курсовая на тему: Постановка и методы решения задач целочисленного линейного программирования.
Курсовая на тему: Постановка и методы решения задач целочисленного линейного программирования.
Фрагменты работы:
Клиентские онлайн игры стрелялки — для тех кто любит поиграть.
Содержание
Введение………………………………………………………………….. 3
1. Математическая постановка задачи целочисленного
программирова-ния…………………………………………………………… 4
2. Методы решения задач линейного целочисленного программирова-ния………………………………………………………………………….. 8
2.1 Решение задач целочисленного программирования графическим
методом……………………………………………………………………. 8
2.2 Решение задач линейного целочисленного программирования ме-тодами отсечения…………………………………………………………. 9
2.3 Решения задачи целочисленного программирования методом вет-вей и границ ……………………………………………………… 12
3. Практическая реализация методов решения задачи линейного цело-численного программирования 14
Заключение…………………………………………………………………. 20
Литература…………………………………………………………………. 21
Введение
Среди практически важных задач отыскания условного экстремума линейной функции важное место занимают задачи с требованием целочис-ленности всех переменных. Они получили название задач целочисленного программирования.
Казалось бы, естественный путь решения целочисленной задачи со-стоит в решении соответствующей линейной задачи с последующим округ-лением компонент ее оптимального плана до ближайших целых чисел. На самом деле такой путь в большинстве случаев не только уводит, от оптиму-ма, но даже приводит иногда к недопустимому решению задачи.
Наиболее распространенными методами решения задач целочислен-ного программирования являются методы отсечения, а в частности метод Гомори. В связи с этим, в курсовой работе рассмотрен алгоритм данного метода и приведена его практическая реализация. Кроме того, для задач целочисленного программирования, содержащих две переменных, широко применяют графический способ решения, который также рассмотрен в курсовой работе.
Целью данной курсовой работы является изучение моделей линейно-го целочисленного программирования, в частности различных методов решения задачи целочисленного программирования и реализация двух способов решения задачи целочисленного программирования на конкрет-ном примере.
Исходя из поставленной цели, можно выделить следующие задачи для вы-полнения в данной курсовой работе:
1. Рассмотреть общие подходы к решению задач линейного целочисленно-го программирования.
2. Подобрать практическую задачу по данной теме.
3. Решить задачу двумя методами из рассмотренных в теоретической ча-сти.
4. Сделать вывод о применимости методов целочисленного ЛП на практи-ке.
1. Математическая постановка
задачи целочисленного программирования
При решении целого ряда задач на отыскание экстремума, сводя-щихся к задачам линейного программирования, может сложиться такая ситуация, при которой удовлетворяет только тот оптимальный план, все или некоторые компоненты которого являются целыми числами. Подобно-го рода задачи весьма многогранны. В частности, задачи эффективного использования производственных площадей, распределения рабочей силы по видам технологического оборудования, оптимального использования инвестиций, оптимального раскроя материала, производства неделимой (штучной) продукции, распределения судов по линиям или самолетов по рейсам и др.
Задачи линейного программирования, в которых в качестве допол-нительного условия ставится требование, чтобы все или некоторые пере-менные в оптимальном плане были целыми числами, называются соответ-ственно задачами линейного целочисленного программирования или задачами частично линейного целочисленного программирования. Целью данной работы является изучение задачи линейного целочисленно-го программирования.
…
Для решения задач целочисленного программирования используется ряд методов. Самый простой из них – симплекс-метод. В случае если ком-поненты оптимального плана оказываются нецелочисленными, их округ-ляют до ближайших целых чисел. Однако такое округление может или дать решение, не лучшее среди целочисленных решений, или привести к решению, не удовлетворяющему условию задачи. Поэтому используют специально разработанные методы.
Методы целочисленной оптимизации можно разделить на три ос-новные группы:
1) методы отсечения;
2) комбинаторные методы;
3) приближенные методы.
Остановимся более подробно на некоторых из этих методов.
2. Методы решения задач линейного целочисленного програм-мирования
2.1 Решение задач целочисленного программирования
графическим методом
Для задачи линейного программирования, содержащей две перемен-ные и неравенства в системе ограничений, решение может быть найдено графическим методом. При этом строится область всех допустимых реше-ний. Если эта область пустая, то задача неразрешима.
После построения области допустимых решений строят вектор направления возрастания целевой функции и проводят линии уровня целевой функции, которые смещают параллельно в направлении вектора .
…
2.2 Решение задач линейного целочисленного программирования ме-тодом отсечения
Сущность методов отсечения состоит в том, что сначала задача ре-шается без условий целочисленности. Если полученный план целочислен-ный, задача решена. В противном случае к ограничениям задачи добавля-ется новое ограничение, обладающее следующими свойствами:
…
4. Полученную расширенную задачу решить симплексным методом. Если найденный оптимальный план будет целочисленным, то задача цело-численного программирования (1.1)-(1.4) решена. В противном случае вернуться к п.2 алгоритма.
Если задача разрешима в целых числах, то после конечного числа шагов оптимальный целочисленный план будет найден. Пример реализа-ции метода Гомори приведен в п.5 курсовой работы.
2.3 Решение задачи целочисленного программирования методом вет-вей и границ
Метод ветвей и границ – один из комбинаторных методов. Его суть, заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспектив-ными, и отбрасывании бесперспективных вариантов.
…
Заключение
В курсовой работе рассмотрены математическая постановка задачи линейного целочисленного программирования, приведены примеры цело-численных задач (задача о рюкзаке, задача о назначениях, задача о рас-крое материалов).
Изучены методы решения задач целочисленного программирования: графический способ решения, метод построения правильных отсечений Гомори, комбинаторный метод ветвей и границ.
…
Работу прислала: Марина.
Скачать весь реферат:
|
