Пример 2.4. Таблица 2.5

Максимизировать 4x₁+3x₂

при ограничениях

x₁ £ 4000;

x₂ £ 6000;

x₁ + x₂ £ 6000;

x₁, x₂ ³ 0.

Расширенная форма задачи имеет такой вид:

максимизировать 4x₁+3x₂

при ограничениях

1x₁ + 0x₂ + 1x₃ + 0x₄ + 0x₅ = 4000;

0x₁ + 1x₂ + 0x₃ + 1x₄ + 0x₅ = 6000;

1x₁ + 2/3x₂ + 0x₃ + 0x₄ + 1x₅ = 6000;

Так как A ₀>0, а векторы A ₃, A ₄, A ₅ образуют единичный базис, то задачу можно решать методом симплекс-таблиц.

Первая итерация. Составляем и заполняем начальную симплекс-таблицу (табл.2.3).

Таблица 2.3.

Ci
	Bx	Ai0	A1	A2	A3	A4	A5
	X3
	X4
	X5			1/3
	D		-4	-3

Поскольку –4<–3<0, то направляющий столбец – первый.

Составив отношение вида ,определим направляющую строку.Для этого находим

.

Итак, направляющая строка -первая, направляющий элемент a ₁₁ = 1.

Выполнив первую итерацию симплекс-метода, получим табл. 2.4.

Таблица 2.4.

Ci
	Bx	ai0	A1	A2	A3	A4	A5
	X1
	X4
	X5			2/3	-1
	D			-3

Вторая итерация. Как видим с табл. 2.4.,направляющий столбец – второй, а направляющая строка – третья, так как

Выполнив очередную итерацию симплекс-метода, получим симплекс-таблицу 2.5.

Таблица 2.5.

Ci
	Bx	ai0	A1	A2	A3	A4	A5
	X1
	X4				3/2		-3/2
	X2				-3/2		3/2
	D				-1/2		9/2

Третья итерация. Так как a ₀₃ = -1/2 <0, то направляющий столбец A ₃, а направляющая строка – вторая, поскольку a ₂₃ = 3/2. Выполнив очередную итерацию с направляющим элементом a ₂₃ = 3/2, получим симплекс-таблицу 2.6.

Таблица 2.6.

Ci
	Bx	ai0	A1	A2	A3	A4	A5
	X1					-2/3
	X3					2/3	-1
	X2
	D					1/3

Поскольку в индексной строке табл. 2.6. все оценки положительны, то найдено оптимальное решение: x _{1 опт} = 2000, x _{2 опт} = 6000, x _{3 опт} = 2000.

Соответствующее значение целевой функции:

max(4 x ₁ + 3 x ₂) =a ₀₀ = 26000 = 4 x _1опт + 3 x _2опт.

Транспортная задача. Различные технико-экономические и экономические задачи менеджмента, от оптимальной загрузки станка и раскройки стального листа или полотна ткани до анализа межотраслевого баланса и оценки темпов роста экономики страны в целом, приводят к необходимости решения тех или иных задач линейного программирования. В книге [1] приведен обширный перечень публикаций, посвященный многочисленным применениям линейного программирования в металлургии, угольной, химической, нефтяной, бумажной и прочих отраслях промышленности, в проблемах транспорта и связи, планирования производства, конструирования и хранения продукции, сельском хозяйстве, в научных исследованиях, в том числе экономических, и даже при регулировании уличного движения.

В качестве очередного примера рассмотрим т.н. транспортную задачу. Имеются склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить товар со складов потребителям. Можно по-разному организовать "прикрепление" потребителей к складам, т.е. установить, с какого склада какому потребителю и сколько вести. Кроме того, известна стоимость доставки единицы товара с определенного склада определенному потребителю. Требуется минимизировать издержки по перевозке.

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

Рассмотрим пример транспортной задачи, исходные данные к которой представлены в табл. 3. В ней, кроме объемов потребностей и величин запасов, приведены стоимости доставки единицы товара со склада i, i = 1,2,3, потребителю j, j = 1,2,3,4. Например, самая дешевая доставка - со склада 2 потребителям 1 и 3, а также со склада 3 потребителю 2. Однако на складе 2 имеется 80 единиц товара, а потребителям 1 и 3 требуется 50+70 =120 единиц, поэтому к ним придется вести товар и с других складов. Обратите внимание, что в табл.3 запасы на складах равны суммарным потребностям. Для примера с доставкой песка кирпичным заводам это вполне естественное ограничение - при невыполнении такого ограничения либо порты будут засыпаны горами песка, либо кирпичные заводы не выполнят заказы.

Таблица 3.

Исходные данные к транспортной задаче.

	Потреби-тель 1	Потреби-тель 2	Потреби-тель 3	Потреби-тель 4	Запасы на складах
Склад 1
Склад 2
Склад 3
Потреб-ности

Надо спланировать перевозки, т.е. выбрать объемы Х_ij поставок товара со склада i потребителю j, где i = 1,2,3; j = 1,2,3,4. Таким образом, всего в задаче имеется 12 переменных. Они удовлетворяют двум группам ограничений. Во-первых, заданы запасы на складах:

X ₁₁ + Х ₁₂ + Х ₁₃ + Х ₁₄ = 60,

X ₂₁ + Х ₂₂ + Х ₂₃ + Х ₂₄ = 80,

X ₃₁ + Х ₃₂ + Х ₃₃ + Х ₃₄ = 60.

Во-вторых, известны потребности клиентов:

X ₁₁ + Х ₂₁ + Х ₃₁ = 50,

X ₁₂ + Х ₂₂ + Х ₃₂ = 40,

X ₁₃ + Х ₂₃ + Х ₃₃ = 70,

X ₁₄ + Х ₂₄ + Х ₃₄ = 40.

Итак, всего 7 ограничений типа равенств. Кроме того, все переменные неотрицательны - еще 12 ограничений.

Целевая функция - издержки по перевозке, которые необходимо минимизировать:

F = 2 X ₁₁ + 5 Х ₁₂ + 4 Х ₁₃ + 5 Х ₁₄ + X ₂₁ + 2 Х ₂₂ + Х ₂₃ + 4 Х ₂₄ +

+ +3 X ₃₁ + Х ₃₂ + 5 Х ₃₃ + 2 Х ₃₄ → min.

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

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