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

Задачи линейного программирования рассмотрены в литературе [1-4].

В задаче линейного программирования  требуется найти экстремум (максимум или минимум) линейной целевой функции (ЦФ) f(X*):

max(min) f(X*)=c1x1+c2x2+…+cnxn,                                 (1)

При  ограничениях:

                                                               (3)

где – заданные постоянные величины.

 Так записывается общая задача линейного программирования в развернутой форме; знак {≤, =, ≥} означает, что в конкретной ЗЛП возможно ограничение типа равенства или неравенства (в ту или иную сторону).

Вектор X* = (x1, х2, ..., хп), удовлетворяющий системе ограничений (2), (3), называется допустимым решением, или планом ЗЛП, т.е. ограничения (2), (3) определяют область  допустимых решений или планов задачи линейного программирования (область определения ЗЛП).

Рассмотрим методику решения задачи линейного программирования на примере.

 Пример.1. Пусть требуется определить, в каком количестве надо выпускать продукции четырех типов Прод.1, Прод.2, Прод.3, Прод.4, для изготовления которой требуются ресурсы трех видов: трудовые, сырье, финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода и прибыль, получаемая от реализации каждого типа продукции приведена в табл.1.

Таблица 1. Исходные данные