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

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

Пусть предприятие расолагает М видами различных ресурсов, обозначенных R1...Rn, каждый ресурс ограничен количеством в (R1 – b1, Rn – bn), стоимость единицы ресурса - ai руб. Предприятие, используя эти ресурсы может производить N видов товаров ( Т1...Tn) , для производства товара Tj необходимо затратить aij количество ресурса Ri. Известно, что каждая единица товара Tj стоит Сj руб, а рынок не может поглотить более Кj единиц товара Tj. Требуется определить такое производство товара, которое бы обеспечило MAX прибыль.

Решение: вводим переменную Xj, обозначающую количество товара Tj.

Ограничения: Хj £ Кj - по количеству товаров, поглощаемых рынком.

Хj ³ 0 ;

- по количеству ресурсов,

Целевая функция:

- (сумма всех прибылей с товаров Tj, умноженная на количество товаров), равная MAX – является целевой функцией.