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

Сформулируем общую задачу линейного программирования.

Пусть дана система m линейных уравнений и неравенств с n переменными (система ограничений):

(1)

и линейная функция

. (2)

Необходимо найти такое решение системы (1), при котором линейная функция принимает максимальное (минимальное) значение.

В общем случае ЗЛП может иметь бесконечное множество решений. Часто решение , удовлетворяющее ограничениям (1), называют планом. Если все компоненты (3) для , то называют допустимым решением.

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

Модель задачи линейного программирования может быть задана в одной из следующих форм.

Каноническая	Стандартная	Общая
1)Ограничения
Уравнения ,	Неравенства ,	Уравнения и неравенства ,
2)Условия неотрицательности
Все переменные ,	Все переменные ,	Часть переменных , ,
3)Целевая функция
(max или min)

Здесь: – переменные задачи; – коэффициенты при переменных в целевой функции; – коэффициенты при переменных в основных ограничениях задачи; – правые части ограничений.

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

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

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

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

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

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

Пример. Составить математическую модель задачи: На четырех станках (I, II, III, IV) обрабатываются два вида деталей (А и В). Каждая деталь проходит обработку на всех станках. Известны время обработки деталей на каждом станке, время работы станков в течение одного цикла производства и прибыль, полученная от выпуска одной детали. Данные приведены в таблице:

Составить план производства, обеспечивающий наибольшую прибыль при условии, что количество деталей вида В не должно быть меньше количества деталей вида А.

Решение.Пусть – количество деталей вида А и В соответственно, планируемое к выпуску ( , ). Задача аналогична предыдущей, но при составлении модели не следует выпускать из поля зрения фразу: количество деталей вида В не должно быть меньше количества деталей вида А, что математически представимо в виде неравенства: .

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

Любая ЗЛП может быть сведена к канонической, стандартной или общей задаче.