Реализация целочисленных моделей принятия решений
Реализация целочисленных моделей принятия решений
Содержание
Введение
1. Метод отсекающих плоскостей
2. Применение метода отсекающихплоскостей
3. Геометрическая интерпретация метода Гомори
4. Компьютерная реализация
Литература
Приложение
Введение
Существует ряд задач оптимального планирования, в которых переменные могут принимать лишь целочисленные значения. Такие задачи связаны с определением количества единиц неделимой продукции, числа станков при загрузке оборудования, численности работников в структурных подразделениях предприятия и т.д. Достаточно часто возникают задачи с так называемыми булевыми переменными, решениями которых являются суждения типа “да-нет”. Если функция и ограничения в таких задачах линейны, то мы говорим о задаче линейного целочисленного программирования.
Задача линейного целочисленного программирования формулируется следующим образом: найти такое решение (план)
X = (X1, X2, ..., Xn),
при котором линейная функция
принимает максимальное или минимальное значение при ограничениях
, i = 1, 2, ..., m
, j = 1, 2, ... n
- целые числа
1. Метод отсекающих плоскостей
Одним из методов решения задач линейного целочисленного программирования является метод отсекающих плоскостей или метод Гомори. Сущность метода заключается в построении ограничений, отсекающих нецелочисленные решения задачи линейного программирования, но не отсекающих ни одного целочисленного плана.
Рассмотрим алгоритм решения задачи линейного целочисленного программирования этим методом.
1. Решаем задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования.
2. Если среди компонент оптимального решения есть нецелые, то к ограничениям задачи добавляем новое ограничение, обладающее следующими свойствами:
- оно должно быть линейным;
- должно отсекать найденный оптимальный нецелочисленный план;
- не должно отсекать ни одного целочисленного плана.
Для построения ограничения выбираем компоненту оптимального плана с наибольшей дробной частью и по соответствующей этой компоненте k-й строке симплексной таблицы записываем ограничение Гомори.
, ,
где fk = xj - [xj];
fkj = zkj - [zkj];
S* - новая переменная;
[xj], [zkj] -ближайшее целое, не превосходящее xj и zkj соответственно.
3. Составленное ограничение добавляем к имеющимся в симплексной таблице, тем самым получаем расширенную задачу. Чтобы получить опорный план этой задачи, необходимо ввести в базис тот вектор, для которого величина минимальна. И если для этого вектора величина получается по дополнительной строке, то в следующей симплексной таблице будет получен опорный план. Если же величина не соответствует дополнительной строке, то необходимо переходить к М-задаче (вводить искусственную переменную в ограничение Гомори).
4. Решаем при помощи обычных симплексных преобразований полученную задачу. Если решение этой задачи приводит к целочисленному оптимальному плану, то искомая задача решена. Если мы получили нецелочисленное решение, то снова добавляем одно дополнительное ограничение, и процесс вычислений повторяется. Проделав конечное число итераций, либо получаем оптимальный план задачи целочисленного программирования, либо устанавливаем ее неразрешимость.
Замечания:
1. Если дополнительная переменная S* вошла в базис, то после пересчета какого-либо последующего плана соответствующие ей строку и столбец можно удалить (тем самым сокращается размерность задачи).
2. Если для дробного xj обнаружится целочисленность всех коэффициентов соответствующего уравнения (строки), то задача не имеет целочисленного решения.
2. Применение метода отсекающих плоскостей
Задача: Для приобретения нового оборудования предприятие выделяет 19 ден.ед. Оборудование должно быть размещено на площади, не превышающей 16 кв.м. Предприятие может заказать оборудование двух видов: машины типа “А” стоимостью 2 ден.ед., требующие производственную площадь 4 кв.м и обеспечивающие производительность за смену 8 т продукции, и машины типа “В” стоимостью 5 ден.ед., занимающие площадь 1 кв.м и обеспечивающие производительность за смену 6 т продукции.
Требуется составить оптимальный план приобретения оборудования, обеспечивающий максимальную общую производительность.
Решение: Обозначим через x1, x2 количество машин соответственно типа “А” и “В”, через L - их общую производительность. Тогда математическая модель задачи:
max L = 8x1 + 6x2
при ограничениях:
2x1 + 5x2 19
4x1 + x2 16
x1 0, x2 7
x1 , x2 - целые числа
Решаем задачу симплексным методом без учета целочисленности.
Co | Бo | Хo | 8 | 6 | . | . |
x1 | x2 | x3 | x4 | |||
. | x3 | 19 | 2 | 5 | 1 | . |
zj | | . | . | . | . | |
-8 | -6 | . | . | |||
C1 | Б1 | Х1 | 8 | 6 | . | . |
x1 | x2 | x3 | x4 | |||
. | x3 | 11 | . | 9/2 | 1 | -1/2 |
zj | | 80 | 2 | . | 2 | |
. | -4 | . | 2 | |||
C2 | Б2 | Х2 | 8 | 6 | . | . | . |
x1 | x2 | x3 | x4 | S1 | |||
6 | x2 | 22/9 | . | 1 | 2/9 | -1/9 | . |
zj | | 8 | 6 | 8/9 | 14/9 | . | |
. | . | 8/9 | 14/9 | . | |||
| 4/9 | . | . | 2/9 | 8/9 | -1 | |
Получен оптимальный нецелочисленный план Хопт= (61/18;22/9). Lmax = 376/9.
Т.к. у компоненты плана х2 максимальная дробная часть:
max(4/9;7/18) = 4/9, то дополнительное ограничение записываем по первой строке.
22/9 - [22/9] = (2/9 - [2/9])x3 + (-1/9 - [-1/9])x4 - S1, S1 0
22/9 - 2 = (2/9 - 0)x3 + (-1/9 - (-1))x4 - S1, S1 0
4/9 = 2/9x3 + 8/9x4 - S1, S1 0 - первое ограничение Гомори.
Составленное ограничение дописываем к имеющимся в симплексной таблице.
После построения дополнительного ограничения имеем новую задачу линейного программирования, в которой 3 ограничения. Для получения опорного плана этой задачи необходимо найти третий базисный вектор. Для этого определяем:
min = в базис вводим вектор х4.
Рассчитываем величину = . Минимальное значение получено по дополнительной строке, значит, не прибегая к искусственной переменной, получаем опорный план расширенной задачи.
C3 | Б3 | Х3 | 8 | 6 | . | . | . | . |
x1 | x2 | x3 | x4 | S1 | S2 | |||
6 | x2 | 5/2 | . | 1 | 1/4 | . | -1/8 | . |
zj | | 8 | 6 | 1/2 | . | 7/4 | . | |
. | . | 1/2 | . | 7/4 | . | |||
| 1/2 | . | . | 1/4 | . | 7/8 | -1 | |
Найденный план оптимален, но нецелочисленный. Строим новое ограничение Гомори.
Т.к. максимальная дробная часть среди компонент плана равна 1/2, записываем дополнительное ограничение по первой строке (можно и по третьей).
5/2 - [5/2] = (1/4 - [1/4])x3 + (-1/8 - [-1/8])S1 - S2, S2 0
1/2 = 1/4x3 + 7/8S1 - S2, S2 0 - второе ограничение Гомори
Это ограничение добавляем в последнюю симплексную таблицу.
Получили задачу, в которой 4 ограничения, следовательно, в базисе должно быть 4 единичных вектора.
Определяем вектор, вводимый в базис: . Можно ввести либо x3, либо S1. Введем вектор S1.
соответствует дополнительному ограничению.
C4 | Б4 | Х4 | 8 | 6 | . | . | . | . | . |
x1 | x2 | x3 | x4 | S1 | S2 | S3 | |||
6 | x2 | 18/7 | . | 1 | 2/7 | . | . | -1/7 | . |
. | S1 | 4/7 | . | . | 2/7 | . | 1 | -8/7 | . |
zj | | 8 | 6 | . | . | . | 2 | . | |
. | . | . | . | . | 2 | . | |||
| 4/7 | . | . | 2/7 | . | . | 6/7 | -1 | |
Получаем новый оптимальный нецелочисленный план. Учитывая замечание 1, вычеркиваем строку и столбец, соответствующие переменной S1.
В полученном плане максимальную дробную часть имеет компо-нента х2, поэтому записываем дополнительное ограничение по первой строке.
4/7 = 2/7х3 + 6/7S2 - S3, S3 0 - третье ограничение Гомори.
Определяем вектор, вводимый в базис: . Это вектор х3. Минимальное значение = 2, что соответствует дополнительной строке.
После проведения очередных симплексных преобразований получили:
C5 | Б5 | Х5 | 8 | 6 | . | . | . | . | . |
x1 | x2 | x3 | x4 | S2 | S3 | S4 | |||
6 | x2 | 2 | . | 1 | . | . | -1 | 1 | . |
zj | | 8 | 6 | . | . | . | 2 | . | |
. | . | . | . | . | 2 | . | |||
| 4/7 | . | . | . | . | . | 1/4 | -1 | |
План Х5 - оптимальный нецелочисленный.
Дополнительное ограничение запишем по второй строке:
1/2 = 1/4S3 - S4, S4 0 - четвертое ограничение Гомори.
Т.к. базисной компонентой может быть S3, определяем величину . Минимальное значение получилось по 3 строке, а не по строке Гомори, следовательно, переходим к М-задаче: введем дополнительную переменную х5 в ограничение Гомори.
C5 | Б5 | Х5 | 8 | 6 | . | . | . | . | . | -M |
x1 | x2 | x3 | x4 | S2 | S3 | S4 | x5 | |||
6 | x2 | 2 | . | 1 | . | . | -1 | 1 | . | . |
zj | 40- | 8 | 6 | . | . | 2 | -M/4 | M | -M | |
. | . | . | . | 2 | -M/4 | M | . | |||
C6 | Б6 | Х6 | 8 | 6 | . | . | . | . | . | -M |
x1 | x2 | x3 | x4 | S2 | S3 | S4 | x5 | |||
6 | x2 | 2 | . | 1 | . | -1/2 | 1/2 | . | . | . |
. | S3 | . | . | . | . | 1/2 | -3/2 | 1 | . | . |
. | x3 | 2 | . | . | 1 | 7/4 | -9/4 | . | . | . |
zj | 40- | 8 | 6 | . | M/8 | 2-3M/8 | . | M | -M | |
. | . | . | M/8 | 2-3M/8 | . | M | . | |||