Краткая характеристика методов исследования операций

Линейное программирование

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

Постановка задачи

Предприятию требуется изготовить п видов приборов, для чего необходимо т ресурсов (трудовых, материальных и денежных). От реализации одного вида прибора с номером у (j — 1, 2, …, п) предприятие получает прибыль Су Требуется так спланировать работу, чтобы максимизировать общую прибыль С.

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

а_;,-— число единиц i-ro ресурса, необходимое для изготовления одного i-ro прибора (i = 1, 2, …, m);

b₍ — максимальное число единиц i-ro ресурса;

Xj — планируемое предприятием количество производства j-го прибора.

Общий план производства {х_1; х₂, …, х,} должен выполняться при условии ограниченного количества ресурсов {b_v Ъ_ъ Ь_т}. Следовательно, задача сводится к нахождению х_;— < 0, удовлетворяющих неравенствам:

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

или в сокращенной записи:

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