Целочисленное программирование

Размещено на http://www.allbest.ru/

Федеральное государственное образовательное бюджетное учреждение высшего образования

Финансовый университет

при Правительстве Российской Федерации

Липецкий филиал

Кафедра "Математика и информатика"

Направление: Государственное и муниципальное управление

Контрольная работа

по дисциплине: "Основы математического моделирования социально-экономических процессов"

тема: "Целочисленное программирование"

Преподаватель: ст. пр. Рязанцева Е.А.

Студент: Кирина Валерия Андреевна

Липецк 2015г.

Введение

При рассмотрении целого ряда задач финансового менеджмента и бизнеса необходимо учитывать требование целочисленности используемых переменных. Такие задачи называются задачами целочисленного программирования.

Под задачей целочисленного программирования (ЦП) понимается задача, в которой все или некоторые переменные должны принимать целые значения. В том случае, когда ограничения и целевая функция задачи представляют собой линейные зависимости, задачу называют целочисленной задачей линейного программирования. В противном случае, когда хотя бы одна зависимость будет нелинейной, это будет целочисленной задачей нелинейного программирования. Особый интерес к задачам ЦП вызван тем, что во многих практических задачах необходимо находить целочисленное решение ввиду дискретности ряда значений искомых переменных.

Целочисленное программирование возникло в 50-60-е годы нашего века из нужд практики - главным образом в работах американских математиков Дж. Данцига и Р. Гомори. Первоначально целочисленное программирование развивалось независимо от геометрии чисел на основе теории и методов математической оптимизации, прежде всего линейного программирования. Однако, в последние время исследования в этом направлении все чаще проводятся средствами математики целых чисел.

Задачи такого типа весьма актуальны, так как к их решению сводится анализ разнообразных ситуаций, возникающих в экономике, технике, военном деле и других областях. С появлением ЭВМ (электронная вычислительная машина), ростом их производительности повысился интерес к задачам такого типа и к математике в целом.

Целочисленное программирование. Основные понятия.

При рассмотрении целого ряда задач финансового менеджмента и бизнеса необходимо учитывать требование целочисленности используемых переменных. Такие задачи называются задачами целочисленного программирования.

Целочисленным (иногда его называют также дискретным) программированием называется раздел математического программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Огромное количество экономических задач носит дискретный, чаще всего целочисленный характер, что связано, как правило, с физической неделимостью многих элементов расчета: например, нельзя построить два с половиной завода, купить полтора автомобиля и т.д. В ряде случаев такие задачи решаются обычными методами, например, симплексным методом, с последующим округлением до целых чисел. Однако такой подход оправдан, когда отдельная единица составляет очень малую часть всего объема (например, товарных запасов); в противном случае он может внести значительные искажения в действительно оптимальное решение. Поэтому разработаны специальные методы решения целочисленных задач.

Рекомендации по формулировке и решению ЦП:

1. Количество целочисленных переменных уменьшать насколько возможно. Например, целочисленные переменные, значения которых должно быть не менее 20, можно рассматривать как непрерывные;

2. В отличие от общих задач ЛП, добавление новых ограничений особенно включающих целочисленные переменные, обычно уменьшают время решения задач ЦП;

3. Если нет острой необходимости в нахождении точного оптимального целочисленного решения, отличающегося от непрерывного решения, например, 3%. Тогда реализацию метода ветвей и границ для задачи максимизации можно заканчивать, если отношение разницы между верхней и нижней границ к верхней границы меньше 0,03.

Метод ветвей и границ можно применять для решения задач нелинейного программирования.

Метод Гомори

Одним из методов решения задач линейного целочисленного программирования является метод Гомори. Сущность метода заключается в построении ограничений, отсекающих нецелочисленные решения задачи линейного программирования, но не отсекающих ни одного целочисленного плана.

Рассмотрим алгоритм решения задачи линейного целочисленного программирования этим методом.

1. Решаем задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования.

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

- оно должно быть линейным;

- должно отсекать найденный оптимальный нецелочисленный план;

- не должно отсекать ни одного целочисленного плана.

Для построения ограничения выбираем компоненту оптимального плана с наибольшей дробной частью и по соответствующей этой компонентной строке симплексной таблицы записываем ограничение Гомори.

, (1)

где ;

;

новая переменная;

ближайшее целое не превосходящее xj и zj соответственно.

3. Составленное ограничение добавляем к имеющимся в симплексной таблице, тем самым получаем расширенную задачу. Чтобы получить опорный план этой задачи, необходимо ввести в базис тот вектор, для которого величина минимальна. И если для этого вектора величина и = min, то получается по дополнительной строке, если zkj 0, то в следующей симплексной таблице будет получен опорный план. Если же величина и не соответствует дополнительной строке, то необходимо переходить к М-задаче (вводить искусственную переменную в ограничение Гомори).

4. Решаем при помощи обычных симплексных преобразований полученную задачу. Если решение этой задачи приводит к целочисленному оптимальному плану, то искомая задача решена. Если мы получили нецелочисленное решение, то снова добавляем одно дополнительное ограничение, и процесс вычислений повторяется. Проделав конечное число итераций, либо получаем оптимальный план задачи целочисленного программирования, либо устанавливаем ее неразрешимость.

Метод ветвей и границ

Впервые метод ветвей и границ был предложен Ландом и Дойгом в 1960 году для решения общей задачи целочисленного линейного программирования (Land A.H., Doig A.G. An automatic method of solving discrete programming problems // Econometrica. V28, 1960).

Алгоритм метода ветвей и границ представляет собой эффективную процедуру перебора всех целочисленных допустимых решений.

Решается исходная задача ЛП при условии непрерывности переменных.

Если все корни решения нецелочисленны (в обратном случае - оптимальное целочисленное решение найдено), производим ветвление задачи на две, для каждой из задач вводим дополнительные ограничения по одной из переменных xiai, xibi, где ai - наибольшее целое, не превосходящее xi, а bi - наименьшее целое, большее xi, например, при корне исходной задачи x2=2.3 доп. ограничение в одной ветви будет x22, а по другой - x23.

Снова решаются задачи в обеих ветвях с накладыванием последующих ограничений по другим переменным. На каждом шаге проверяется целочисленность корней.

Ветку считают тупиковой, если:

а) допустимое решение очередной задачи ЛП отсутствует;

б) текущее решение (значение целевой функции) хуже уже найденного целочисленного решения; математический программирование алгоритм

в) текущая задача ЛП является подзадачей ранее рассчитанной задачи.

Циклический алгоритм целочисленного программирования

Рассмотрим следующую задачу линейного программирования:

Максимизировать

X0=a00-a01x1-a02x2-……..-a0nxn, (2)

при условии:

xn+1=an+1,0-an+1,1x1-an+1,2x2-…….-an+1,nxn,

xn+m=an+m,0 - an+m,1x1-an+m,2x2-…….-an+m,nxn,

xj?0 (j=1,……., n+1,……., n+m).

Заметим, что xn+1., хn+m - слабые переменные, a x1…., хn - исходные переменные задачи (2). Если наряду с ограничениями (2) потребовать, чтобы все хj, (j'=1,…, т) были целыми, то задача будет называться задачей целочисленного программирования. Существует большое количество задач, особенно комбинаторных, которые можно сформулировать как задачи целочисленного программирования.

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

Как только это будет сделано, можно решать модифицированную задачу линейного программирования любым обычным методом, и полученное базисное оптимальное решение автоматически будет целочисленным.

Представленный ниже целочисленный алгоритм обладает следующими свойствами:

1) все дополнительные ограничения сохраняют допустимые точки исходной целочисленной задачи;

2) за конечное число шагов создается достаточное количество дополнительных ограничений для того, чтобы оптимальное решение модифицированной задачи было целочисленным;

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

4) каждое новое ограничение сокращает область допустимых решений исходной задачи целочисленного программирования.

Следует подчеркнуть, что оптимальное решение исходной задачи может быть получено прежде, чем допустимая область сократится до размеров выпуклой оболочки. К тому же, поскольку оптимальное целочисленное решение определяется пересечением п гиперплоскостей, таких гиперплоскостей существует не более, чем это необходимо; некоторые из них могут быть ограничениями исходной задачи.

Обычно в ограничения задачи (2) включаются в тривиальные соотношения xj= - (-Xj) (j'=1,…, n), а задача в матричной форме принимает вид:х = А (-хn), (3)

где х - вектор-столбец с компонентами Х 0, x1,…, xn, xn+1,…, xn+m А - соответствующая матрица размера (п + т + 1) * (n + 1) и (-хn) - вектор с компонентами (1, - x1, - x2,…, - xn), представляющими собой небазисные переменные исходной таблицы. Задачу целочисленного программирования также можно записать в виде таблицы.

Причины представления переменных в виде (-x1), (-x2,……, (-xn)) - чисто исторические, но это стало обычной практикой в целочисленном программировании. Будем использовать бj(j = 0, 1,…, п) для обозначения j-го столбца текущей таблицы и aij (i = 0, 1,…, п + т; j = 0, 1,…, n) для обозначения элемента 1-й строки и 7-го столбца таблицы. Предполагается, что все a, ij в исходной таблице целые. Следовательно, все слабые переменные xn+1,…, Хn+m должны быть также неотрицательными целыми числами.

При изложении алгоритма для решения целочисленных задач будем следовать работе Гомори. Вначале задача целочисленного программирования рассматривается как линейная программа и алгоритм решает ее с помощью прямого или двойственного симплекс-метода. В конце работы алгоритма аij?0 (i = 1,……, п + т) и a0j? 0 (j' = 1,…, n). (Для получения исходного двойственного допустимого решения введем дополнительное ограничение xn+m+1 == М - X1 - x2 - … - xn? 0, где M - достаточно большая константа, и проделаем одну итерацию с этой строкой и лексикографически минимальным столбцом в качестве ведущего.) Если аi0? 0 и целые для всех i, то получено оптимальное решение целочисленной задачи. В этом случае решение получается сразу, без использования ограничений целочисленности. Если аi0? 0, но не все целые, добавим к ограничениям (1) еще одно. Новое ограничение записывается внизу таблицы так, чтобы она перестала быть прямо допустимой, т.е. аi0<О для i == п + т + 1. Затем используется двойственный симплекс-метод с целью сделать все аi0? 0. Если аi0 получаются нецелыми, в таблицу добавляются новые ограничения до тех пор, пока аi0 (i = 1,…, n,…, n + m) не станут все целыми и неотрицательными.

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

Каждый раз после проведения итерации симплекс-метода происходит изменение множества небазисных переменных. Таблица также меняется. Будем использовать t для обозначения t-й. таблицы. Матричное уравнение (3) запишется как

Хt = Аt (-хtn), (4)

где х° - вектор-столбец с n + т + 1 компонентами, А° - матрица размера (п + т + 1)*(n + 1) и (-х 0n) - вектор с компонентами (1, - x1,…, - xn), представляющими собой текущие небазисные переменные, взятые со знаком минус. Если в матрице А а 0i?0 (j = 1,…, n), а 00 ? 0 (mod 1) 1} и аi0 ? 0 (i=1,…, п+т) - целые неотрицательные числа, то получено оптимальное решение целочисленной задачи. Если аi0 не все целые, введем дополнительное ограничение. Рассмотрим такое уравнение из (4), в котором аi0m нецелое. Опуская индексы строки, имеем

x=a0+?aj(-xj) (5)

где xj в правой части - текущие небазисные переменные и a0 - нецелое. Поскольку требуется, чтобы х было целым, или х ?0 (mod1), правая часть уравнения (5) также должна удовлетворять условию

0?a0+?aj(-xj) (mod1). (6)

Это условие должно выполняться при допустимом целочисленном решении. Поскольку требуется, чтобы xj, были целыми, можно алгебраически складывать с отношения 0?f0+?jfi(-xi) (mod1) (0<f0<1, 0?fj<1).

Задача о рюкзаке

Контейнер оборудован m отсеками вместимостью для перевозки n видов продукции . Виды продукции характеризуются свойством неделимости, т.е. их можно брать в количестве 0, 1, 2, ... единиц. Пусть - расход i-го отсека для перевозки единицы j-ой продукции. Обозначим через полезность единицы j-ой продукции. Требуется найти план перевозки, при котором максимизируется общая полезность рейса.

Модель задачи примет вид:

при ограничениях на вместимости отсеков

 условии неотрицательности

условии целочисленности

- целые .

Когда для перевозки имеется один отсек и каждый вид продукции может быть взят или нет, то модель задачи принимает вид:

.

Задача о назначении

Имеет n исполнителей, которые могут выполнять n различных работ. Известна полезность , связанная с выполнением i-м исполнителем j-й работы . Необходимо назначить исполнителей на работы так, чтобы добиться максимальной полезности, при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должне быть закреплен только один исполнитель.

Математическая модель задачи примет вид:

Каждый исполнитель назначается только на одну работу:

На каждую работу назначается только один исполнитель:

Условия неотрицательности и целочисленности:

,.

Задача коммивояжера

В данной работе была рассмотрена сущность целочисленного программирования. Затронуты специальные методы решения целочисленных задач. Такие задачи возникают при моделировании разнообразных производственно-экономических, технических, военных и других ситуаций. В то же время ряд проблем самой математики может быть сформулирован как целочисленные экстремальные задачи.

Задачи такого типа весьма актуальны, так как к их решению сводится анализ разнообразных ситуаций, возникающих в экономике, технике, военном деле и других областях. Эти задачи интересны и с математической точки зрения. С появлением ЭВМ, ростом их производительности повысился интерес к задачам такого типа и к математике в целом.

Список использованной литературы

1. А. Схрейвер. Теория линейного и целочисленного программирования: в 2-х томах.; перевод с английского. 1991г. 360с.

2. Т. Ху. Целочисленное программирование и потоки в сетях.; перевод с английского. 1974г.

3. А.В. Кузнецов, В.А. Сакович, Н.И. Холод. Высшая математика: Математическое программирование. Ученик - 2-е издание. 2001г. 351с.

4. В.Г. Карманов. Математическое программирование: Учебное пособие - 5-е издание, стереотип-М:ФИЗМАТ, 2001г.-264с.

5. Е.Г. Белоусов. Введение в выпуклый анализ и целочисленное программирование. М.: Издательство МГУ, 1977г.

6. В.В. Федосеев, А.Н. Гармаш, Д.М. Дайитбегов.: Экономико-математические методы и прикладные модели: Учеб.пособие для вузов/ЮНИТИ, 1999г.-391с.

7. Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; под ред. Проф. Н.Ш. Кремера. : Исследование операций в экономике; учеб. Пособие для вузов.

Размещено на Allbest.ru