Постановка линейной целочисленной задачи. Метод отсекающих плоскостей. Дробный алгоритм решения полностью целочисленных задач. Эффективность отсечения Гомори. Сравнение вычислительных возможностей метода отсекающих плоскостей и метода ветвей и границ.
Среди практически важных задач отыскания условного экстремума линейной функции важное место занимают задачи с требованием целочисленности всех переменных. Существуют различные методы решения таких задач, и заметное место среди них занимают методы отсечения., п) из которых обладает по j-ой характеристике показателем и полезностью , найти такой набор, который позволяет максимизировать эффективность использования ресурсов величины . Математическая модель этой задачи может быть представлена следующим образом: в области, определенной условиями (3) найти решение , при котором максимизируется (минимизируется) значение целевой функции Допустимое решение, при котором функция (4) достигает наибольшего (наименьшего) значения, называется оптимальным решением. Казалось бы, что естественный путь решения целочисленной задачи состоит в решении соответствующей линейной задачи с последующим округлением компонент ее оптимального плана до ближайших целых чисел.Представленный ниже пример раскрывает смысл понятия “отсекающая плоскость”. Рассмотрим следующую линейную задачу целочисленного программирования: В области, определенной условиями Область допустимых решений задачи с ослабленными ограничениями, получаемой путем отбрасывания требования целочисленности переменных, изображена на рис. В основе метода отсекающих плоскостей лежит преобразование области допустимых решений задачи с ослабленными ограничениями в выпуклый многогранник, экстремальная точка которого является оптимальным решением исходной целочисленной задачи.Например, ограничение можно записать в виде неравенства в котором дроби отсутствуют. В этом случае дробный алгоритм позволяет обнаружить отсутствие допустимого решения даже тогда, когда задача, записанная в исходных переменных, имеет допустимое целочисленное решение. На первом шаге решается задача с ослабленными ограничениями, не содержащими условия целочисленности переменных. В противном случае следует ввести дополнительные ограничения, порождающие (вместе с исходными ограничениями) новую задачу линейного программирования, решение которой оказывается целочисленным и совпадает с оптимальным решением исходной целочисленной задачи. Пусть последняя симплексная таблица задачи с ослабленными ограничениями имеет следующий вид: Базисные переменные Решение (свободные члены) Свободные переменныеИз изложенного выше следует, что вид неравенства, определяющего некоторое отсечение, зависит от выбора производящей строки. Эффективность отсечения характеризуется размерами области, отсекаемой от многогранника допустимых решений, что математически можно выразить следующим образом. Будем говорить, что отсечение (1) более эффективно, чем отсечение (2), если и для всех j, причем по крайней мере в одном случае выполняется строгое неравенство.После применения симплекс-метода для этой же задачи, но с ослабленными ограничениями, получаемой путем отбрасывания требования целочисленности переменных, имеем из исходной симплекс-таблицы следующую: Базисные переменные Решение (свободные члены) Свободные переменные То есть отсечение будем строить на основе производящей i-ой строки, которой соответствует Введем отсечения, соответствующие производящим строкам с базисными переменными и целевой функции L: (L-строка) Получаем новую таблицу: Базисные переменные Решение (свободные члены) Свободные переменные Вычисляются отношения коэффициентов L-строки к соответствующим коэффициентам-строки(столбец свободных членов не рассматривается).Попробуем охарактеризовать поведение алгоритмов метода отсекающих плоскостей и метода ветвей и границ при решении задач целочисленного линейного программирования. В качестве меры продолжительности вычислений рассмотрим количество симплексных итераций I и количество дополнительных линейных ограничений D. Сравним выше указанные методы при решении следующей целочисленной задачи: В области, определенной условиями При использовании метода отсекающих плоскостей (см. приложение 2): x[1]=1 (погрешность 1.788139e-07) x[2]=1 (погрешность 5.960464e-07) x[3]=8 (погрешность 1.000000e-16) x[4]=0 (погрешность 1.000000e-16) При использовании метода ветвей и границ: x[1]=1 (погрешность 5.960464e-08) x[2]=1 (погрешность 5.960464e-08) x[3]=8 (погрешность 1.000000e-16) x[4]=0 (погрешность 1.000000e-16)В данной работе был рассмотрен метод отсекающих плоскостей и представлена программа на языке программирования С , реализующая данный метод. Также приведен конкретный пример решения полностью целочисленной задачи выше указанным методом. Сравнительный анализ вычислительных возможностей метода отсекающих плоскостей и метода ветвей и границ показал, что использование второго из них становится гораздо более эффективным с увеличением количества переменных и количества неравенств задачи, при небольшой же размерности задачи предпочтительней первый метод.
План
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1. Постановка линейной целочисленной задачи
2. Описания метода отсекающих плоскостей
2.1 Идея метода
2.2 Дробный алгоритм решения полностью целочисленных задач
2.3 Эффективность отсечения Гомори
3. Использование метода отсекающих плоскостей для решения одной задачи линейного целочисленного программирования
4. Сравнение вычислительных возможностей метода отсекающих плоскостей и метода ветвей и границ
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
Приложение 1. Листинг программы
Приложение 2. Результат работы программы
Вывод
В данной работе был рассмотрен метод отсекающих плоскостей и представлена программа на языке программирования С , реализующая данный метод.
Также приведен конкретный пример решения полностью целочисленной задачи выше указанным методом. При этом использовались условия наиболее эффективного отсечения. В результате было введено два дополнительных ограничения и после чего получен целочисленный ответ.
Сравнительный анализ вычислительных возможностей метода отсекающих плоскостей и метода ветвей и границ показал, что использование второго из них становится гораздо более эффективным с увеличением количества переменных и количества неравенств задачи, при небольшой же размерности задачи предпочтительней первый метод.
При реализации метода отсекающих плоскостей возникают трудности, носящие технический характер. В настоящий момент можно говорить о решении с помощью этого метода задач не более чем среднего размера (сотни переменных и десятки ограничений).
Более того, опыт показывает, что даже некоторые задачи сравнительно небольшой размерности не могут быть решены с помощью метода отсекающих плоскостей. Известны случаи, когда непреднамеренное изменение порядка следования ограничений делало несложную исходную задачу поистине гигантской по объему вычислений.
Наиболее общий вывод о возможностях использования метода отсечений заключается в признании того факта, что указанный метод не обеспечивают эффективного решения общей задачи целочисленного программирования. Однако некоторые идеи метода отсечений оказываются полезными для совершенствования других алгоритмов решения целочисленных задач.
Список литературы
1. Таха Х., Введение в исследование операций: В 2-х книгах. Кн. 1. М.: Мир, 1985. 479с.
2. Подбельский В. В. и Фомин С. С. Программирование на языке Си. М.: “Финансы и статистика”, 2000. 599с.
3. Лященко И.Н. Линейное и нелинейное программирование, М.: Наука, - 1985.
4. Санович К.М. Исследование операций, М.: Наука, - 1989.
Листинг программы
#include
#include
#include
#include void main()
{ float dr(float);
float zz,*x,**a,alk,*ai,*aj,**f;
int simpiter=0,p,n=4,m=4,i=0,j=0,k=0,l=0,q=0,xx;
clrscr();
x=new float[m 1];//m - k-vo peremennyh ai=new float[n m 100];
Результат работы программы x[1]=1 (погрешность 1.788139e-07) x[2]=1 (погрешность 5.960464e-07) x[3]=8 (погрешность 1.000000e-16) x[4]=0 (погрешность 0.000000e-16)
Максимум функции z=101.
Количество симплексных итераций: I=5
Количество дополнительных ограничений: D=1
Размещено на .ru
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
