Производственный менеджмент (лекции). Производственный менеджмент
 Скачать 6.27 Mb.
|
Задачи целочисленного программированияЗначительная часть задач производственного менеджмента, относящихся к задачам линейного программирования, требует целочисленного решения. К ним относятся задачи, у которых переменные величины означают количество единиц неделимой продукции. Целочисленное программирование ориентировано на решение задач, в которых все или некоторые переменные должны принимать только целые значения. Задача называется полностью целочисленной, если условие целочисленности наложено на все ее переменные; когда это условие относится лишь к некоторым переменным, задача называется частично целочисленной. Математическая модель линейной целочисленной задачи может быть записана следующим образом: F(  ) =  (1) , bi  0, i = 1, ..., m, (2)xj 0, j = 1, ..., n, xj – целые. (3)Существует эвристический подход к решению задач целочисленного программирования (ЗЦП), основанный на решении ЗЦП как задачи ЛП. Использование процедур округления нецелочисленного оптимального решения задачи ЛП дает возможность получать приближенное оптимальное целочисленное решение. Например, если в оптимальном решении двумерной задачи ЛП значения переменных х1 и х2 оказались равными 3,5 и 4,4 соответственно, то в качестве кандидатов на роль приближенного целочисленного оптимального решения необходимо рассмотреть точки (3;4), (4;4), (4;5), (3;5) полученные в результате округления. Заметим однако, что истинное оптимальное целочисленное решение может не совпадать ни с одним из четырех, указанных выше. ПРИМЕР F( ) = x1 – 3x2 + 3х3  при ограничениях 2x1 + x2 - х3 4 4x1 - 3x2 2 -3x1 + 2x2 + х3 3 x1, х2, х3 0, целые. Игнорируя условия целочисленности получим  . Никакое округление компонент этого плана не дает допустимого решения, так как искомое целочисленное решение  . Таким образом, для решения целочисленных задач необходимы специальные методы.Точные методы решения задач целочисленного программирования можно классифицировать как методы отсечений и комбинаторные методы. Название “методы отсечений” связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают некоторые области многогранника допустимых решений, в которых отсутствуют точки с целочисленными координатами. Метод отсекающих плоскостей, разработанный Р. Гомори, используется при решении полностью целочисленных задач. В основе комбинаторных методов лежит идея перебора всех допустимых целочисленных решений. Разумеется, на первый план здесь выдвигается проблема разработки процедур, позволяющих непосредственно рассматривать лишь относительно небольшую часть указанных решений, а остальные допустимые решения учитывать некоторым косвенным образом. Наиболее известным комбинаторным методом является метод ветвей и границ. Дробный алгоритм решения полностью целочисленных задачНеобходимым условием применения данного алгоритма является целочисленность всех коэффициентов и правых частей ограничений исходной задачи. Например, ограничение х1 + (1/3) х2 13/2 записывается в виде 6х1 + 2х2 39, в котором дроби отсутствуют. На первом шаге решается задача с ослабленными ограничениями, которая возникает в результате исключения требования целочисленности переменных. Если полученное оптимальное решение оказывается целочисленным, то оно является также решением исходной задачи. В противном случае следует ввести дополнительные ограничения, порождающие (вместе с исходными ограничениями) новую задачу линейного программирования, решение которой оказывается целочисленным и совпадает с оптимальным решением исходной целочисленной задачи. Пусть последняя симплексная таблица задачи с ослабленными ограничениями имеет следующий вид:
Через xi (i = 1, ..., m) обозначены базисные переменные, а через j (j = 1, ..., n) – небазисные переменные. Рассмотрим i-ю строку симплексной таблицы, которой соответствует нецелое значение базисной переменной xi, и выразим xi через небазисные переменные:  , i – нецелое.Каждую строку симплексной таблицы, порождающую аналогичное равенство, будем называть производящей строкой. Пусть i = [i] + fi, ij = [ij] + fij. Отсюда следует , что 0 < fi < 1, 0 fij < 1. ПРИМЕР
|
