close

Вход

Забыли?

вход по аккаунту

?

Курсовая Метод отсекающих плоскостей

код для вставкиСкачать
Приднестровский государственный университет им.Т.Т.Шевченко Рыбницкий филиал
Кафедра физики, математики и информатики
КУРСОВАЯ РАБОТА
по дисциплине "Исследование операций"
Тема: "Целочисленные методы линейного программирования. Метод отсекающих плоскостей"
Выполнил: студент IV курса 420 гр, специальности "ПОВТиАС"
Тыршу Михаил Иванович
Проверил:
-
Тягульская Л.А.
г.Рыбница 2013г.
Оглавление
ВВЕДЕНИЕ3
ГЛАВА I. Метод ветвей и границ.4
1.1.Пример задачи целочисленного программирования4
1.2.Общий алгоритм методов решения задач целочисленного программирования6
1.3.Метод ветвей и границ7
1.4.Алгоритм метода ветвей и границ12
ГЛАВА II. ОПИСАНИЕ ПРОГРАММНОГО ПРОДУКТА13
ЗАКЛЮЧЕНИЕ18
Список литературы19
ВВЕДЕНИЕ
Целочисленное линейное программирование ориентировано на решение задач линейного программирования, в которых все или некоторые переменные должны принимать целочисленные (или дискретные) значения. Несмотря на интенсивные исследования, проводимые на протяжении последних десятилетий, известные вычислительные методы Решения задач Целочисленного Линейного программирования далеки от совершенства. На сегодня не существует надежных вычислительных алгоритмов решения таких задач.
Примером таких задач могут быть задания расчета количества работающих людей или машин на предприятии, расчет необходимых цельных деталей и т.д.
В данной курсовой работе будет рассмотрен один из целочисленных методов - метод отсекающих плоскостей.
ГЛАВА I. Метод отсекающих плоскостей.
Пример задачи целочисленного программирования
Рассмотрим сначала простую практическую задачу, которая сводится к ЦЛП. Для удобства задачи, в которых все переменные должны быть целочисленными, называются полностью целочисленными, а задачи, в которых лишь некоторые переменные должны принимать целочисленные значения - частично целочисленными.
Пример: Оценивается пять проектов с точки зрения их возможного финансирования на предстоящий трехлетний период. Следующая таблица содержит ожидаемую прибыль от реализации каждого проекта и распределение необходимых капиталовложений по годам.
Предполагая, что каждый утвержденный проект будет реализован на трехлетний период. Необходимо определить совокупность проектов, которой соответствует минимум суммарной прибыли.
Задача сводится к решению типа "Да - Нет" относительно каждого проекта. Определим двоичные переменные X_j:
Задача ЦЛП будет записана следующим образом:
Максимизировать z = 20x_1+40x_2+20x_3+15x_4+30x_5
〖5x〗_1+4x_2+3x_3+7x_4+8x_5≤25,
x_1+7x_2+9x_3+4x_4+6x_5≤25,
〖8x〗_1+10x_2+2x_3+x_4+10x_5≤25,
x_1,x_2,x_3,x_4,x_5=0 или 1
Оптимальным целочисленным планом (полученным с помощью программы Tora) является х1=х2=х3=х4=1, х5=0 с Z=95 (млн. долл.). Это решение означает, что необходимо выбрать для финансирования все проекты, кроме пятого.
Интересно сравнивать решение данной задачи ЦЛП с решением "обычной" задачи ЛП с теми же ограничениями, но без условия целочисленности переменных. Задача линейного программирования получается в результате замены условия X_j=0 или 1 на ограничение 0≤X_j≤1 для всех j. Эта задача имеет решение при х1=0.5789, х2=х3=х4=1, х5=0.7368 и z=108.68 (млн. долл.). Такое решение с точки зрения целочисленной задачи лишено смысла, так как две переменные принимают дробное значение. Можно было бы попытаться округлить полученный результат, что привело бы к х1=х5=1. Полученное при этом решение является не допустимым, так как нарушаются ограничения задачи . Более существенным в этой ситуации является то, что округление применять нельзя, т.к. X_j представляет решение "типа да - нет", для которого дробные значения лишены смысла. Общий алгоритм методов решения задач целочисленного программирования Методы решения задач целочисленного линейного программирования основаны на использовании вычислительных возможностей методов линейного программирования. Обычно алгоритм целочисленного программирования включает три шага.
Шаг 1. "Ослабление" пространства допустимых решений задачи целочисленного линейного программирования путем замены любой двоичной переменной с непрерывным ограничением 0≤y≤1 и отбрасывания требования целочисленности для всех остальных переменных. В результате получается обычная задача линейного программирования. Шаг 2. Решение задачи линейного программирования и определение ее оптимального решения.
Шаг 3. Имея полученное (непрерывное) оптимальное решение, добавляем специальные ограничения, которые итерационным путем изменяют пространство допустимых решений задачи линейного программирования таким образом, чтобы, в конечном счете, получилось оптимальное решение, удовлетворяющее требованиям целочисленности.
Разработаны два общих метода генерирования специальных ограничений, о которых идет речь при реализации шага 3.
Метод ветвей и границ.
Метод отсекающих плоскостей.
Хотя ни один из перечисленных методов не дает надежных результатов при решении задачи целочисленного линейного программирования, опыт вычислений свидетельствует, что метод ветвей и границ более успешно решает задачу, чем метод отсекающих плоскостей. Метод отсекающих плоскостей
Рассмотрим следующую задачу целочисленного линейного программирования. Максимизировать z=7x_1+10x_2 при ограничениях
〖-x〗_1+〖3x〗_(2 )≤6
〖7x〗_1+1≤35
x_1,x_2≥0 и целые
Данный метод путём добавления отсечений (отсекающих плоскостей) преобразует пространство допустимых решений соответствующей задачи линейного программирования в выпуклый многогранник, вершина которого, соответствующая оптимуму, является целочисленной и представляет решение исходной задачи. На рис. 1 показан пример двух таких отсечений. Мы начинаем с оптимального решения непрерывной задачи линейного программирования 〖(x〗_1,x_2)=(4 1/2,3 1/2) и z=66 1/2. Затем прибавляем отсечение I, которое вместе с ограничениями исходной задачи линейного программирования приводит к оптимальному решению 〖(x〗_1,x_2)=(4 4/7,3) с z = 62. После этого прибавляется отсечение II, которое вместе с отсечением I и исходными ограничениями приводят к оптимальному решению 〖(x〗_1,x_2)=(4,3) с z = 58. Последнее решение является полностью целочисленным, как и требуется.
Прибавленные отсечения не отбрасывают ни одной исходной допустимой целочисленной точки, но должны проходить по меньшей мере через одну целочисленную точку (допустимую или недопустимую). Этим основным требованиям должно удовлетворять любое отсечение.
В общем случае может потребоваться любое (конечное) число отсечений для достижения полностью целочисленной экстремальной точки. В действительности количество необходимых для этого отсечений не зависит от размерности задачи в том смысле, что для решения задачи с небольшим количеством переменных и ограничений может потребоваться больше отсечений, чем для задачи большей размерности.
Рисунок 1.
Алгебраический способ определения отсечений. Метод отсекающих плоскостей начинает работу с решения непрерывной задачи линейного программирования. В симплекс-таблице, соответствующей оптимальному решению задачи линейного программирования, следует выбрать одну из строк (называемую производящей), для которой базисная переменная нецелочисленная. Искомое отсечение строится на основании дробных составляющих коэффициентов производящей строки. По этой причине его называют дробным отсечением.
Сейчас мы введём уравнение дробного отсечения. Построение отсечения объясняется на численном примере, а не на сложных математических конструкциях.
При дополнительных переменных x_3 и x_4 для ограничений I и II оптимальная симплекс-таблица соответствующей задачи линейного программирования имеет следующий вид:
Оптимальным непрерывным решением является x_1=4 1/2, x_2=3 1/2, x_3=0, x_4=0 и z=66 1/2. Целочисленное отсечение получается в предположении, что все переменные задачи являются целочисленными. Заметим также, как коэффициенты исходной целевой функции являются целочисленными, то и значение z, соответствующее целочисленному решению, должно быть целочисленным.
Информация, содержащаяся в симплекс-таблице, соответствующей оптимальному решению, может быть записана в виде следующих уравнений:
z-уравнение: z+ 63/22 x_3+31/22 x_4=66 1/2
x_2-уравнение: x_2+ 7/22 x_3+1/22 x_4=3 1/2
x_1-уравнение: x_1- 1/22 x_3+3/22 x_4=4 1/2
Так как в этом примере z, x_1 и x_2 должны быть целочисленными и все они на данный момент имеют дробные значения в оптимальной симплекс таблице, любое из трёх уравнений можно использовать в качестве производящей строки для построения отсечения. Выберем (произвольно) для этой цели z-уравнение:
z+ 63/22 x_3+31/22 x_4=66 1/2 (производящая z-строка)
Для построения дробного отсечения каждый из нецелочисленных коэффициентов раскладывается на целую и дробную части при условии, что дробная часть является строго положительной. Например:
5/2=(2+1/2).
-7/3=(-3+2/3).
Разложение коэффициентов производящей z-строки приводит к следующему уравнению:
z+(2+19/22) x_3+(1+9/22) x_4=(66+1/2).
При переносе всех целочисленных слагаемых в левую часть уравнения, а всех дробных слагаемых в правую часть получаем следующее:
z+2x_3+x_4-66=1/2-19/22 x_3-9/22 x_4.
Поскольку все переменные в рассматриваемой задаче принимают целочисленные значения, левая часть последнего уравнения должна быть целочисленной, откуда следует, что и правая часть также должна принимать целые значения. Перепишем её следующим образом:
1/2-19/22 x_3-9/22 x_4=1/2-(19/22 x_3+9/22 x_4).
Поскольку x_3, x_(4 )≥0, выражение в скобках является неотрицательным. Поэтому величина 1/2-19/22 x_3-9/22 x_4, будучи целочисленной, не может превышать 1. Следовательно, необходимое условие целочисленности можно записать следующим образом:
1/2-19/22 x_3-9/22 x_4≤0.
Это и есть отсечение, порождённое z-строкой. Нетрудно убедиться, что ранее найденное оптимальное непрерывное решение x_1=4 1/2, x_2=3 1/2, x_3=0, x_4=0 не удовлетворяет отсечению. Действительно, так как x_3=x_4=0, отсечение не удовлетворяется (оно приводит к неравенству 1≤0). Следовательно, если мы присоединим отсечение к конечной симплекс-таблице, то оптимальное решение новой симплекс-таблицы будет "двигаться" в направлении выполнения ограничения челоцисленности.
Можно таким же образом построить отсечение, исходя из производящей x_1-строки или x_2-строки. Рассмотрим сначала x_1-строку. Имеем:
x_1- 1/22 x_3+3/22 x_4=4 1/2 (производящая x_1-строка)
Операция разложения приводит к уравнению:
x_1+(-1+21/22) x_3+(0+3/22) x_4=(4+1/2).
Соответствующим отсечением является:
-21/22 x_3-3/22 x_4+1/2≤0.
Аналогично:
x_2+ 7/22 x_3+1/22 x_4=3 1/2(производящая x_2-строка)
записывается в виде:
x_2+(0+7/22) x_3+(0+1/22) x_4=(3+1/2).
Следовательно, в данном случае отсечение имеет вид:
-7/22 x_3-1/22 x_4+1/2≤0.
Любое из трёх отсечений может быть использовано на первой итерации метода отсекающих плоскостей. Поэтому нет необходимости строить все три отсечения перед выбором одного из них.
Выбирая (произвольно) отсечение, порождённое x_2-строкой, записываем его следующим образом:
-7/22 x_3-1/22 x_4+s_1=-1/2,s_(1 )≥0 (отсечение 1)
Это ограничение добавляется в качестве дополнительного в оптимальную симплекс-таблицу задачи линейного программирования:
Таблица представляет оптимальное, но недопустимое решение. Для восстановления допустимости решения применим двойственный симплекс-метод, что приведёт к следующей симплекс-таблице:
Из-за дробных значений переменных x_1 и x_3 последнее решение всё ещё нецелочисленное. Выберем x_1-строку в качестве производящей, т.е.:
x_1+(0+1/7) x_4+(-1+6/7) s_1=(4+4/7).
Соответствующее отсечение имеет вид:
-1/7 x_4-6/7 s_1+s_2=-4/7,s_(2 )≥0 (отсечение 2)
Присоединяя отсечение 2 к последней симплекс-таблице, получаем следующее:
Применение двойственного симплекс-метода приводит к следующей таблице:
Оптимальное решение (x_1=4, x_2=3, z=58), определяемое последней симплекс-таблицей, является целочисленным. То, что все элементы данной симплекс-таблицы являются целочисленными, не случайность. Это типичное явление при использовании дробных отсечений.
Важно подчеркнуть, что применение дробного отсечения предполагает целочисленность всех переменных, включая дополнительные. Это значит, что данный метод применим только к решению полностью целочисленных задач.
Важность этого продемонстрируем на следующем примере. Рассмотрим ограничение:
x_1+1/3 x_2≤13/2,
〖 x〗_1,x_2≥0 и целые
С точки зрения решения соответствующей задачи ЦЛП это ограничение преобразуется путём введения неотрицательной дополнительной переменной s_1, т.е.:
x_1+1/3 x_2+s_1=13/2.
Применение дробного отсечения предполагает, что ограничение имеет допустимое целочисленное решение по всем переменным, т.е. x_1, x_2 и s_1. Рассмотрев это уравнение, можем сказать, что оно может иметь допустимое целочисленное решение переменных x_1 и x_2 лишь в том случае, если переменная s_1 принимает нецелочисленные значения. Следовательно, применение дробного отсечения приведёт к недопустимому целочисленному решению, так как все переменные x_1, x_2 и s_1 не могут одновременно быть целочисленными. Тем не менее ограничение имеет допустимые целочисленные решения для рассматриваемых переменных x_1 и x_2.
Есть две возможности исправить эту ситуацию:
Можно умножить все ограничения на соответствующую константу для устранения дробей. Например, приведённое выше ограничение умножается на 6, что приводит к неравенству 6x_1+2x_2≤39. Любое целочисленное решение переменных x_1 и x_2 автоматически даёт целочисленное значение дополнительной переменной. Однако, этот тип преобразования применим лишь для простых ограничений, так как значения необходимых целочисленных коэффициентов в некоторых случаях могут быть чрезвычайно большими.
Можно использовать специальные отсечения, именуемые частично-целочисленные. Они ориентированы на решение задач, в которых лишь часть переменных должна принимать целочисленные значения, а остальные (включая дополнительные) остаются непрерывными. Детальное изложение таких отсечений в данной курсовой работе не рассматривается.
ГЛАВА II. ОПИСАНИЕ ПРОГРАММНОГО ПРОДУКТА
Для разработки программного продукта, использовался язык программирования C++. Среда разработки - C++ Builder 6.0 . Для запуска программного продукта достаточно запустить Kursovik.exe. Перед пользователем появится окно программы (Рис.5). Рис.5
Далее следует форма с добавленными базисными переменными. Рис.6
Рис.6
Так как в столбцах базисных переменных отсутствуют отрицательные числа, будет произведен расчет симплекс методом, а так же предложены два варианта в виде кнопок для продолжении вычислений Рис.7.
Рис.7
В данной форме происходит разветвление алгоритма и отсекание плоскости возможных решений. На переменную х1 накладываются ограничения. При нажатии на кнопку х1=>3 произойдет вызов формы Рис.8, с измененной симплекс таблицей.
Рис.8
При нажатии на кнопку поиск произойдет расчет таблицы методом искусственного базиса, так как в базисных элементах присутствуют отрицательные числа. Рис.9
Рис.9
Так как в этой задачи нас не устраивают ответы, данная задача считается прозондированной и мы продолжаем цикл, возвращаемся к началу решений Рис.7 и кликаем по кнопке x1<=2. Происходит вызов с измененной симплекс таблицей, в которой на х1 наложены ограничения.Рис.10
Рис.10
Далее при нажатии на кнопку произойдет расчет таблицы симплекс методом, и снова будет предоставлены варианты с наложенными ограничениями на х1,х2. Рис11.
Рис.11
Последнее ветвление будет предоставлено для переменной х3.Рис.12
Рис.12
При проходе методом по обеим ветвям, решения будут найдены.Рис.13
Рис.13
Так как нам необходимо максимизировать функцию мы выбираем наибольшее значение функции Z. Z=32 и ему соответствуют переменные х1=2, х2=2, х3=0.
ЗАКЛЮЧЕНИЕ
В ходе выполнения курсовой работы был изучен один из алгоритмов целочисленного линейного программирования.
Для реализации изученного алгоритмы был выбран язык программирования С++, в среде разработки С++ Builder 6. Приведен пример задачи целочисленного линейного программирования. Описан общий алгоритм методов решения задач целочисленного линейного программирования. Определен метод ветвей и границ, а так же расписан его алгоритм. Для каждого ветвления алгоритма создана специальная форма с измененными параметрами, что позволяет наглядно увидеть проводимые расчеты и улучшить понимание работы метода ветвей и границ. Курсовая работа выполнена, поскольку, реализованы все поставленные цели.
СПИСОК ЛИТЕРАТУРЫ
Абрамов Л.Ф. Капустин В.Ф. Математическое программирование. Л., Издательство Ленинградского университета,1976, 184 с.
Акоф Р., Сасиени М. Основы исследования операций. М.:Мир,1971, 534 с.
Алесинская Т.В. Учебное пособие по решению задач по курсу "Экономико-математические методы и модели". Таганрог: Изд-во ТРТУ, 2002, 153 с.
Аронович А.Б., Афанасьев М.Ю., Суворов Б.П. Сборник задач по исследованию операций. - М.: Изд-во МГУ, 1997, 256 с.
Бережная Е.В., Бережной В.И. Математические методы моделирования
экономических систем: Учебное пособие. - М.: финансы и статистика, 2002, 386 с.:
Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов / Под ред. В.С. Зарубина, А.П. Крищенко. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2000. - 436 с. (Сер. Математика в техническом университете; Вып. ХХ).
Гермейер Ю.Б. Введение в теорию исследования операций.-М.: Наука, 1971.
Давыдов Э.Т. Исследование операций.- М.: Высш.шк., 1990.
Димов Э.М., Калиновский Д.А. Основы исследования операция в экономике: Учебное пособие. - Самара: ПИРС, 1997, 68 с., ил.
Дубров А.М., Лагоша Б.А., Хрусталев Е.Ю. Моделирование рисковых ситуаций в экономике и бизнесе: Учебное пособие / Под ред. Б.А. Лагоши. - М.: Финансы и статистика, 1999. - 16 с.: ил.
2
Документ
Категория
Рефераты
Просмотров
450
Размер файла
386 Кб
Теги
метод, плоскости, отсекающих, курсовая
1/--страниц
Пожаловаться на содержимое документа