Реализация целочисленных моделей принятия решений

Реализация целочисленных моделей принятия решений

Содержание

Введение

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 - целые числа

Решаем задачу симплексным методом без учета целочисленности.