Постановка задачи линейного программирования

Впервые общая постановка задачи линейного программирования и один из методов ее решения были сформулированы советским ученым Л.В. Канторовичем в работе «Математические методы организации и планирования производства». Общая математическая теория линейного программирования была разработана в 1949 г. Дж.Данцигом. Дальнейшее развитие теории линейного программирования и ее практических приложений связано с именем отечественных и зарубежных ученых: В.С. Немчинова, В.В. Новожилова, Д.Б. Юдина, Г. Куна, С. Гасса и других.

Рассмотрим пример постановки задачи линейного программирования. Для передачи сообщений в автоматизированной системе управления организуется комплекс средств связи. При организации комплекса в распоряжении разработчика имеется n типов средств связи (например, КВ и УКВ радиостанции, средства проводной и радиорелейной связи и т.д.). Комплекс предназначен для работы в различных условиях обстановки (в условиях преднамеренных помех, создаваемых противником, в условиях воздействия различных видов оружия и т.п.). Число различных вариантов обстановки равно m.

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

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

Известно, что выполняя задачу управления в i-м варианте обстановки, i =1,..., m, комплекс должен обеспечить передачу сообщений объемом е менее V_i условных единиц. Затраты на эксплуатацию одного комплекта i-го средства связи составляют С, i =1,..., n.

Таблица 3.1

			...	j	...	n
	u11	u12		u1 j		u1 n
	u21	u22		u2 j		u2 n
...	.....	.....	..............	........	.................	.....
i	u i 1	u i 2		u ij		u in
...	.....	.....	..............	........	.................	.....
m	u m 1	u m 2		u mj		u mn

 

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

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

Обозначим через x ₁ - количество комплектов средств связи первого типа, x ₂ - количество комплектов средств связи второго типа и т.д. Тогда в первом варианте обстановки комплекс обеспечит передачу u₁ условных единиц информации:

u1 = u11x1 + u12x2 +... + u1jxj +... + u1nxn

(3.1)

Но по условию задачи управления в первом варианте обстановки необходимо, что u₁ ³ V. Следовательно, с учетом (3.1) можно записать

u11x1 + u12x2 +... + u1jxj +... + u1nxn ³ V1

(3.2)

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

u11x1 + u12x2 +... + u1jxj +... + u1nxn ³ V 1 u21x1 + u22x2 +... + u2jxj +... + u2nxn ³ V 2 .............................................. uj1x1 + uj2x2 +... + uijxj +... + uinxn ³ Vi .............................................. um1x1 + um2x2 +... + umjxj +... + umnxn ³ Vm

(3.3)

Таким образом, система неравенств (3.3) характеризует ограничения на объемы информации, необходимые для выполнения задачи управления в любых условиях обстановки.

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

C ()= С (x 1, x 2,..., xn) = c 1 x 1+ c 2x2+...+ cjxj +...+ cnxn .

(3.4)

По смыслу задачи величины x ₁, x ₂ и т.д. не могут принимать отрицательные значения, т.е. имеют место следующие ограничения:

x 1 ³ 0, x 2 ³ 0,..., xj ³ 0,..., xn ³ 0.

(3.5)

Теперь задачу организации комплекса средств связи можно сформулировать следующим образом: найти такие неотрицательные значения переменных x ₁, x ₂, x ₃,..., x_n, которые удовлетворяют ограничениям (3.3) и обращают в минимум целевую функцию (3.4). Так как ограничения представляют систему неравенств, а целевая функция (3.4) - линейную функцию переменных x ₁, x ₂, x ₃,..., x_n, то согласно приведенной выше классификации задача организации комплекса средств связи для передачи информации в АСУ относится к задачам линейного программирования.