4.2. Алгоритм метода Гомори. Геометрическая иллюстрация метода Гомори

Метод Гомори основан на применении симплекс-метода и метода отсечения. Идея его достаточно проста и заключается в следующем.

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

Приведем алгоритм метода Гомори.

1. Симплекс-методом находят оптимальный план задачи (4.1)–(4.3) (таблица 4.1). Если в таблице 4.1 все свободные члены целые, то план является оптимальным и для исходной задачи (4.1)–(4.4). Если задача (4.1)–(4.3) неразрешима, то и задача (4.1)–(4.4) неразрешима. Если среди свободных членов есть нецелые, о переходят к пункту 2 алгоритма.

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

Таблица 4.1.

3. Неравенство представленное выше введением дополнительной неотрицательной целочисленной переменной преобразовывают в эквивалентное уравнение

4. Расширяют таблицу 4.1 за счет включения в нее дополнительной строки для составленного уравнения (4.6) (таблица 4.2), получая тем самым симплексную таблицу для расширенной задачи.

5. Составленную расширенную задачу вновь решают симплекс-методом. Если оптимальный план будет целочисленным, то он и станет решением исходной задачи (4.1)–(4.4). В противном случае возвращаются к пункту 2 алгоритма.

Таблица 4.2.

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

Геометрическая иллюстрация метода Гомори осуществляется с помощью графического поля, на которое нанесена целочисленная решетка (рисунок 4.2).

Рисунок 4.2. – Геометрическая иллюстрация метода Гомори

На рисунке 9.2 максимальное значение функции в области допустимых решений (четырехугольник ABCD) достигается в нецелочисленной точке С. После построения первого дополнительного ограничения, прямая линия которого на рисунок 4.2 проходит через точки Е и F, максимальное значение функции в новой области допустимых решений (многоугольник ABEFD) достигается в нецелочисленной точке F. При включении в систему ограничений второго дополнительного ограничения, прямая которого проходит через точки E и K, максимум функции достигается в нецелочисленной точке Е в области допустимых решений, представленной многоугольником ABEKD. А после включения в систему ограничений третьего дополнительного ограничения, прямая которого проходит через точки L и М, найдено максимальное значение функции в целочисленной точке N с координатами (2;4) многоугольника ABLNKD.

Нетрудно увидеть, что дополнительные ограничения отсекали только нецелочисленные точки, и не была отсечена ни одна целочисленная точка.

В качестве преимуществ метода Гомори можно рассматривать его эффективность и точность, т.к. в результате решения получается наиболее оптимальное значение задачи. К недостаткам метода можно отнести:

– трудоемкость (в некоторых задачах для расчета симплексных таблиц необходимо производить множество расчетов);

– громоздкость (решение достаточно объемно, т.к. приходится искать оптимальные значения сначала симплекс-методом, а затем методом отсечения, который также может применяться несколько раз);

– малая применимость (метод применяется для задач с небольшим количеством переменных, т.к. при увеличении их числа происходит значительное увеличение трудоемкости вычислений).

Тема № 5. Модель межотраслевого баланса в системе национальных счетов

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

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

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

– в предпоследнем столбце таблицы содержится информация о той

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

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

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

Xi – валовой выпуск в i-й отрасли;

Yi – объем конечного потребления в i-й отрасли;

Пi – объем продукции i-й отрасли, использованной в j-й отрасли.

Базисным в теории межотраслевого баланса является следующее предположение: величина

равная объему продукции i-й отрасли, который используется в j-й отрасли для производства единицы продукции, не зависит от объема производства Xi, а обусловлен технологическими особенностями. Другими словами, промежуточное потребление в j-й отрасли линейно зависит

от валового выпуска Xi в этой отрасли:

При этом матрица A называется матрицей прямых производственных затрат.

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

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

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

(5.1)

Матрица B называется матрицей полных затрат. Ее элементы Bij показывают, какое потребуется изменение объема валового выпуска продукции в i-й отрасли, обеспечения увеличения конечного спроса j-й отрасли на единицу.

Матрицей полных производственных затрат называют матрицу Из (7.1) получаем

Таким образом, элементы матрицы Bполн показывают, какие необходимы затраты продукции i-й отрасли для обеспечения единичного конечного спроса в j-й отрасли.

Из тождества

получаем равенство

откуда

(5.2)

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

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

Тема № 6. Экономико-математические модели управления запасами