Работа По теме: «Целочисленное программирование»

Курсовая работа По теме: «Целочисленное программирование»

Работа По теме: «Целочисленное программирование»

Российский Государственный Торгово-Экономический Университет

Ивановский филиал

Курсовая работа

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

Выполнила: студентка 2 курса УФФ

Проверила:

Иваново 2003г.

План:

Введение.

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

2.Метод Гомори.

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

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

5.Полностью целочисленный алгоритм.

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

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

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

Заключение.

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

Ведение.

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

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

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

Целочисленное программирование возникло в 50-60-е годы нашего века из нужд практики — главным образом в работах американских математиков Дж. Данцига и Р. Гомори.

Первоначально целочисленное программирование развивалось независимо от геометрии чисел на основе теории и методов математической оптимизации, прежде всего линейного программирования.

Однако, в последние время исследования в этом направлении все чаще проводятся средствами математики целых чисел.

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

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

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

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

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

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

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

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

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

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

МетодГомори

Задача целочисленного программирования может быть сформули­рована следующим образом: найти максимум или минимум функции

(7.1)

при условиях

(7.2)

Xj >0, j = 1, 2, …, n, а также при дополнительном условии

хj — целые числа.

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

Для решения задач целочисленного программирования разработа­ны специальные методы. К ним относятся метод отсечений (метод Го­мори) и метод ветвей и границ.

В основе метода Гомори заложена идея, состоящая в том, что сна­чала решается задача линейного программирования (7.1)—(7.3) без уче­та условий целочисленности. Если полученное таким образом реше­ние целочисленное, то оно принимается за оптимальный план задачи (7.I)—(7.4).

Если решение нецелочисленное, то система ограничений дополняется условием, которое отсекает от множества планов задачи нецелочисленный оптимальный план, но при этом сохраняет целочис­ленные вершины множества планов. Затем решается задача линейного программирования с дополнительным условием.

Если полученное та­ким образом решение целочисленное, то оно оптимально и для задачи (7.1)—(7.4). Если же и после этого не для всех переменных выполняется условие целочисленности, то вводится новое условие-отсечение.

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

Рассмотрим указанный алгоритм. Пусть получено решение задачи (7.1)-(7.3) без учета целочисленности и пусть в строке r симплексной таблицы с оптимальным решением содержится нецелочисленная ком­понента опорного плана хr0. В этом случае к условиям (7.1)—(7.3) до­бавляют условие, порожденное строкой г.

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

(7.5)

Далее введем понятие целой и дробной частей чисел аr0 и аrj, для чего запишем эти числа в виде:

Здесь r0] и [arj] — целые части, a qt, qr] — дробные части чисел аrj и arj.

Например, 37/3 =12 +1/3, так как [37/3] = 12, a — s/, = -3 + 1/3„ так как [-8/3] = -3.

Из уравнения (7.5) найдем хr

xr=аr0-

Теперь числа аю и аrj заменим суммами целых и дробных частей:

xr =

Предположим, что все xj — целые числа. Тогда разность

является целым числом.

Чтобы оказалось целым числом и хr, необходима целочисленность разности

Но О

£(/)/) = 42 >£(D12) = 40. Следовательно, план X°1= (3, 1) является решением задачи (7.11)-(7.13),

т. е. надо взять три единицы первого груза и одну единицу второго груза.

Алгоритм метода ветвей и границ

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

ЦИКЛИЧЕСКИЙ АЛГОРИТМ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

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

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

X0=a00-a01x1-a02x2-……..-a0nxn,

при условии

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

.

.

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

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

Заметим, что xn+1, . ., хn+m — слабые переменные, a x1 … ., хn — исходные переменные задачи (1). Если наряду с огра­ничениями (1) потребовать, чтобы все хj, (j'=1, . . .

, т) были целыми, то задача будет называться задачей целочисленного про­граммирования.

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

Ограничения (1) определяют выпуклую область OABCD в n-мер­ном пространстве, как показано на рис. 13.1. Узлы целочисленной решетки на рис. 13.1 изображены точками. Такие точки, рас­положенные внутри области OABCD, являются допустимыми решениями задачи целочисленного программирования.

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

Предположим, что область допу­стимых решений сужена до выпуклой оболочки допустимых целых точек внутри допустимой области. На рис. 13.1 эта выпук­лая оболочка показана затененной областью OEFGH.

Эту зате­ненную область можно рассматривать как область допустимых решений некоторой другой задачи линейного программирования. Действительно, если к задаче линейного программирования, опре­деляющей допустимую область OABCD, добавить ограничение типа RR', как показано на рис. 13.

1, то вновь полученная задача будет иметь OEFGH в качестве области допустимых решений.

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

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

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

Представ­ленный ниже целочисленный алгоритм обладает следующими свойствами: 1) все дополнительные ограничения сохраняют допустимые точки исходной целочисленной задачи; 2) за конеч­ное число шагов создается достаточное количество дополнитель­ных ограничений для того, чтобы оптимальное решение моди­фицированной задачи было целочисленным; 3) дополнительные ограничения (гиперплоскости) проходят по крайней мере через одну целочисленную точку, хотя и не обязательно находящуюся внутри выпуклой оболочки; 4) каждое новое ограничение сокра­щает область допустимых решений исходной задачи целочислен­ного программирования. Следует подчеркнуть, что оптимальное решение исходной задачи может быть получено прежде, чем допустимая область сократится до размеров выпуклой оболочки. К тому же, поскольку оптимальное целочисленное решение определяется пересечением п гиперплоскостей, таких гиперпло­скостей существует не более, чем это необходимо; некоторые из них могут быть ограничениями исходной задачи.

Рис, 13.1.

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

х = А (-хn), (2)

где х — вектор-столбец с компонентами Х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) еще одно. Новое ограничение записывается внизу таблицы так, чтобы она перестала быть прямо допустимой, т. е.

аi01 имеем [1/λ]=0[2] и уравнение (8) приобретает вид

(10)

Уравнение (10) должно выполняться для любого допустимого целочисленного решения задачи (1). Заметим, что если а0 < О,. то [a0/λ] < 0 в уравнении (10). Поэтому уравнение (10) может использоваться в качестве ведущей строки в двойственном сим­плекс-методе. В частности, всегда можно выбрать λ достаточно большим, так чтобы ведущий элемент [aj/λ] в строке (10) стал:

равным —1, что позволит сохранить целочисленность таблицы. Выбор соответствующего λ будет влиять на скорость сходимости алгоритма. Прежде всего опишем сам алгоритм.

В качестве началь­ного необходимо взять двойственно допустимое решение, которое-можно получить добавлением ограничения xn+m+1 = М — x1 — —xn, где М — достаточно большая константа, и про­ведением одной итерации с добавленной строкой и с лексикогра­фически минимальным столбцом, взятыми в качестве ведущих. Алгоритм состоит из следующих шагов.

Ш а г 0. Начать с двойственно допустимой матрицы А° в урав­нении (2), элементы которой — целые числа (как будет видно из дальнейшего, матрица А° может содержать и нецелые элементы).

Шаг 1. Среди строк с аi0 < 0 (i = 1, . . ., n+m) выбрать строку с наименьшим значением i; эта строка станет производя­щей. (Если аi0≥ 0 (i= 1, . . ., n + m), то задача решена.)

Ш а г 2. Выбрать λ > 0 (правило выбора будет описано даль­ше) и написать внизу таблицы дополнительную строку

Эта строка выбирается в качестве ведущей.

Ш а г 3. Провести шаг двойственного симплекс-метода, вычерк­нуть дополнительную строку и вернуться к шагу 1.

Доказательство конечности. Доказательство конечности про­водится в предположении, что существует нижняя граница целевой функции x0. Использование двойственного метода гарантирует выполнение условия

Если a00 уменьшается, то уменьшается на целое число, поскольку все числа остаются целыми, и, следовательно, через конечное число шагов a00 станет меньше x0.

Если алгоритм бесконечен, то a00 должно оставаться Неизменным для всех t > to. Рассмотрим тогда компоненту a10, столбца α0. Если a10 уменьшается, то на целое число.

Когда a10 становится отрицательным, первая строка должна быть выбрана в качестве производящей. Если а1j< О для всех j, то задача неразрешима.

Теперь опишем правило выбора λ в шаге 2 полностью цело­численного алгоритма. Пусть производящая строка имеет вид

и дополнительная строка

Для любого аj 1).

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

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

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

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

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

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

— целые .

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

.

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

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

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

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

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

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

,.

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

Коммивояжер должен посетить один, и только один, раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарную длину пройденного пути.

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

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

,.

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

Заключение.

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

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

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

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

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

3.  , , . Высшая математика: Математическое программирование. Ученик — 2-е издание. 2001г. 351с.

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

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

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

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

[1] Символ (≡) означает «сравнимость».

[2] Если λ > 1, то для получения отсечения (10) из (4) требуется только неотрицательность левой части уравнения (4). Следовательно, любая поло­жительная линейная комбинация строк таблицы может служить произво­дящей строкой.

Источник: https://pandia.ru/text/78/375/1296.php

Работа По теме: «Целочисленное программирование» (стр. 1 из 6)

Работа По теме: «Целочисленное программирование»

Российский Государственный Торгово-Экономический Университет

Ивановский филиал

Курсовая работа

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

Выполнила: студентка 2 курса УФФ

Прозорова В.С.

Проверила: Малеж Л.Н.

Груздева Н.Н.

Иваново 2003г.

План:

Введение.

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

2.Метод Гомори.

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

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

5.Полностью целочисленный алгоритм.

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

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

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

Заключение.

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

Ведение.

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

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

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

Целочисленное программирование возникло в 50-60-е годы нашего века из нужд практики — главным образом в работах американских математиков Дж.Данцига и Р.Гомори.

Первоначально целочисленное программирование развивалось независимо от геометрии чисел на основе теории и методов математической оптимизации ,прежде всего линейного программирования.

Однако, в последние время исследования в этом направлении все чаще проводятся средствами математики целых чисел.

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

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

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

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

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

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

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

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

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

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

МетодГомори

Задача целочисленного программирования может быть сформули­рована следующим образом: найти максимум или минимум функции

(7.1)

при условиях

(7.2)

Xj >0, j = 1, 2, …, n, а также при дополнительном условии

хj— целые числа.

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

Для решения задач целочисленного программирования разработа­ны специальные методы. К ним относятся метод отсечений (метод Го­мори) и метод ветвей и границ.

В основе метода Гомори заложена идея, состоящая в том, что сна­чала решается задача линейного программирования (7.1)—(7.3) без уче­та условий целочисленности. Если полученное таким образом реше­ние целочисленное, то оно принимается за оптимальный план задачи (7.I)—(7.4).

Если решение нецелочисленное, то система ограничений дополняется условием, которое отсекает от множества планов задачи нецелочисленный оптимальный план, но при этом сохраняет целочис­ленные вершины множества планов. Затем решается задача линейного программирования с дополнительным условием.

Если полученное та­ким образом решение целочисленное, то оно оптимально и для задачи (7.1)—(7.4). Если же и после этого не для всех переменных выполняется условие целочисленности, то вводится новое условие-отсечение.

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

Рассмотрим указанный алгоритм. Пусть получено решение задачи (7.1)-(7.3) без учета целочисленности и пусть в строке r симплексной таблицы с оптимальным решением содержится нецелочисленная ком­понента опорного плана хr0. В этом случае к условиям (7.1)—(7.3) до­бавляют условие, порожденное строкой г.

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

(7.5)

Далее введем понятие целой и дробной частей чисел аr0и аrj, для чего запишем эти числа в виде:

Здесь r0] и [arj] — целые части, a qt, qr] — дробные части чисел аrj и arj.

Например, 37/3=12 +1/3, так как [37/3] = 12, a -s/, = -3 + 1/3„ так как [-8/3] = -3.

Из уравнения (7.5) найдем хr

xr=аr0-

Теперь числа аюи аrj заменим суммами целых и дробных частей:

xr =

Предположим, что все xj — целые числа. Тогда разность

является целым числом.

Чтобы оказалось целым числом и хr, необходима целочисленность разности

Но О

Источник: https://mirznanii.com/a/276973/rabota-po-teme-tselochislennoe-programmirovanie

Реферат: Работа По теме: «Целочисленное программирование»

Работа По теме: «Целочисленное программирование»

Российский Государственный Торгово-Экономический Университет

Ивановский филиал

Курсовая работа

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

Выполнила: студентка 2 курса УФФ

Прозорова В.С.

Проверила: Малеж Л.Н.

Груздева Н.Н.

Иваново 2003г.

План:

Введение.

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

2.Метод Гомори.

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

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

5.Полностью целочисленный алгоритм.

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

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

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

Заключение.

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

Ведение.

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

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

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

Целочисленное программирование возникло в 50-60-е годы нашего века из нужд практики — главным образом в работах американских математиков Дж.Данцига и Р.Гомори.

Первоначально целочисленное программирование развивалось независимо от геометрии чисел на основе теории и методов математической оптимизации ,прежде всего линейного программирования.

Однако, в последние время исследования в этом направлении все чаще проводятся средствами математики целых чисел.

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

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

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

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

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

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

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

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

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

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

МетодГомори

Задача целочисленного программирования может быть сформули­рована следующим образом: найти максимум или минимум функции

(7.1)

при условиях

(7.2)

Xj > 0, j = 1, 2, …, n, а также при дополнительном условии

хj — целые числа.

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

Для решения задач целочисленного программирования разработа­ны специальные методы. К ним относятся метод отсечений (метод Го­мори) и метод ветвей и границ.

В основе метода Гомори заложена идея, состоящая в том, что сна­чала решается задача линейного программирования (7.1)—(7.3) без уче­та условий целочисленности. Если полученное таким образом реше­ние целочисленное, то оно принимается за оптимальный план задачи (7.I)—(7.4).

Если решение нецелочисленное, то система ограничений дополняется условием, которое отсекает от множества планов задачи нецелочисленный оптимальный план, но при этом сохраняет целочис­ленные вершины множества планов. Затем решается задача линейного программирования с дополнительным условием.

Если полученное та­ким образом решение целочисленное, то оно оптимально и для задачи (7.1)—(7.4). Если же и после этого не для всех переменных выполняется условие целочисленности, то вводится новое условие-отсечение.

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

Рассмотрим указанный алгоритм. Пусть получено решение задачи (7.1)-(7.3) без учета целочисленности и пусть в строке r симплексной таблицы с оптимальным решением содержится нецелочисленная ком­понента опорного плана хr0. В этом случае к условиям (7.1)—(7.3) до­бавляют условие, порожденное строкой г.

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

(7.5)

Далее введем понятие целой и дробной частей чисел аr0 и аrj , для чего запишем эти числа в виде:

Здесь r0 ] и [arj ] — целые части, a qt , qr ] — дробные части чисел аr j и ar j.

Например, 37 /3 =12 +1/3 , так как [37 /3 ] = 12, a -s /, = -3 + 1/3„ так как [-8/3] = -3.

Из уравнения (7.5) найдем хr

xr =аr0 —

Теперь числа аю и аrj заменим суммами целых и дробных частей:

xr =

Предположим, что все xj — целые числа. Тогда разность

является целым числом.

Чтобы оказалось целым числом и хr , необходима целочисленность разности

Но О

£(/)/) = 42 >£(D1 2 ) = 40. Следовательно, план X°1 = (3, 1) является решением задачи (7.11)-(7.13),

т.е. надо взять три единицы первого груза и одну единицу второго груза.

Алгоритм метода ветвей и границ

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

ЦИКЛИЧЕСКИЙ АЛГОРИТМ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

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

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

X0 =a00 -a01 x1 -a02 x2 -……..-a0n xn ,

при условии

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

.

.

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

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

Заметим, что xn +1 , . ., хn+ m — слабые переменные, a x1 … ., хn — исходные переменные задачи (1). Если наряду с огра­ничениями (1) потребовать, чтобы все хj , (j'=1, . . .

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

Ограничения (1) определяют выпуклую область OABCD в n-мер­ном пространстве, как показано на рис. 13.1. Узлы целочисленной решетки на рис. 13.1 изображены точками. Такие точки, рас­положенные внутри области OABCD, являются допустимыми решениями задачи целочисленного программирования.

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

Предположим, что область допу­стимых решений сужена до выпуклой оболочки допустимых целых точек внутри допустимой области. На рис. 13.1 эта выпук­лая оболочка показана затененной областью OEFGH.

Эту зате­ненную область можно рассматривать как область допустимых решений некоторой другой задачи линейного программирования. Действительно, если к задаче линейного программирования, опре­деляющей допустимую область OABCD, добавить ограничение типа RR', как показано на рис. 13.

1, то вновь полученная задача будет иметь OEFGH в качестве области допустимых решений.

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

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

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

Представ­ленный ниже целочисленный алгоритм обладает следующими свойствами: 1) все дополнительные ограничения сохраняют допустимые точки исходной целочисленной задачи; 2) за конеч­ное число шагов создается достаточное количество дополнитель­ных ограничений для того, чтобы оптимальное решение моди­фицированной задачи было целочисленным; 3) дополнительные ограничения (гиперплоскости) проходят по крайней мере через одну целочисленную точку, хотя и не обязательно находящуюся внутри выпуклой оболочки; 4) каждое новое ограничение сокра­щает область допустимых решений исходной задачи целочислен­ного программирования. Следует подчеркнуть, что оптимальное решение исходной задачи может быть получено прежде, чем допустимая область сократится до размеров выпуклой оболочки. К тому же, поскольку оптимальное целочисленное решение определяется пересечением п гиперплоскостей, таких гиперпло­скостей существует не более, чем это необходимо; некоторые из них могут быть ограничениями исходной задачи.

Рис, 13.1.

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

х = А (-хn ), (2)

где х — вектор-столбец с компонентами Х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, … . . .

, п + т) и a0 j ≥ 0 (j' = 1, . . ., n). (Для получения исходного двойственного допустимого решения введем дополнительное огра­ничение xn + m+1 == М — X1 —x2 — . . . — xn ≥ 0, где M — до­статочно большая константа, и проделаем одну итерацию с этой строкой и лексикографически минимальным столбцом в качестве ведущего.

) Если аi0 ≥ 0 и целые для всех i, то получено оптимальное решение целочисленной задачи. В этом случае решение получается сразу, без использования ограничений целочисленности. Если аi0 ≥ 0, но не все целые, добавим к ограничениям (1) еще одно. Новое ограничение записывается внизу таблицы так, чтобы она перестала быть прямо допустимой, т. е.

аi0 1 имеем [1/λ]=0[2] и уравнение (8) приобретает вид

(10)

Уравнение (10) должно выполняться для любого допустимого целочисленного решения задачи (1). Заметим, что если а0 < О,. то [a0 /λ] < 0 в уравнении (10). Поэтому уравнение (10) может использоваться в качестве ведущей строки в двойственном сим­плекс-методе. В частности, всегда можно выбрать λ достаточно большим, так чтобы ведущий элемент [aj /λ] в строке (10) стал:

равным —1, что позволит сохранить целочисленность таблицы. Выбор соответствующего λ будет влиять на скорость сходимости алгоритма. Прежде всего опишем сам алгоритм.

В качестве началь­ного необходимо взять двойственно допустимое решение, которое-можно получить добавлением ограничения xn + m+1 = М — x1 — … …

—xn , где М — достаточно большая константа, и про­ведением одной итерации с добавленной строкой и с лексикогра­фически минимальным столбцом, взятыми в качестве ведущих. Алгоритм состоит из следующих шагов.

Ш а г 0. Начать с двойственно допустимой матрицы А° в урав­нении (2), элементы которой — целые числа (как будет видно из дальнейшего, матрица А° может содержать и нецелые элементы).

Шаг 1. Среди строк с аi0 < 0 (i = 1, . . ., n+m) выбрать строку с наименьшим значением i; эта строка станет производя­щей. (Если аi0 ≥ 0 (i= 1, . . ., n + m), то задача решена.)

Ш а г 2. Выбрать λ > 0 (правило выбора будет описано даль­ше) и написать внизу таблицы дополнительную строку

Эта строка выбирается в качестве ведущей.

Ш а г 3. Провести шаг двойственного симплекс-метода, вычерк­нуть дополнительную строку и вернуться к шагу 1.

Доказательство конечности. Доказательство конечности про­водится в предположении, что существует нижняя граница целевой функции x0 . Использование двойственного метода гарантирует выполнение условия

Если a00 уменьшается, то уменьшается на целое число, поскольку все числа остаются целыми, и, следовательно, через конечное число шагов a00 станет меньше x0 .

Если алгоритм бесконечен, то a00 должно оставаться Неизменным для всех t > to. Рассмотрим тогда компоненту a10 , столбца α0 . Если a10 уменьшается, то на целое число.

Когда a10 становится отрицательным, первая строка должна быть выбрана в качестве производящей. Если а1 j < О для всех j, то задача неразрешима.

Теперь опишем правило выбора λ в шаге 2 полностью цело­численного алгоритма. Пусть производящая строка имеет вид

и дополнительная строка

Для любого аj 1).

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

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

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

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

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

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

— целые .

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

.

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

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

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

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

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

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

,.

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

Коммивояжер должен посетить один, и только один, раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарную длину пройденного пути.

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

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

,.

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

Заключение .

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

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

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

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

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

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

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

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

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

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

[1] Символ (≡) означает «сравнимость».

[2] Если λ > 1, то для получения отсечения (10) из (4) требуется только неотрицательность левой части уравнения (4). Следовательно, любая поло­жительная линейная комбинация строк таблицы может служить произво­дящей строкой.

Источник: https://www.bestreferat.ru/referat-396985.html

������ �� ����: �������������� ����������������

Работа По теме: «Целочисленное программирование»

���������� ��������������� �������-������������� �����������

���������� ������

�� ����: �������������� ����������������

���������: ��������� 2 ����� ���

��������� �.�.

���������: ����� �.�.

�������� �.�.

������� 2003�.

����:

��������.

1.������������� ����������������. ����� �������.

2.����� ������.

3.����� ������ � ������.

4.����������� �������� �������������� ����������������.

5.��������� ������������� ��������.

6.������ � �������.

7.������ � ����������.

8.������ ������������.

����������.

������ ������������ ����������.

�������.

��� ������������ ������ ���� ����� ����������� ����������� � ������� ���������� ��������� ���������� ��������������� ������������ ����������. ����� ������ ���������� �������� �������������� ����������������.

��� ������� �������������� ���������������� (��) ���������� ������, � ������� ��� ��� ��������� ���������� ������ ��������� ����� ��������. � ��� ������, ����� ����������� � ������� ������� ������ ������������ ����� �������� �����������, ������ �������� ������������� ������� ��������� ����������������.

� ��������� ������, ����� ���� �� ���� ����������� ����� ����������, ��� ����� ������������� ������� ����������� ����������������. ������ ������� � ������� �� ������ ���, ��� �� ������ ������������ ������� ���������� �������� ������������� ������� ����� ������������ ���� �������� ������� ����������.

������������� ���������������� �������� � 50-60-� ���� ������ ���� �� ���� �������� — ������� ������� � ������� ������������ ����������� ��.������� � �.������.

������������� ������������� ���������������� ����������� ���������� �� ��������� ����� �� ������ ������ � ������� �������������� ����������� ,������ ����� ��������� ����������������.

������, � ��������� ����� ������������ � ���� ����������� ��� ���� ���������� ���������� ���������� ����� �����.

������ ������ ���� ������ ���������, ��� ��� � �� ������� �������� ������ ������������� �������� , ����������� � ���������, �������, ������� ���� � ������ ��������. � ���������� ���, ������ �� ������������������ ��������� ������� � ������� ������ ���� � � ���������� � �����.

������������� ����������������. �������� �������.

��� ������������ ������ ���� ����� ����������� ����������� � ������� ���������� ��������� ���������� ��������������� ������������ ����������. ����� ������ ���������� �������� �������������� ����������������.

������������� (������ ��� �������� ����� ����������) ����������������� ���������� ������ ��������������� ����������������, ��������� ������������� ������, � ������� �� ������� ���������� ������������� ������� ���������������, � ������� ���������� ������� �������.

�������� ���������� ������������� ����� ����� ����������, ���� ����� ������������� ��������, ��� �������, ��� ������� � ���������� ������������ ������ ��������� �������: ��������, ������ ��������� ��� � ��������� ������, ������ ������� ���������� � �.�.

� ���� ������� ����� ������ �������� �������� ��������, ��������, ����������� �������, � ����������� ����������� �� ����� �����.

������ ����� ������ ��������, ����� ��������� ������� ���������� ����� ����� ����� ����� ������ (��������, �������� �������); � ��������� ������ �� ����� ������ ������������ ��������� � ������������� ����������� �������. ������� ����������� ����������� ������ ������� ������������� �����.

������������ �� ������������ � ������� ��

  1. ���������� ������������� ���������� ��������� ��������� ��������. ��������, ������������� ����������, �������� ������� ������ ���� �� ����� 20, ����� ������������� ��� �����������.
  2. � ������� �� ����� ����� ��, ���������� ����� ����������� �������� ���������� ������������� ����������, ������ ��������� ����� ������� ����� ��.
  3. ���� ��� ������ ������������� � ���������� ������� ������������ �������������� �������, ������������� �� ������������ �������, ��������, 3%. ����� ���������� ������ ������ � ������ ��� ������ ������������ ����� �����������, ���� ��������� ������� ����� ������� � ������ ������ � ������� ������� ������ 0,03.

����� ������ � ������ ����� ��������� ��� ������� ����� ����������� ����������������.

�����������

������ �������������� ���������������� ����� ���� �������������� ��������� �������: ����� �������� ��� ������� �������

(7.1)

��� ��������

(7.2)

Xj > 0, j = 1, 2, …, n, � ����� ��� �������������� �������

j � ����� �����.

� ��������� ������� ������� (7.4) ���������������� ������ �� ����� ����������, ����� ������ ���������� �������� ��������������.

��� ������� ����� �������������� ���������������� ����������� ����������� ������. � ��� ��������� ����� ��������� (����� ������) � ����� ������ � ������.

� ������ ������ ������ �������� ����, ��������� � ���, ��� ������� �������� ������ ��������� ���������������� (7.1)�(7.3) ��� ����� ������� ���������������. ���� ���������� ����� ������� ������� �������������, �� ��� ����������� �� ����������� ���� ������ (7.I)�(7.4).

���� ������� ���������������, �� ������� ����������� ����������� ��������, ������� �������� �� ��������� ������ ������ ��������������� ����������� ����, �� ��� ���� ��������� ������������� ������� ��������� ������. ����� �������� ������ ��������� ���������������� � �������������� ��������.

���� ���������� ����� ������� ������� �������������, �� ��� ���������� � ��� ������ (7.1)�(7.4). ���� �� � ����� ����� �� ��� ���� ���������� ����������� ������� ���������������, �� �������� ����� �������-���������.

�������-��������� ���������� ����� �������, ����� �� �������� ����� ����� ������ � �������������� �������, ���� ��� � ������ ������ ����������. ���� �� ���������� ���������� ����� �������-��������� ��� ��������� ������.

���������� ��������� ��������. ����� �������� ������� ������ (7.1)-(7.3) ��� ����� ��������������� � ����� � ������ r ����������� ������� � ����������� �������� ���������� ��������������� ���������� �������� ����� r0. � ���� ������ � �������� (7.1)�(7.3) ��������� �������, ����������� ������� �.

��� ����������� ����� �������-��������� ���������� �-� ��������� �� ��������� ����������� �������, ���������� ����������� �������,

(7.5)

����� ������ ������� ����� � ������� ������ ����� r0 rj , ��� ���� ������� ��� ����� � ����:

����� [�r0 ] [arj ] — ����� �����, a qt , qr ] — ������� ����� ����� r j � ar j.

��������, 37 /3 =12 +1/3 , ��� ��� [37 /3 ] = 12, a -s /, = -3 + 1/3� ��� ��� [-8/3] = -3.

�� ��������� (7.5) ������ r

xr =�r0 —

������ ����� �� � �rj ������� ������� ����� � ������� ������:

xr =

�����������, ��� ��� xj — ����� �����. ����� ��������

�������� ����� ������.

����� ��������� ����� ������ � r , ���������� ��������������� ��������

�� �

£(/)/) = 42 >£(D1 2 ) = 40. �������������, ���� X�1 = (3, 1) �������� �������� ������ (7.11)-(7.13),

�.�. ���� ����� ��� ������� ������� ����� � ���� ������� ������� �����.

�������� ������ ������ � ������

  1. ������� ������� ������ ��������� ���������������� ��� ����� ���������������.
  2. ���������� �������������� ����������� �� ������� ���������� �����.
  3. ������� ������� ���� ����� � ������������� �� ����������.
  4. ������ � ������ ������������� �������������� �����������, �������� ��������� ������� ������� �������� ����������� ������������� ���� ���� ������������� �������������� ������.

����������� �������� �������������� ����������������

���������� ��������� ������ ��������� ����������������:

���������������

X0 =a00 -a01 x1 -a02 x2 -��..-a0n xn ,

��� �������

xn+1 =an+1,0 -an+1,1 x1 -an+1,2 x2 -��.-an+1,n xn,

.

.

xn+m =an+m,0 — an+m,1 x1 -an+m,2 x2 -��.-an+m,n xn ,

xj ≥0 (j=1,��.,n+1,��.,n+m).

�������, ��� xn +1 , . ., n+ m � ������ ����������, a x1 … ., n � �������� ���������� ������ (1). ���� ������ � ������������� (1) �����������, ����� ��� j , (j'=1, . . .

, �) ���� ������, �� ������ ����� ���������� ������� �������������� ����������������. ���������� ������� ���������� �����, �������� �������������, ������� ����� �������������� ��� ������ �������������� ����������������.

����������� (1) ���������� �������� ������� OABCD � n-������ ������������, ��� �������� �� ���. 13.1. ���� ������������� ������� �� ���. 13.1 ���������� �������. ����� �����, ������������� ������ ������� OABCD, �������� ����������� ��������� ������ �������������� ����������������.

������������ ������� ������ ��������� ���������������� ������ ������������� �� ������� ������� �������. � ������ ������ ��������� ����� �� �������� ���� ����������� ���������, ��������� �� ���� �� ��� �� ������������.

�����������, ��� ������� ���������� ������� ������ �� �������� �������� ���������� ����� ����� ������ ���������� �������. �� ���. 13.1 ��� �������� �������� �������� ���������� �������� OEFGH. ��� ���������� ������� ����� ������������� ��� ������� ���������� ������� ��������� ������ ������ ��������� ����������������.

�������������, ���� � ������ ��������� ����������������, ������������ ���������� ������� OABCD, �������� ����������� ���� RR', ��� �������� �� ���. 13.1, �� ����� ���������� ������ ����� ����� OEFGH � �������� ������� ���������� �������.

����� ����� ���������� ������� �������� ����� ������� ����������: ��-������, ��� �������� ��� ���������� ������������� ����� �������� ������ ��������� ���������������� (��������� ��� �������� �������� ��������� ���� �����), ��-������, ��� ������� ����� ����� ������� � ������������.

������� ����� �������� ����������� ������� ���������������� ������ ��������� ���������������� ����� ������ ������������ ����� ����� � �������� ����������� �������� �������� ������ �������������� ����������������.

������ ��������� �������������� ����������������, ������� ����� ������� ����, ��������� ������ ���������������� �������� �������������� ����������� � ����� �������� �������� ���������� ������� � �������� �������� �� ���������� ������������� �����.

��� ������ ��� ����� �������, ����� ������ ���������������� ������ ��������� ���������������� ������ ������� �������, � ���������� �������� ����������� ������� ������������� ����� �������������.

�������������� ���� ������������� �������� �������� ���������� ����������: 1) ��� �������������� ����������� ��������� ���������� ����� �������� ������������� ������; 2) �� ��������� ����� ����� ��������� ����������� ���������� ��������������� ����������� ��� ����, ����� ����������� ������� ���������������� ������ ���� �������������; 3) �������������� ����������� (��������������) �������� �� ������� ���� ����� ���� ������������� �����, ���� � �� ����������� ����������� ������ �������� ��������; 4) ������ ����� ����������� ��������� ������� ���������� ������� �������� ������ �������������� ����������������. ������� �����������, ��� ����������� ������� �������� ������ ����� ���� �������� ������, ��� ���������� ������� ���������� �� �������� �������� ��������. � ���� ��, ��������� ����������� ������������� ������� ������������ ������������ ���������������, ����� ��������������� ���������� �� �����, ��� ��� ����������; ��������� �� ��� ����� ���� ������������� �������� ������.

���, 13.1.

������ � ����������� ������ (1) ���������� � ����������� ����������� xj=�(�Xj ) (j'=1, …,n), � ������ � ��������� ����� ��������� ���

� = � (-�n ), (2)

��� � � ������-������� � ������������ �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, … . . .

, + �) � a0 j ≥ 0 (j' = 1, . . ., n). (��� ��������� ��������� ������������� ����������� ������� ������ �������������� ����������� xn + m+1 == � � X1 �x2 � . . . � xn ≥ 0, ��� M � ���������� ������� ���������, � ��������� ���� �������� � ���� ������� � ����������������� ����������� �������� � �������� ��������.

) ���� �i0 ≥ 0 � ����� ��� ���� i, �� �������� ����������� ������� ������������� ������. � ���� ������ ������� ���������� �����, ��� ������������� ����������� ���������������. ���� �i0 ≥ 0, �� �� ��� �����, ������� � ������������ (1) ��� ����. ����� ����������� ������������ ����� ������� ���, ����� ��� ��������� ���� ����� ����������, �. �.

�i0 1 ����� [1/λ]=0[2] � ��������� (8) ����������� ���

(10)

��������� (10) ������ ����������� ��� ������ ����������� �������������� ������� ������ (1). �������, ��� ���� �0 < �,. �� [a0 /λ] < 0 � ��������� (10). ������� ��������� (10) ����� �������������� � �������� ������� ������ � ������������ ��������-������. � ���������, ������ ����� ������� λ ���������� �������, ��� ����� ������� ������� [aj /λ] � ������ (10) ����:

������ �1, ��� �������� ��������� ��������������� �������. ����� ���������������� λ ����� ������ �� �������� ���������� ���������. ������ ����� ������ ��� ��������.

� �������� ����������� ���������� ����� ����������� ���������� �������, �������-����� �������� ����������� ����������� xn + m+1 = � � x1 � … …

�xn , ��� � � ���������� ������� ���������, � ����������� ����� �������� � ����������� ������� � � ����������������� ����������� ��������, ������� � �������� �������. �������� ������� �� ��������� �����.

� � � 0. ������ � ����������� ���������� ������� �� � ��������� (2), �������� ������� � ����� ����� (��� ����� ����� �� �����������, ������� �� ����� ��������� � ������� ��������).

��� 1. ����� ����� � �i0 < 0 (i = 1, . . ., n+m) ������� ������ � ���������� ��������� i; ��� ������ ������ �������������. (���� �i0 ≥ 0 (i= 1, . . ., n + m), �� ������ ������.)

� � � 2. ������� λ > 0 (������� ������ ����� ������� �������) � �������� ����� ������� �������������� ������

��� ������ ���������� � �������� �������.

� � � 3. �������� ��� ������������� ��������-������, ���������� �������������� ������ � ��������� � ���� 1.

�������������� ����������. �������������� ���������� ���������� � �������������, ��� ���������� ������ ������� ������� ������� x0 . ������������� ������������� ������ ����������� ���������� �������

���� a00 �����������, �� ����������� �� ����� �����, ��������� ��� ����� �������� ������, �, �������������, ����� �������� ����� ����� a00 ������ ������ x0 .

���� �������� ����������, �� a00 ������ ���������� ���������� ��� ���� t > to. ���������� ����� ���������� a10 , ������� α0 . ���� a10 �����������, �� �� ����� �����.

����� a10 ���������� �������������, ������ ������ ������ ���� ������� � �������� ������������. ���� �1 j < � ��� ���� j, �� ������ �����������.

������ ������ ������� ������ λ � ���� 2 ��������� �������������� ���������. ����� ������������ ������ ����� ���

� �������������� ������

��� ������ �j 1).

������ � �������

��������� ���������� m �������� ������������ ��� ��������� n ����� ��������� . ���� ��������� ��������������� ��������� �����������, �.�. �� ����� ����� � ���������� 0, 1, 2, … ������. ����� — ������ i-�� ������ ��� ��������� ������� j-�� ���������. ��������� ����� ���������� ������� j-�� ���������. ��������� ����� ���� ���������, ��� ������� ��������������� ����� ���������� �����.

������ ������ ������ ���:

��� ������������ �� ����������� �������

������� �����������������

������� ���������������

— ����� .

����� ��� ��������� ������� ���� ����� � ������ ��� ��������� ����� ���� ���� ��� ���, �� ������ ������ ��������� ���:

.

������ � ����������

����� n ������������, ������� ����� ��������� n ��������� �����. �������� ���������� , ��������� � ����������� i-� ������������ j-� ������ . ���������� ��������� ������������ �� ������ ���, ����� �������� ������������ ����������, ��� �������, ��� ������ ����������� ����� ���� �������� ������ �� ���� ������ � �� ������ ������� ������ ���� ��������� ������ ���� �����������.

�������������� ������ ������ ������ ���:

������ ����������� ����������� ������ �� ���� ������:

�� ������ ������ ����������� ������ ���� �����������:

������� ����������������� � ���������������

, .

������ ������������

����������� ������ �������� ����, � ������ ����, ��� ������ �� n ������� � ��������� � �������� �����. ��� ������� ������ �������������� ��������� ����� ����������� ����.

�������������� ������ ������:

������� ����������������� � ���������������

, .

����������� ������� ����������� �������� ����� ��� ������, �.�. ��� ���������� ������� �����������. �����, ������� ������ ������������ ����� ��������� �������, ��� ����������� � �������-������.

���������� .

� ������ ������ ���� ����������� �������� �������������� ����������������. ��������� ����������� ������ ������� ������������� �����. ����� ������ ��������� ��� ������������� ������������� ���������������-�������������, �����������, ������� � ������ ��������. � �� �� ����� ��� ������� ����� ���������� ����� ���� ������������� ��� ������������� ������������� ������.

������ ������ ���� ������ ���������, ��� ��� � �� ������� �������� ������ ������������� �������� , ����������� � ���������, �������, ������� ���� � ������ ��������. ��� ������ ��������� � � �������������� ����� ������. � ���������� ���, ������ �� ������������������ ��������� ������� � ������� ������ ���� � � ���������� � �����.

������ �������������� ����������:

1. �.��������. ������ ��������� � �������������� ����������������: � 2-� �����.; ������� � �����������. 1991�. 360�.

2. �.��. ������������� ���������������� � ������ � �����.; ������� � �����������. 1974�.

3. �.�.��������, �.�.�������, �.�.�����. ������ ����������: �������������� ����������������. ������ — 2-� �������. 2001�. 351�.

4. �.�.��������. �������������� ����������������: ������� ������� � 5-� �������, ���������-�:������, 2001�.-264�.

5. �.�.��������. �������� � �������� ������ � ������������� ����������������. �.:������������ ���, 1977�.

6. �.�. ��������, �.�.������, �.�.����������.: ���������-�������������� ������ � ���������� ������: ����.������� ��� �����/�����, 1999�.-391�.

7. �.�. ������, �.�.�����, �.�.������, �.�.�������; ��� ���. ����.�.�.�������. : ������������ �������� � ���������; ����. ������� ��� �����.

[1] ������ (≡) �������� �������������.

[2]

����������   ..  280  281  282   ..

Источник: https://zinref.ru/000_uchebniki/04600_raznie_3/783_lekcii_raznie_09/281.htm

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

Работа По теме: «Целочисленное программирование»

    ВВЕДЕНИЕ 

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

     Под задачей целочисленного программирования (ЦП) понимается задача, в которой все или некоторые переменные должны принимать целые значения.

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

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

     Целочисленное программирование возникло в 50-60-е годы нашего века из нужд практики —  главным образом в работах американских математиков Дж. Данцига и Р. Гомори.

Первоначально целочисленное программирование развивалось независимо от геометрии чисел на основе теории и методов математической оптимизации, прежде всего линейного программирования.

Однако в последние время исследования в этом направлении все чаще проводятся средствами математики целых чисел.

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

     В курсовой работе рассмотрено понятие целочисленного программирования, а так же описан один из методов решения задач целочисленного линейного программирования – метод ветвей и границ.

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

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

  1. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

 

    1.1 Общие понятия целочисленного программирования 

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

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

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

Однако такой подход оправдан, когда отдельная единица составляет очень малую часть всего объема (например, товарных запасов); в противном случае он может внести значительные искажения в действительно оптимальное решение [1].

     Целочисленное линейное программирование (сокращенно ЦЛП) занимается задачами линейного программирования с целочисленными переменными, общая задача формулируется следующим образом: найти тах{сх|Ах ≤ b; х — целочисленный}.

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

Иными словами, в ЦЛП рассматриваются совместные ограничения – не отрицательность и целочисленность [3].

     Специфика задач целочисленного программирования заключается в том, что на переменные xi и функцию цели F(x) налагается дополнительное ограничение – условие целочисленности.

Целочисленное программирование иногда называют дискретным программированием.

Если требование целочисленности распространяется не на все переменные, а только на часть из них, то задача называется частично целочисленной [2].

     В большинстве случаев целочисленные задачи сильно отличаются от своих непрерывных аналогов и требуют для решения специальных методов. Условно методы решения задач целочисленного программирования можно разделить на три основных группы: методы отсечения; комбинаторные методы; приближенные методы.

     Процедура решения задачи методом отсечения осуществляется следующим образом:

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

     2. Строятся дополнительные линейные ограничения, отсекающие от ОДЗП ту её часть, в которой содержится оптимальное решение и не содержится ни одного целочисленного решения.

     3. В исходную задачу включается дополнительное ограничение и применяется симплекс-процедура. Если же найденное оптимальное решение опять будет дробным, то формируется новое дополнительное ограничение и процесс вычислений повторяется [1].

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

  1. Количество целочисленных переменных уменьшать насколько возможно. Например, целочисленные переменные, значения которых должно быть не менее 20, можно рассматривать как непрерывные.
  2. В отличие от общих задач ЛП, добавление новых ограничений особенно включающих целочисленные переменные, обычно уменьшают время решения задач ЦП.
  3. Если нет острой необходимости в нахождении точного оптимального целочисленного решения, отличающегося от непрерывного решения, например, 3%. Тогда реализацию метода ветвей и границ для задачи максимизации можно заканчивать, если отношение разницы между верхней и нижней границ к верхней границы меньше 0,03 [4].

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

     К частному случаю задачи целочисленного линейного программирования относятся задачи, где переменные X могут принимать всего лишь два значения — 0 и 1. Соответствующие задачи часто называют задачами булевского программирования.

Наиболее известные из этих задач — задача о назначениях (какого работника на какую работу поставить), задача выбора маршрута (задача коммивояжера, задача почтальона), задача о максимальном паросочетании и т. д.

Целочисленное программирование применяется при решении задачи оптимизации развития компании, в которой 0 или 1 означают покупку какого-либо оборудования.

     Для решения задач этого типа разрабатываются специфические алгоритмы, основанные на комбинаторике, графах и т. д. [5] 

    1. Постановка  задачи целочисленного программирования

 

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

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

     Задача линейного целочисленного программирования формируется следующим образом: найти такое решение (план) X = (x1,x2,…,xn), при котором линейная функция

        (1)

принимает максимальное или минимальное значение при ограничениях

     =bi, i=1, 2…, m.   (2)

           хj ³ 0, j=1, 2,…, п.   (3)

     xjцелые числа   (4)

     Для наглядности рассмотрим пример решения задачи целочисленного программирования: [3]

     Задача о выборе оборудования. На приобретение оборудования для нового участка цеха выделено 20000 долларов США. При этом можно занять площадь не более 38 м2. Имеется возможность приобрести станки типа А и станки типа Б.

При этом станки типа А стоят 5000 долларов США, занимают площадь 8 м2 (включая необходимые технологические проходы) и имеют производительность 7 тыс. единиц продукции за смену. Станки типа Б стоят 2000 долларов США, занимают площадь 4 м2 и имеют производительность 3 тыс. единиц продукции за смену.

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

     Решение: Пусть Х — количество станков типа А, а У — количество станков типа Б, входящих в комплект оборудования. Требуется выбрать комплект оборудования так, чтобы максимизировать производительность С участка (в тыс. единиц за смену):  

      С = 7 Х + 3 У → max .

     При этом должны быть выполнены следующие ограничения:

по стоимости (в тыс. долларов США)

     5 Х + 2 У ≤ 20,

по занимаемой площади (в м2 )

     8 Х + 4 У ≤ 38,

а также вновь появляющиеся специфические ограничения по целочисленности, а именно,

     Х ≥ 0 , У ≥ 0 , Х и У — целые числа.

     Сформулированная математическая задача отличается от задачи линейного программирования только последним условием целочисленности.

Однако наличие этого условия позволяет (в данном конкретном случае) легко решить задачу перебором. Действительно, как ограничение по стоимости, так и ограничение по площади дают, что Х ≤ 4.

Значит, Х может принимать лишь одно из 5 значений: 0, 1, 2, 3, 4.

     Если Х = 4, то из ограничения по стоимости следует, что У = 0, а потому С = 7 Х = 28.

     Если Х= 3, то из первого ограничения вытекает, что У ≤ 2, из второго У ≤ 3. Значит, максимальное С при условии выполнения ограничений достигается при У =2, а именно С = 21 + 6 = 27. 

     Если Х= 2, то из первого ограничения следует, что У ≤ 5, из второго также У ≤ 5. Значит, максимальное С при условии выполнения ограничений достигается при У =5, а именно С = 14 + 15 = 29.

     Если Х= 1, то из первого ограничения имеем У ≤ 7, из второго также

У ≤ 7. Значит, максимальное С при условии выполнения ограничений достигается при У = 7, а именно С = 7 + 21 = 28.

     Если Х= 0, то из первого ограничения вытекает У ≤ 10, из второго У ≤ 9. Значит, максимальное С при условии выполнения ограничений достигается при У = 9, а именно, С = 27.

     Все возможные случаи рассмотрены. Максимальная производительность. С = 29 (тысяч единиц продукции за смену) достигается при Х = 2, У = 5. Следовательно, надо покупать 2 станка типа А и 5 станков типа Б.  

     1.3 Методы решения задач целочисленного программирования 

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

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

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

Источник: https://student.zoomru.ru/math/celochislennoe-programmirovanie/32894.247528.s1.html

Refy-free
Добавить комментарий