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

Задачей линейного программирования (ЛП) называется задача минимизации или максимизации линейного функционала при линейных ограничениях. В литературе принят ряд специальных форм записи задачи ЛП:

1. Форма общей задачи ЛП (задача ЛП со смешанными ограничениями) - найти максимум по переменным линейного функционала
c₁x₁ + c₂x₂ → max

(0.10)

при линейных ограничениях
A₁₁x₁ + A₁₂x₂ ≤ b₁,

(0.11)

A₂₁x₁ + A₂₂x₂ = b₂,

(0.12)

x₁ ≥ 0.

(0.13)

Здесь , матрицы A₁₁, A₁₂, A₂₁, A₂₂ имеют соответственно размеры
(m₁ × n₁), (m₁ × n₂), (m₂ × n₁), (m₂ × n₂).

2. Форма основной задачи ЛП

(c, x) → max

при линейных ограничениях

Ax ≤ b

Здесь - матрица размера (m × n).

3. Стандартная форма записи задачи ЛП

(c, x) → max

при линейных ограничениях Ax ≤ b, x ≥ 0

Здесь - матрица размера (m × n).

4. Каноническая форма записи задачи ЛП

(c, x) → max

при линейных ограничениях

Ax = b

x ≥ 0

Формально говоря, задачи 2-4 являются частными случаями общей задачи 1. Однако в свою очередь общая задача может быть представлена в форме любой из трех остальных. Так задача 1 принимает основную форму, если заменить в ней систему ограничений-равенств на эквивалентную систему ограничений-неравенств

A₂₁x₁ + A₂₂x₂ ≤ b₂

-A₂₁x₁ - A₂₂x₂ ≤ -b₂

Если сделать замену переменных
x₂ = y₂ - z₂, y₂ &ge 0, z₂ ≥ 0,
то задача 1 примет стандартную форму. Если же ограничения неравенства в задаче 1 записать в виде

A₁₁x₁ + A₁₂x₂ + u = b₁

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

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

Пример 1. Для изготовления трех видов изделий А, В и С используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия для каждого из типов оборудования указаны в табл. 1. В ней же указан общий фонд рабочего времени каждого из типов используемого оборудования, а также прибыль от реализации одного изделия каждого вида.

Таблица 1

Тип оборудования	Затраты времени (станко-часы) на обработку одного изделия каждого вида	Общий фонд рабочего времени оборудования (часы)
	А	В	С
Фрезерное
Токарное
Сварочное
Шлифовальное
Прибыль (руб.)

Требуется определить, сколько изделий и какого вида следует изготовить предприятию, чтобы прибыль от их реализации была максимальной. Составить математическую модель задачи.

Решение. Предположим, что будет изготовлено x₁ единиц изделий вида А, единиц – вида В и единиц – вида С. Тогда для производства такого количества изделий потребуется затратить станко-часов фрезерного оборудования.

Так как общий фонд рабочего времени станков данного типа не может превышать 120, то должно выполняться неравенство

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

При этом так как количество изготовляемых изделий не может быть отрицательным, то

(1)

Далее, если будет изготовлено x₁ единиц изделий вида А, единиц изделий вида В и единиц изделий вида С, то прибыль от их реализации составит

Таким образом, приходим к следующей математической задаче: дана система

(2)

четырех линейных неравенств с тремя неизвестными и линейная функция относительно этих же переменных

. (3)

Требуется среди всех неотрицательных решений системы неравенств (2) найти такое, при котором функция (3) принимает максимальное значение. Как это сделать, будет показано в дальнейшем.

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

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