Симплекс-метод решения задач

На лекции мы разобрали симплекс-метод решения задач линейного программирования. Теперь рассмотрим конкретный пример.

Пример 3. Фирма рекламирует свою продукцию с использованием четырех средств: телевидения, радио, газет и афиш. Из различных рекламных экспериментов, проводимых в прошлом, известно, что эти средства приводят к увеличению прибыли, соответственно, на 10, 3, 7 и 4денежные единицы в расчете на 1 денежную единицу, затраченную на рекламу.

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

а) полный бюджет не должен превосходить 500 000 денежных единиц;

 б) следует расходовать не более 40% бюджета на телевидение и не более 20% бюджета на афиши,

в) вследствие привлекательности для подростков радио на него следует расходовать, по крайней мере, половину того, что планируется на телевидение.

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

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

F=10x₁+3x₂+7x₃+4x₄,

а система ограничений:

x₁+x₂+x₃+x₄≤ 500;

x₁ ≤0,4(x₁+x₂+x₃+x₄);

x₄≤0,2(x₁+x₂+x₃+x₄);

x₂≥0,5x_1.

 

(единица измерения — тыс. руб.).

Запишем ее в таком виде:

x₁+x₂+x₃+x₄ ≤ 500;

0,6x₁ –0,4x₂ – 0,4x₃ – 0,4x₄ ≤ 0;

-0,2x₁ – 0,2x₂ – 0,2x₃+0,8x₄ ≤ 0;

0,5x₁ –x₂≤0,

 

а затем упростим:

x₁+x₂+x₃+x₄ ≤ 500;

3x₁ – 2x₂ – 2x₃ –2x₄ ≤ 0;

-x₁ –x₂ –x₃+4x₄ ≤ 0;

x₁– 2x₂≤0.

 

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

x₁+x₂+x₃+x₄ +x₅ = 500;

3x₁ – 2x₂ – 2x₃ – 2x₄ +x₆ = 0;

-x₁ –x₂ –x₃+4x₄ +x₇ = 0;

x₁– 2x₂+x₈ =0.

Максимизируем целевую функцию на множестве неотрицательных решений этой системы ограничений. Система является канонической, базисные неизвестные — x₅, x₆, x₇, x₈.

Построим симплексную таблицу

Цены	Базис	Свободные коэффициенты	Цены
			x1	x2	x3	x4	x5	x6	x7	x8
					1
				-2	-2	-2
			-1	-1	-1
				-2
			-10	-3	-7	-4
			1	-2
			-3
				-2
										-1
				10						-5
				-2
							0,2	0,1		-0,5
							-0,4	-0,2
							0,4	-0,3		0,5
						0,6
							7,4	0,2

Максимальное значение целевой функции равно 3700 000; достигается оно на плане (200000, 100000, 200000, 0). Это означает, что для достижения максимальной прибыли от рекламы (3700000 денежных единиц) следует вложить в рекламу на телевидении 200000, на радио — 100000, в газетах — 200000 денежных единиц, а использовать для этого афиши вовсе не следует.

Упражнения

1. Максимизируйте функцию f = x+2y на множестве

 неотрицательных решений системы

x+3y≤9;

2x+3y≤12;

x≤4.

 

2. Минимизируйте функцию f = 7x+y на множестве неотрицательных решений системы

4x+y≥6;

х +y≥3;

у ≥1.

 

3. Пусть симплексная таблица имеет вид:

Базис	Свободный коэффициент	х1	х2	х3
х1			-3
х3

Найдите максимальное значение целевой функции.

4. Пусть симплексная таблица имеет вид:

	Свободный коэффициент	х1	х2	х3
х1			-3
х3
			-3

Найдите минимальное значение целевой функции.

5. При решении задачи максимизации получена таблица:

Базис	Свободные коэффициенты	x1	x2	x3
x1
x3
			-2

Если она является окончательной, выпишите оптимальный план; если нет, постройте следующую таблицу и выпишите оптимальный план, если она окажется окончательной.

6. При решении задачи минимизации получена таблица:

Базис	Свободные коэффициенты	x1	x2	x3	x4
x1
x2
x3

Если она является окончательной, выпишите оптимальный план; если нет, постройте следующую таблицу и выпишите оптимальный план, если она окажется окончательной.

7. На заводе производят фруктовые напитки двух сортов. Для производства первого смешивают яблочный сок с клюквенным в пропорции 1:3, а для производства второго смешивают яблочный и клюквенный соки в равных пропорциях. Известно, что производство 1л первого напитка приносит 3руб. прибыли, а второго — 4руб. Завод может расходовать ежедневно не более 2000 л клюквенного сока и 1000 л — яблочного. Определите, как следует организовать производство, чтобы доход был наибольшим.

8.  Звероферма выращивает черно-бурых лисиц и песцов. На звероферме имеются 10000 клеток. В одной клетке могут жить либо две лисы, либо один песец. По плану, на ферме должно быть не менее 3000 лис и не менее 6 000 песцов. В сутки каждой лисе необходимо выдавать 4 ед. корма, а каждому песцу — 5 ед. Ферма ежедневно может иметь не более 200 000 ед. корма. От реализации одной шкурки лисицы ферма получает 10 денежных единиц прибыли, а шкурки песца — 5 ед.

Какое количество лисиц и песцов следует держать на ферме, чтобы получать максимальную прибыль?