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

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

Слово «программирование» введено в связи с тем, что неизвестные переменные, которые находятся в процессе решения задачи, обычно определяют программу или план работы некоторого экономического субъекта.

Математическая модель задачи линейного программирования включает следующее:

· Совокупность переменных , каждый набор которых называется планом ЗЛП. Очевидно, что план ЗЛП можно рассматривать как n -мерный вектор.

· Целевую функцию , которая позволяем выбирать оптимальный, т.е. наилучший план из множества возможных планов ЗЛП.

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

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

Пример 1. Составить экономико-математическую модель задачи:

Для выпуска изделий двух типов А и В на заводе используют сырье четырех видов (I, II, III, IV). Для изготовления изделия А необходимо: 2 ед. сырья первого вида, 1 ед. второго вида, 2 ед. третьего вида и 1 ед. четвертого вида. Для изготовления изделия В требуется: 3 ед. сырья первого вида, 1 ед. второго вида, 1 ед. третьего вида. Запасы сырья составляют: I вида – 21 ед., II вида – 8 ед., III вида – 12 ед., IV вида – 5 ед. Выпуск одного изделия типа А приносит 3 УДЕ прибыли, а одного изделия типа В – 2 УДЕ. Составить план производства, обеспечивающий наибольшую прибыль.

►Достаточно часто при составлении математической модели экономической задачи бывает удобно данные условия представить в виде таблицы:

Пусть – количество изделий типа А и В соответственно, планируемое к выпуску (, ).

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

Составим систему ограничений, используя заданную ограниченность сырья. При планируемых объемах производства расходуется сырья I вида: (ед.), что не должно превышать запас 21 ед. Таким образом, получим неравенство: . Составляя неравенства по каждому виду сырья, получим систему:

Итак, математическая модель задачи линейного программирования имеет вид:

◄

Определение 1. Решения системы ограничений образуют область допустимых решений (планов) ЗЛП.

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