Дробный алгоритм решения полностью целочисленных задач

Необходимым условием применения данного алгоритма является целочисленность всех коэффициентов и правых частей ограничений исходной задачи. Например, ограничение х1 + (1/3) ×х2 £ 13/2 записывается в виде 6×х1 + 2×х2 £ 39, в котором дроби отсутствуют.

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

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

Базисные переменные		...		...			...		...		Решение
		...		...
...	...	...	...	...	...	...	...	...	...	...	...
		...		...			...		...
...	...	...	...	...	...	...	...	...	...	...	...
		...		...			...		...
		...		...			...		...

Через x_i (i = 1, ..., m) обозначены базисные переменные, а через w_j (j = 1, ..., n) – небазисные переменные.

Рассмотрим i-ю строку симплексной таблицы, которой соответствует нецелое значение базисной переменной x_i, и выразим x_i через небазисные переменные:

, b_i – нецелое.

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

Пусть b_i = [b_i] + f_i, a_ij = [a_ij] + f_ij.

Отсюда следует , что

0 < f_i < 1, 0 £ f_ij < 1.

ПРИМЕР

а	[а]
3/2		1/2
-7/3	-3	2/3
-1	-1

Теперь наше уравнение принимает следующий вид:

Поскольку все переменные x_i и w_i принимают целые значения, правая часть уравнения должна быть целочисленной, откуда следует, что левая часть уравнения также должна принимать целые значения. Далее, так как f_ij ³ 0 и w_i ³ 0 для всех i и j, то

.

Следовательно, выполняется неравенство .

Это означает, что

, поскольку f_i < 1.

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

.

Последнее ограничение перепишем в виде равенства

, где S_i – неотрицательная дополнительная переменная, которая по определению должна принимать целые значения. Такое ограничение-равенство определяет отсечение Гомори для полностью целочисленной задачи.

Из симплексной таблицы следует, что w_i = 0, и, таким образом, S_i = – f_i, т. е. данная компонента решения не является допустимой. Это означает, что полученное ранее решение не удовлетворяет новому ограничению. В такой ситуации следует использовать двойственный симплекс-метод, реализация которого обеспечивает отсечение некоторой области многогранника решений, не содержащей точек с целочисленными координатами.

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

Получим новую таблицу:

Базисные переменные

...

...

...

...

Решение

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

-

...

-

...

-

-

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

Название дробный алгоритм связано с тем обстоятельством, что все ненулевые коэффициенты введенного отсечения меньше единицы. Общее число ограничений порожденной задачи не может превышать (m + n).

Процесс определения оптимального плана методом Гомори включает следующие этапы:

1. Используя симплекс-метод находят решение задачи без учета требований целочисленности переменных.

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

3. Используя двойственный симплекс-метод, находят решение задачи, получающейся в результате присоединения дополнительного ограничения.

4. В случае необходимости составляют еще одно дополнительное ограничение и продолжают процесс.

ПРИМЕР

F( ) = 7×x1 + 9×x2

при ограничениях

-x1 + 3×x2 £ 6 -x1 + 3× x2 + x3 = 6

7×x1 + x2 £ 35 7×x1 + x2 + x4 = 35

x1, х2 ³ 0, целые; x1, ..., x4 ³ 0, целые.

Таблица 1

						=
		-1
		-7	-9
		-1/3 22/3		1/3 -1/3
		-10
				7/22 -1/22	1/22 3/22	7/2 9/2
				28/11	15/11

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

x2 + 7/22×x3 + 1/22×x4 = 7/2.

Следовательно, уравнение отсечения Гомори имеет вид

- 7/22×x3 - 1/22×x4 + = -1/2

В результате получаем новую таблицу:

Таблица 2

							=
				7/22 -1/22 -7/22	1/22 3/22 -1/22		7/2 9/2 -1/2
				28/11	15/11
					1/7 1/7	-1/7 -22/7	32/7 11/7

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

- 1/7×x4 - 6/7× + = -4/7

Таблица 3

								=
					1/7 1/7 -1/7	-1/7 -22/7 -6/7		32/7 11/7 -4/7
						-1 -4	-7

В результате получили оптимальное целочисленное решение исходной задачи:

x1 = 4, x2 = 3, F( ) = 55.

Дадим геометрическую интерпретацию задачи. На рис. 1 показано, что введение двух ограничений позволяет получить новую экстремальную точку с координатами (4;3), в которой достигается оптимум исходной целочисленной задачи.

1 ОТСЕЧЕНИЕ: - 7/22×x3 - 1/22×x4 + S₁ = -1/2 или

- 7/22×x3 - 1/22×x4 £ -1/2

Тогда из таблицы 1 получим

-7/22×(х1 - 3×х2 + 6) - 1/22× (-7×x1 - х2 + 35) £ -1/2 Þ

7×(х1 - 3×х2 + 6) + (-7×x1 - х2 + 35) ³ 11 Þ х2 £ 3.

2 ОТСЕЧЕНИЕ: - 1/7×x4 - 6/7×S₁ + S₂ = -4/7 или

- 1/7×x4 - 6/7×S₁ + S₂ £ -4/7

Теперь из таблиц 1 и 2 получим

- 1/7×(-7×x1 - х2 + 35) - 6/7×(7/22×x3 + 1/22×x4 - 1/2) £ -4/7 Þ

-1/7×(-7×x1 - х2 + 35) - 6/7×[7/22×(х1 - 3×х2 + 6) + 1/22×(-7×x1 - х2 + 35) - 1/2 ] £ -4/7 Þ х1 + х2 £ 7.

Рис. 1. Графическая интерпретация задачи

[1] Современное управление. Энциклопедический справочник. Том второй.:"Издацентр",1997, с разд. 8.

[2] Дж. Риггс Производственные системы: планирование, анализ, контроль., пер. с англ. Общая ред. А.И. Анчишкина.- М.: Прогресс, 1972., с.9.

[3] Мескон М.Х., Альберт М., Хедоури Ф. Основы менеджмента: Пер. с англ.-М.:"Дело", 1992, с. 596..

[4] См., например, Ансофф И. Стратегическое управление.№ пер. с англ.- М.: Экономика,1989; Томпсон А..А., Стрикленд А.Дж. Стратегический менеджмент. Искусство разработки и реализации стратегии: Учебник для вузов/ пер. с англ. Под ред. Л.Г. Зайцева, М.И. Соколовой.- М.: Банки и биржи, ЮНИТИ,1998.

См., например,[5] Мескон М.Х., Альберт М., Хедоури Ф. Основы менеджмента.- М.:"Дело", 1993.; Герчикова И.Н. Менеджмент.- М.: ЮНИТИ, 1995.

[6] См., например, Лифшиц А.Л., Мальц Э.А. Статистическое моделирование систем массового обслуживания, "Советское радио", 1978.

[7] Смирнов Е.Л. Справочное пособие по НОТ.- М.: Экономика, 1986, с. 177.

[8] См. подробнее Зубов В.М. Как измеряется производительность труда в США.- М.: Финансы и статистика, 1990,

[9] Синк Д.С. Управление производительностью: планирование,измерение и оценка, контроль и повышение; Пер. с англ.- М. Прогресс, 1989.

[10] Англо-русский экономический словарь/ под ред. А.В.Аникина.-М.: Русский язык, 1977,с.365.

[11] В.К.Мюллер Англо-русский словарь.-М.: Русский язык, с.441.

[12] William J. Stevenson Production/Operations Management.-4-th ed., IRWIN, INC., 1993, p.725.

[13] Логистика: Учеб.пособие / под ред. Б.А.Аникина.-М.:ИНФРА-М,1997, с.7.

[14] Там же, с.10.

[15] Там же, с.14.

[16] В экономической литературе выделяют и несколько иные этапы развития логистики: например, дологистический период (до 50-х годов); период классической логистики (60-е годы); период неологистики (с начала 80-х годов). См., например, Логистика /под ред. Б.А.Аникина.-М.: ИНФРА-М,1997,с.31-37.

[17] Производство на заказ может применяться и в условиях дефицита, когда производится сложная и дорогая продукция. В этих условиях целесообразно подождать, пока потребитель точно не изложит свои требования. Например, строить суда или электротурбины на склад не принято. Рельсы же или арматурную сталь производят на склад. То же самое характерно и для продукции, которая имеет множество модификаций (См.: Янош Корнаи Дефицит.-М.: Наука,1990, с.137).

[18] MRP – material requirement planning

[19] Впервые эта система была опробована в 1972 году на автомобильной фирме “Тайота”. Автор системы Т.Оно использовал принцип “последнего звена”, применяемый в супермаркетах, для промышленного производства. В супермаркетах покупатель является информационным источником необходимого количества, ассортимента и т.д. Импульсом для функционирования всей системы служит спрос, определяемый покупателем.

[20] В литературе есть указание, что фонетически более точным является термин “камбан”. См.,например, Статистические методы повышения качества /Под ред. Хитоси Кумэ.- М.: Финансы и статистика, 1990, с. 274.

[21] Янош Корнаи Дефицит.-М.: Наука, 1990, с.139.

[22] Cм. Рис.2.

[23] Подробнее об этом см.: Неруш Ю.М.Коммерческая логистика /учебник.- М.: ЮНИТИ, 1997, с.141.

[24] Подробнее об этом см.: Логистика:Учеб.пособие / Под ред. Б.А.Аникина.-М.:ИНФРА-М,1997,с.237-246.

[25] Неруш Ю.М. Коммерческая логистика/ учебник, М.: ЮНИТИ, 1997, с.143.

[26]Подробнее об этом: Статистическое моделирование и прогнозирование /под ред. А.Г.Гранберга.-М.: Финансы и статистика, 1990, с.184-189.

[27] Промышленная логистика / пер. А.В Проскуряков, Н.К.Моисеева, Н.Т.Севруков, А.Н.Пилищенко.- Санкт-Петербург, Политехника, 1994, с.78-83.

[28] Метод Дельфы получил название от города Дельфы, ставшего известным из-за прорицателей – оракулов, живших в нем и предсказывающих будущее. Пророчества обнародовались после тщательного обсуждения на совете дельфийских мудрецов.

[29] Подробнее о UPC см.: William J. Stevenson Production/Operfnions Management.-4^th ed.-RICHARD D. IRWIN, INC., 1993, р.589.

[30] Гаджинский А.М. Основы логистики.-М.:ИВЦ “Маркетинг”, 1996,с.105.

[31] Неруш Ю.М. Коммерческая логистика/ учебник.-М.: ЮНИТИ, 1997, с.165

[32] Логистика /учебное пособие под ред. Б.А.Аникина.-М.: ИНФРА-М. 1997, с. 254.

[33] Гаджинский А.М. Основы логистики (2-е издание).-М.: ИВЦ “Маркетинг”, 1996, с.82.

[34] Там же, с.86.

[35] В настоящее время для внебюджетных предприятий и организаций норматив разрядов рабочих и работ директивно не устанавливается. Предприятие, тем не менее, с учетом имеющегося опыта нормирования, особенностей технологии производства и других факторов, а также в связи с необходимостью оценки затрат труда, его оплаты и т.д. разрабатывает показатели, позволяющие определить и оценить сложность работ самостоятельно. На наш взгляд, применявшаяся ранее 6-ти (в отдельных отраслях 8-ми) разрядная сетка может быть признана наиболее приемлемой, так как не сужает и не размывает диапазон сложности работ по числу разрядов и позволяет соблюдать принцип преемственности экономической информации.

1 На практике перечень дополнительных затрат может быть значительно шире, что увеличивает фактическую себестоимость продукции.

[36] См., например, Фридман П."Контроль затрат и финансовых результатов при анализе качества продукции"– М.: Аудит, ЮНИТИ, 1994 [15]"… возмещенные затраты времени (количество изготовленных единиц изделия, умноженное на нормо-часы)"– с.39. В соответствии с принятой в отечественной экономике терминологией этот показатель носит название"фактического объема производства в нормо-часах».

[37] Значения в рамке приведены с учетом разложения фактора"замена"на составляющие его факторы –"цены"и"нормы».

[38] См."Статистический словарь»– М.: Финанстатинформ, 1996, стр. 268.

[ИС1] В практике менеджмента распространены три основные формы организационной структуры: функциональная структура; структура по видам продукции; структура, ориентированная на потребителя.