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

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

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

Введение

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

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

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

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

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

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

2. Подобрать практическую задачу по данной теме.

3. Решить задачу двумя методами из рассмотренных в теоретической части.

4. Сделать вывод о применимости методов целочисленного ЛП на практике.

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

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

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

Математическая формулировка задачи линейного целочисленного программирования следующая: найти такое решение (план):

,

при котором линейная функция:

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



- целые числа, .

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

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

Составим математическую модель этой задачи. Обозначим:

.

Требуется определить максимум функции:

,

при ограничениях по весу и объему:



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

Составим математическую модель этой задачи. Обозначим:

.

Требуется определить максимум функции:

,

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

Пример 3. Задача о раскрое материалов.

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

Обозначим - число единиц материала, раскраиваемых -ым способом, и - число изготавливаемых комплектов изделий.

Экономико-математическая модель задачи следующая: найти такое решение

,

при котором функция:

.

принимает максимальное значение и при этом выполнены требования:

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

Методы целочисленной оптимизации можно разделить на три основные группы:

1) методы отсечения;

2) комбинаторные методы;

3) приближенные методы.

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

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

2.1 Решение задач целочисленного программирования графическим методом

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

После построения области допустимых решений строят вектор направления возрастания целевой функции:

и проводят линии уровня целевой функции, которые смещают параллельно в направлении вектора .

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

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

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

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

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

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

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

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

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

1. Задачу на максимум решают симплексным методом. Условие целочисленности при этом не учитывается.

2. Пусть на последнем шаге решения задачи симплексным методом получена симплекс-таблица (табл. 1), так что оптимальным решением задачи является

.

Таблица 1

Базис		План
			1
			0
			0

Если решение получилось целочисленное, то вычисления прекращаются.

Если, предположим, что - дробное, то:

- если все - целые, то задача не имеет целочисленного решения;

- если существует дробный, то к системе ограничений добавляется дополнительное ограничение (отсечение Гомори).

3. Построение отсечения Гомори.

Предварительно заметим, что любое действительное число можно представить в виде суммы двух его частей:

,

где - целая часть числа (); - дробная часть числа .

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

.

Неравенство необходимо преобразовать в равенство, введением дополнительной неотрицательной переменной:

.

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

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

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

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

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

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

,

а также нижняя граница линейной функции , т.е. при любом плане X .

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

,

где - целая часть числа . В результате из задачи 1 формируют две задачи: 2 и 3, отличающиеся друг от друга тем, что в задаче 2 кроме ограничений задачи 1 добавлено ограничение:

.

А в задаче 3 кроме тех же ограничений добавлено ограничение:

.

Получим список из двух задач: 2 и 3.

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

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

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

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

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

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

Задача. При модернизации оборудования в цехе выделено 64 м2 для установки оборудования первого и второго типов. На установку одного комплекта оборудования первого типа требуется 2 м2, на установку комплекта оборудования второго типа требуется 3,2 м2. Причем, оборудование первого типа приносит ежемесячный доход 2 млн. руб., а оборудование второго типа - 4 млн. Определить количество комплектов оборудования первого и второго типов, обеспечивающее максимальную прибыль, при условии, что предприятие может приобрести не более 20 комплектов оборудования первого типа и не более 11 комплектов оборудования второго типа.

Решение. Обозначим - количество устанавливаемого оборудования первого типа; - количество устанавливаемого оборудования второго типа. Тогда математическая модель задачи имеет вид:

Решим задачу двумя способами.

Первый способ - графический. В системе координат х0y построим прямые:

по точкам (0; 20) и (8; 15);

(прямая, проходящая через точку (20; 0) параллельно оси 0y);

(прямая, проходящая через точку (0; 11) параллельно оси 0x).

Определим область допустимых решений, задаваемую системой неравенств (рис. 1).

Рис. 1

Многоугольник ОАBCD - область допустимых решений. Функция возрастает быстрее всего в направлении вектора . Строим вектор и прямую (линия уровня целевой функции). Перемещаем линию уровня целевой функции по направлению вектору нормали , пока не покинем область в точке B.

Точка B образуется при пересечении прямых:

и . Найдем ее координаты: В (14,4; 11). Максимальное значение в области допустимых решений .

Полученное оптимальное решение нецелочисленное. Для нахождения целочисленного решения заменим область OABCD на область (рис. 1), содержащую все допустимые точки с целочисленными координатами и такую, что координаты каждой из вершин данного многоугольника являются целыми числами. Тогда в области перемещаем линию уровня целевой функции по направлению вектору нормали , пока не покинем область в точке (14; 11). Максимальное значение целевой функции

Второй способ - метод Гомори.

Задачу (5.1) приведем к каноническому виду.

Приведем задачу в каноническую форму:

Находим первоначальный опорный план и применяем симплекс-метод (табл. 2).

Таблица 2

Базис		План	2	4	0	0	0
	0	64	2	16/5	1	0	0	20
	0	20	1	0	0	1	0	-
	0	11	0	1	0	0	1	11
	0	-2	-4	0	0	0
	0	144/5	2	0	1	0	-16/5	72/5
	0	20	1	0	0	1	0	20
	4	11	0	1	0	0	1	-
	44	-2	0	0	0	4
	2	72/5	1	0	1/2	0	-8/5
	0	28/5	0	0	-1/2	1	8/5
	4	11	0	1	0	0	1
	364/5	0	0	1	0	4/5

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

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

.

Найдем дробные части чисел:

;

;

.

Таким образом, дополнительное условие целочисленности для строки :

.

Введем неотрицательную переменную и составим уравнение

.

Составим новую симплекс-таблицу (табл. 3) с дополнительным условием.

Таблица 3

Базис		План	2	4	0	0	0	0
	2	72/5	1	0	1/2	0	-8/5	0
	0	28/5	0	0	-1/2	1	8/5	0
	4	11	0	1	0	0	1	0
	0	-2/5	0	0	-1/2	0	-2/5	1
	364/5	0	0	1	0	4/5	0

Получили недопустимое базисное решение (). Для получения допустимого базисного решения переведем в основные переменные переменную (табл. 4).

Таблица 4

Базис		План	2	4	0	0	0	0
	2	14	1	0	0	0	-2	1
	0	6	0	0	0	1	2/5	-1
	4	11	0	1	0	0	1	0
	0	4/5	0	0	1	0	4/5	-2
	72	0	0	1	0	0	2

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

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

Заключение

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

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

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

экстремум математический целочисленный линейный

Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. - М.: Высш. шк., 1986. - 319с.

2. Бездудный Ф.Ф., Павлов А.П. Математические методы и модели в планировании текстильной и легкой промышленности: Учебник для вузов. - М.: Легкая индустрия. 1979. - 440с.

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

4. Киселев В.Ю. Экономико-математические методы и модели / В.Ю. Киселев Иваново: ИГЭУ, 1998.

5. Кузнецов Б.Т. Математические методы и модели исследования операций: учеб. пособие для студентов вузов. - М.: ЮНИТИ-ДАНА, 2005. - 390с.

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

...