Задачи целочисленного (дискретного) ЛП

Симплекс-таблица оптимального решения исходной задачи

Таблица 5.16

СП БП
		-1/3	5/3	-1/3	2/3
		1/3	4/3	-2/3	1/3
		5/3	23/3	-7/3	5/3

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

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

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

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

.

Согласно таблице соответствия переменных (таблица 9.4):

, , , .

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

В соответствии с теоремой 5.5: .

Таким образом, оптимальное значение целевой функции , которое достигается при .

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

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

,

, , (6.1)

, ,

.

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

Методы целочисленной оптимизации можно разделить на три основные группы: 1) методы отсечения; 2) комбинаторные методы; 3) приближенные методы.

Дата добавления: 2013-12-12