Файл: Золотарь, И. А. Экономико-математические методы в дорожном строительстве.pdf

В нем коэффициенты ац и а^, имеющие дробные части, можно разбить на целую часть и дробь следующими способами:

2 ,7 = 2 -ф0,7; 2,7 = 3 - 0 ,3 ;

—5,1 = —5 — 0,1;

—5,1 = —6 + 0 ,9 .

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

дробные части коэффициентов ац.

Дополнительные ограничения Гомори, соответствующие прямой,

Величина Д0 как неотрицательная дробная часть числа всегда меньше единицы, а сумма hfijXj может быть и больше единицы.

Кроме того, как было показано выше, введением дополнитель­ ных переменных вместо неравенства (VI.3) легко получить равен­ ство. Поэтому ограничение Гомори может быть задано и равенст­ вом типа

7 = 1

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

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

100

§13. Применение целочисленного программирования

вэкономическом анализе

Рассмотрим описанную методику решения задач целочисленно­ го программирования на следующем методическом примере.

Специальный цех оснащен четырьмя стендами и может изготав­ ливать два вида мостовых конструкций. Изготовление одного комп­ лекта конструкций первого вида требует трех, а второго вида — одной стендо-смены. Цех обслуживают автомобили общей грузо­ подъемностью 50 т, которые должны • ежедневно за один рейс вывозить продукцию цеха строительным подразделениям, ведущим сборку конструкций.

Комплект конструкций первого вида имеет массу Ю ти позволя­ ет собрать 4 пог. м мостовых конструкций, комплект второго вида — соответственно 20 т и 1 пог. м конструкций. Требуется установить, сколько комплектов конструкций первого и второго вида следует ежедневно изготавливать в цехе для того, чтобы максимизировать протяжение собираемых мостовых конструкций с учетом упомяну­ тых выше ограничений по производственной мощности цеха и транспортным возможностям.

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

равенств, введем дополнительные переменные Si и S2 . Тогда полу­

чим:

Рассматриваемая задача целочисленного программирования очень проста и могла бы быть решена обычным перебором вариан­ тов. Однако она принята для решения по алгоритму Гомори для того, чтобы показать использование последнего на простом методи­ ческом примере.

Найдем вначале оптимальное нецелочисленное решение подоб­ ной задачи. Ранее нами для этого использовался метод потенциа­ лов. Теперь обратимся к основному методу решения задач линейно­ го программирования — симплекс-методу, суть которого сводится

кследующему.

1.Находится базисное решение (соответствует одной из угловых точек области допустимых решений), в котором общее число нену­

10!

левых значений основных и дополнительных переменных типа Si и S2 в зависимостях (VI.9) и (VI.10) равно числу уравнений в форме равенств.

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

Понять это положение нетрудно на основе чисто логических со­ ображений. Если бы в нашем примере было только одно ограниче­ ние, например по использованию стендов (уравнение VI.10), то выгодно было бы производить лишь комплекты первого типа, так как при этом целевая функция (VI.6) была бы максимальна и со­ ставляла 5!/з (при у = 0). В этом случае число ненулевых перемен­ ных (одна переменная х) равнялось бы числу ограничений. Если появляется второе ограничение, например по транспортным воз­ можностям, как в нашем примере, то обычно бывает выгодным производить и второй вид продукции в целях использования этого производственного ресурса.

В нашей задаче четыре переменных: х, у, Si и S 2 и два уравне­ ния в форме равенств (VI.9) и (VI.10). Следовательно, базисное решение должно содержать два ненулевых значения переменных. Если начало координат является одной из вершин области допусти­ мых решений, то проще всего за базисное решение принять точку О начала координат. В этой точке будем иметь два нулевых значения

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

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

102

В правую часть равенства (VI.11) введен ноль как коэффициент при дополнительных переменных Si и S 2 в целевой функции. В та­ кой записи все переменные с ненулевыми значениями (Si и S%для базисного решения) находятся в левой части уравнений (VI. 12) и (VI.13), а нулевые переменные — в правой части равенств (VI.11) —

(VI.13).

Составим таблицу-матрицу коэффициентов выражений для L,

Si и S2:

В матрице (VI. 14) для первого базисного решения переменные с нулевыми значениями помещены сверху, а ненулевые — слева. Этот порядок записи будет сохраняться и в дальнейшем.

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

Допустим, что первая строка матрицы очередного базисного ре­ шения имела бы вид:

1 1 * 4 У'

иI 5 1 - 2 I - 1

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

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

103

ца на эти коэффициенты, получим следующие абсолютные значения

частного: — 1 — 5 и Следовательно,

за ведущий элемент должен быть принят коэффициент — 3 во вто­

Полученная матрица (VI.18) удовлетворяет приведенному выше признаку оптимальности. Поэтому найдем нецелочисленное реше­ ние нашей задачи:

S , = 3 - j - , * = l - i - ; S 2 = y = 0;

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

104