Курсовая на тему: Постановка и методы решения задач целочисленного линейного программирования.

Фрагменты работы:

Клиентские онлайн игры стрелялки - для тех кто любит поиграть.

Содержание

Введение………………………………………………………………….. 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 Решение задачи целочисленного программирования методом вет-вей и границ

Метод ветвей и границ – один из комбинаторных методов. Его суть, заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспектив-ными, и отбрасывании бесперспективных вариантов.

...

Заключение

В курсовой работе рассмотрены математическая постановка задачи линейного целочисленного программирования, приведены примеры цело-численных задач (задача о рюкзаке, задача о назначениях, задача о рас-крое материалов).

Изучены методы решения задач целочисленного программирования: графический способ решения, метод построения правильных отсечений Гомори, комбинаторный метод ветвей и границ.

...

Работу прислала: Марина. 
.

Скачать весь реферат:

СКАЧАТЬ ТУТ