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

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

СОДЕРЖАНИЕ

1.Введение

2.Основная часть

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

2.1.1 Постановка задачи. Метод Гомори

2.1.2 Каноническая форма

2.1.3 Приведение к канонической форме

2.1.4 Метод решения задач

2.2 Метод Гомори

2.3 Решение задачи методом Гомори

3.Заключение

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

1. Введение

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

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

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

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

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



2. Основная часть

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

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

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

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

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

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

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

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

2.2 Постановка задачи

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

2.3Каноническая форма

Будем рассматривать каноническую задачу целочисленного программирования с n переменными и m условиями, дополненную условием целочисленности: Где c = (c1, c2, … , cn), x = (x1, x2, … , xn) - вектора размерности n, - их скалярное произведение (), называемое так же целевой функцией, A - матрица размерности n ґ m, b - вектор-столбец размерности m.

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

Будем считать, что множество X планов задачи (без условия целочисленности) ограничено, то есть является многогранником. Из этого условия вытекает, что множество X* всех целочисленных планов задачи конечно. Будем предполагать, что все коэффициенты cj, j=1, 2, …, n, целевые функции - целые числа. Из условия II вытекает, что для всякого целочисленного плана xОX* значение максимизируемой линейной формы - целое число. В этом случае говорят, что гарантирована целочисленность целевой функции. Хотя условия I и II на задачу довольно жесткие, ослабить их, для получения необходимых результатов, можно лишь немного.

2.4 Приведение к канонической форме

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

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

2.5 Метод решения задач

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

1) Поставленную описательную задачу переводят в математическую форму (целевая функция и ограничения).

2) Полученное математическое описание приводят к канонической форме.

3) Каноническую форму приводят к матричному виду.

4) Ищут первое допустимое решение. Для этого матрица должна быть правильной. Матрица в ЗЛП называется правильной, если она содержит минимум m правильных (базисных) столбцов, где m - число строк в матрице. Столбец в канонической ЗЛП называется правильным (базисным), если все его элементы равны нулю, кроме единственного, равного единице.

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

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

2.6 Метод Гомори

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

В общем случае задача целочисленного программирования формулируется следующим образом. Найти максимум или минимум функции

,

при условиях

, .

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

Пусть -е ограничение задачи, находящееся в последней симплексной таблице, имеет вид

,

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

Тогда дополнительное ограничение имеет вид

, (3)

где - дробная часть ; - дробная часть .

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

.

Например, для числа целая часть , дробная часть равна . Для числа целая часть , дробная часть равна . Дробная часть числа всегда неотрицательная и меньше единицы.

В неравенство (3) вводится дополнительная переменная , получается уравнение

.

В систему ограничений задачи это ограничение записывается в виде



.

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

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

2.7 Решение задачи методом Гомори

Предприятие выпускает три вида изделий - A, B и С. Для их производства необходимо три вида ресурсов - R1, R2, R3. Для производства изделия A необходима 1 единица ресурса R1, 4 единицы ресурса R2 и 3 единицы ресурса R3. Для производства изделия B необходимо 2 единицы ресурса R1, 3 единицы ресурса R2 и 1 единица ресурса R3. Для производства изделия С необходимо 3 единицы ресурса R1, 2 единицы ресурса R2, и 1 единица ресурса R3. У предприятия на складе есть 35 единиц ресурса R1, 45 единиц ресурса R2 и 40 единиц ресурса R3. Сколько и каких изделий нужно выпустить предприятию, чтобы его прибыль была максимальной, если от продажи изделия A предприятие получает прибыль 4 рубля, от продажи B - 5 рублей, а от продажи изделия С - 10 рублей.

По условию задачи составим таблицу (Таблица 1).



Таблица 1.

Ресурс	Изделие A	Изделие B	Изделие C	Сколько ресурса на складах
R1	1	2	3	35
R2	4	3	2	45
R3	3	1	1	40
Прибыль	4	5	6

Составим систему ограничений. Обозначим за x_A,x_B и x_C количество производимых изделий A, B и C.

x_A, x_B, x_C >= 0

F(x_A, x_B, x_C) = 4x_A + 5x_B + 6x_{C max}

Приведём задачу к каноническому виду, заменив неравенства на равенства. Для этого добавим дополнительные неотрицательные переменные x₁, x₂, x₃.

x_A, x_B, x_C, x₁, x₂, x₃ >= 0

F(x_A, x_B, x_C) = 4x_A + 5x_B + 6x_{C max}

Запишем симплекс-таблицу (Таблица 2).

x₁, x₂, x₃ - базисные переменные



Таблица 2.

	xA	xB	xC	x1	x2	x3	B
x1	1	2	3	1	0	0	35
x2	4	3	2	0	1	0	45
x3	3	1	1	0	0	1	40
f	-4	-5	-6	0	0	0

Разрешающий элемент находится на пересечении x₁ и x_c.

Итерация 1.

Таблица 3.

	xA	xB	x1	xC	x2	x3	B
xC	1/3	2/3	1/3	1	0	0	35/3
x2	10/3	5/3	-2/3	0	1	0	65/3
x3	8/3	1/3	-1/3	0	0	1	85/3
f	-2	-1	2	0	0	0	70

Разрешающий элемент итоговой таблицы (Таблица 3) находится на пересечении x₂ и x_A .

Итерация 2.

Таблица 4.

	x2	xB	x1	xC	xА	x3	B
xC	-1/10	1/2	2/5	1	0	0	19/2
xA	3/10	1/2	-1/5	0	1	0	13/2
x3	-4/5	-1	1/5	0	0	1	11
f	3/5	0	8/5	0	0	0	83

Отрицательных элементов в строке f итоговой таблицы (таблица 4) нет, значит, этап решения симплекс методом завершён.

x_А = 13/2, x_B = 0, x_C = 19/2

x^* = (13/2, 0, 19/2)

Проверим, верно ли решение.

f^* = 4*13/2+5*0+6*19/2 =26+57=83

Итерация 3.

Значения получились нецелые , следовательно необходимо Применить метод Гомори. Согласно которому, к задаче следует добавить дополнительное ограничение.

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

Дробная часть x_А = 1/2, x_C = 1/2

Составляем ограничение для x_C.

q_C?q_CA?x_A?q_CB?x_B?q_CC?x_C?q_C1?x₁?q_C2?x₂?q_C3?x₃?0

Для нахождения q используем числа 1й строки таблицы, так как там содержатся данные переменной x_C.

Подставив коэффициенты получим ограничение:

1/2?1/2?x_B?2/5?x₁?9/10?x₂?0

Приведем его в каноничный вид, добавив неотрицательную переменную x₄:

?1/2?x_B?2/5?x₁?9/10?x₂+x₄=?1/2

Занесём ограничение и столбец x₄ в симплекс-таблицу (Таблица 5).

Таблица 5.

	x2	xB	x1	xC	xА	x3	x4	B
xC	-1/10	1/2	2/5	1	0	0	0	19/2
xA	3/10	1/2	-1/5	0	1	0	0	13/2
x3	-4/5	-1	1/5	0	0	1	0	11
x4	-9/10	-1/2	-2/5	0	0	0	1	-1/2
f	3/5	0	8/5	0	0	0		83

По правилу Гомори убирать надо всегда только что введённую переменную (x₄). Для определения переменной, которую необходимо ввести найдём частные от деления строки F на предпоследнюю строку и находим наименьшее значение.

Таблица 6.

	x2	xB	x1	xC	xА	x3	x4	B
xC	-1/10	1/2	2/5	1	0	0	0	19/2
xA	3/10	1/2	-1/5	0	1	0	0	13/2
x3	-4/5	-1	1/5	0	0	1	0	11
x4	9/10	-1/2	2/5	0	0	0	1	-1/2
f	3/5	0	8/5	0	0	0	0	83
f/x4	2/3	0	4	-	-	-	-

В таблице 6 видно, что наименьшее значение у столбца с переменной x_B. Определяющее число находится на пересечении x_B и x₄.

После всех действий получаем итоговую таблицу. (Таблица 7)

Таблица 7.

	x2	x4	x1	xC	xА	x3	xB	B
xC	0	1	0	1	0	0	0	9
xA	-3/5	1	-3/5	0	1	0	0	6
x3	1	-2	1	0	0	1	0	12
xB	4/5	-2	9/5	0	0	0	1	1
f	3/5	0	8/5	0	0	0	0	83

целочисленный программирование линейный гомори

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

x_А = 6

x_B = 1

x_C = 9

Проверим, верно ли решение:

f^*=4*6+5*1+6*9=83

83=83

Решение верно



3.Заключение

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

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



Список литературы

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

2. А.А.Копанева, А.В. Овсянникова, И.Ф.Авдеев. Математические методы в экономике. Учебно-методическое пособие для студентов экономических специальностей. 2009г.

3. Конюховский П.В. Математические методы исследования операций в экономике, СПб.: Питер, 2008.

4. Лященко И.Н. Линейное и нелинейное программирование, М.: Наука, 1985.

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

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

...