Пример 2.1.1

Пусть имеется два станка (S₁, S₂), на каждом из которых можно производить два вида продукции (P₁, P₂). Станок S₁ производит единицу продукции P₁ за 1 час, а единицу продукции P₂ - за 2 часа. Станок S₂ затрачивает на единицу продукции P₁ - 2 часа, а на единицу продукции P₂ - 1 час. Станок S₁ может работать в сутки не более 10 ч., а станок S₂ - не более 8 ч. Стоимость единицы продукции P₁ составляет C₁ руб., а стоимость единицы продукции P₂ - C₂ руб.

Требуется определить такие объемы выпуска продукции P₁ и P₂ на станок, чтобы выручка от реализации производственной продукции была максимальной.

Вид ресурса	Число единиц ресурса, затрачиваемое на изготовление единицы продукции	Запас ресурса
P1	P2
S1
S2
Прибыль за единицу продукции	C1	C2	...

Составим математическую модель задачи:

Обозначим через х₁ и х₂ количества продукции P₁ и P₂, которое планируется произвести на каждом отдельном станке. Стоимость произведенной продукции F = c₁ х₁ + c₂ х₂. Мы должны назначить х₁ и х₂ так, чтобы величина F была максимальной. Переменные х₁, х₂ не могут принимать произвольных значений. Их значения ограничены условиями производства, а именно тем, что станки могут работать ограниченное время. На изготовление продукции P₁ станок S₁ тратит 1x₁ часов, а на изготовление продукции P₂ – 2x₂ часов. Поскольку время работы станка S₁ не превосходит 10 ч, то величины х₁ и х₂ должны удовлетворять неравенству x₁ + 2x₂<= 10.

Аналогично можно получить неравенство для станка S₂: 2x₁ + x₂ <= 8.

Кроме того, величины х₁, х₂ не могут быть отрицательными: x₁ >= 0, x₂ >= 0, по смыслу задачи.

Такие задачи кратко записываются следующим образом:

(2.1)

(2.2)

(2.3)

Итак, математическая модель задачи: найти такой план выпуска продукции Х = (х₁, х₂), удовлетворяющий системе (2.1) и условию (2.2), при котором функция (2.3) принимает максимальное значение.

Решения, удовлетворяющие системе ограничений (2.1) и требованием неотрицательности (2.2), являются допустимыми, а решения, удовлетворяющие одновременно и требованием (2.3) оптимальными.

В других ситуациях могут возникать задачи с большим количеством переменных, в систему ограничений которых, кроме неравенств, могут входить и равенства. Поyтому в наиболее общей форме задачу линейного программирования формулируют следующим образом:

	(2.4)
	(2.5)
	(2.6)

Коэффициенты a_i,j, b_i, c_j, j = 1, 2,..., n, i =1, 2,..., m – любые действительные числа (возможно 0).

Итак, решения, удовлетворяющие системе ограничений (2.4) условий задачи и требованиям неотрицательности (2.5), называются допустимыми, а решения, удовлетворяющие одновременно и требованиям минимизации (максимализации) (2.6) целевой функции, - оптимальными.

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

В канонической форме задача является задачей на максимум (минимум) некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х₁, х₂,..., х_n являются неотрицательными:

	(2.7)
	(2.8)
	(2.9)

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

Правило приведения ЗЛП к каноническому виду:

1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением в левую часть некоторой неотрицательной переменной, при чем в неравенства «≤» вводится дополнительная неотрицательная переменная со знаком «+»; в случаи неравенства «≥» - со знаком «-»

(2.10)

Вводим переменную

.

Тогда неравенство (2.10) запишется в виде:

(2.11)

В каждое из неравенств вводится своя “ уравнивающая ” переменная, после чего система ограничений становится системой уравнений.

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

, l - свободный индекс

3. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на (-1)

4. Наконец, если исходная задача была задачей на минимум, то введением новой целевой функции F₁ = -F мы преобразуем нашу задачу на минимум функции F в задачу на максимум функции F₁.

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

В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система ограничений ее состоит из одних линейных неравенств типа «<=» или «>=». Все переменные задачи неотрицательны.

	(2.12)

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

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

Дата добавления: 2014-01-15