НЭ=СЭ – (А*В)/РЭ (6)

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

Пример №2.

На приобретение оборудования для производственного участка выделено 20тыс. руб. Оборудование может быть размещено на площади, не превышающей 72 кв.м. Можно заказать оборудование двух типов: типа А, требующие производственную площадь 6кв.м и дающие 6 тыс.ед. продукции в смену ( цена 5000 руб.) и типа В, требующие площадь 12 кв.м и дающие 3тыс.ед., (цена 2000 руб.). Каков оптимальный план приобретения оборудования, обеспечивающий максимальную производительность участка?

Обозначим количество приобретаемого оборудования типа А и В через Х₁ и Х₂ соответственно.

Производительность участка (целевая функция) : Z(X) =6Х₁+3Х₂.

Основные ограничения связаны

с денежными средствами : 5Х₁+2Х₂ ≤ 20,

с площадью производственного участка : 6Х₁+12Х₂ ≤ 72.

Вводим новые базисные переменные Х₃ (остаток денежных средств после закупки оборудования) и Х₄ (остаток площадей после размещения оборудования) и перепишем ограничения в виде системы уравнений:

5X₁+2Х₂+X₃=20 (X₃=20 – 5X₁ - 2X₂)

6Х₁+12Х₂+X₄ = 72 (X₄=72 – 6X₁ – 12X₂)

При этом функция цели: Z(X) =6Х₁+3Х₂+0Х₃+0Х₄.

Составляем опорный (0-ой) план: Х= (0, 0, 20, 72), т.е. пока ничего не приобретено (деньги не потрачены, площади пустуют). Составляем симплексную таблицу

План	Базис			Ci/Cj	Знач. Xi		X1	X2	X3	X4	Qmin
0	X3			0	20		5	2	1	0	20/5=4
	X4			0	72		6	12	0	1	72/6=12
Z(X) = 0							- 6	- 3	0	0	Индексная строка
1		→X1	6			4	1	0,4	0,2	0	4/0,4=10
		X4	0			48	0	9,6	-1,2	1	48/9,6=5
Z(X) = 6*4=24							0	-0,6	1,2	0	Индексная строка
2		X1	6			2	1	0	0,25	-1/24	-
		→X2	3			5	0	1	-1/8	5/48	-
Z(X) =6*2+3*5=27							0	0	9/8	1/16	Индексная строка

Очевидно, что ведущий столбец соответствует Х₁, так как имеет самый большой индекс 6. Находим минимальное значение Q_min=4 ( самое жесткое ограничение ресурса), определяя ведущую строку, показывающую, что из базисных переменных выводится Х₃, а вместо нее вводится Х₁. Пересчитываем элементы ведущей строки, разделив их на 5, а по формуле (6) определяем элементы второй и индексной строк. Целевая функция для 1-ого плана равна Z(X) =6*4+3*0=24.Однако, один из коэффициентов индексной строки для столбца Х₂ остается отрицательным -0,6, следовательно данный план не оптимален, и требуется еще одна итерация (шаг) для его улучшения. Выбираем ведущим 2-ой столбец и по минимальному значению Q_min=5 определяем ведущую строку с базисной переменной Х₄. Выполнив те же преобразования, получаем 2-ой план, который будет оптимальным, так как все индексные коэффициенты положительны. Проанализируем полученные результаты. При оптимальном решении целевая функция имеет максимальное значение 27тыс.руб., при этом оба ресурса выведены из базиса, следовательно израсходованы полностью! Убедимся в этом : 5*2+2*5=20 тыс.руб., 6*2+12*5=72 кв.м. Искомое решение Х= (2; 5;0;0;).Так бывает далеко не всегда.

---

Пример №3.

Коммерческое предприятие реализует три вида продукции А,В, и С. Нормативы затрат материально-денежных ресурсов на реализацию единицы продукции (или 1 тыс. товарооборота) представлены в таблице.

Виды ресурсов	Нормы затрат ресурсов на 1тыс. руб. товарооборота			Объем ресурсов
	Группа А	Группа В	Группа С
Рабочее время продавцов, чел.-ч	0,1	0,2	0,4	1100
Площадь торговых залов, м2	0,05	0,02	0,02	120
Площадь складских помещений, м2	3	1	2	8000
Доход, тыс. руб.	3	5	4

В последней строке задан доход от продажи товара каждой группы. Необходимо определить объем и структуру товарооборота, при котором доход предприятия будет максимальным. Математическая модель задачи: определение вектора Х=(Х₁; Х₂; Х₃), где Х – количество проданных изделий А, В,С, который удовлетворяет неравенствам

0,1X₁ + 0,2X₂ +0,4 X₃ ≤ 1100_,

0,05X₁ + 0,02X₂ +0,02 X₃ ≤ 120,

3X₁+1X₂+2X₃≤8000. X₁≥0 X₂≥0 X₃≥0

и обеспечивает максимальное значение целевой функции Z(X)=3Х₁+5Х₂+4Х₃.

Для построения опорного 0-ого плана вводим дополнительно базисные переменные Х₄, Х₅,Х₆ (определяем объемы неиспользованных ресурсов), преобразовывая систему неравенств в систему уравнений,

0,1X₁ + 0,2X₂ +0,4 X₃+Х₄= 1100_,

0,05X₁ + 0,02X₂ +0,02 X₃+Х₅= 120,

3X₁+1X₂+2X₃+Х₆=8000.

решаем полученную систему относительно базисных переменных Х₄, Х₅, Х₆:

Х₄=1100-0,1X₁ - 0,2X₂ -0,4 X_{3 ,}

Х₅= 120-0,05X₁ - 0,02X₂ -0,02 X_3,

Х₆=8000-3X₁ -X₂-2X_3.

Функцию цели запишем в виде Z(X)=0 – (- 3Х₁ – 5Х₂ – 4Х₃) и полагая, что основные переменные Х₁=Х₂=Х₃=0, получим опорный план Х=(0; 0; 0; 1100; 120; 8000), при котором целевая функция Z(X)=0 (товары не продаются, ресурсы не используются, доход нулевой). Опорный план запишем в симплексную таблицу:

План	Базис	Ci/Cj	Знач. Xi	X1	X2	X3	X4	X5	X6	Qmin
0	X4	0	1100	0,1	0,2	0,4	1	0	0	5500
	X5	0	120	0,05	0,02	0,02	0	1	0	6000
	X6	0	8000	3	1	2	0	0	1	8000
Z(X) = 0				- 3	- 5	- 4	0	0	0	Индекс строка
1	→X2	5	5500	0,5	1	2	5	0	0	11000
	X5	0	10	0,04	0	-0,02	-0,1	1	0	250
	X6	0	2500	2,5	0	0	-5	0	1	1000
Z(X) = 27500				- 0,5	0	6	25	0	0	Индекс строка
2	X2	5	5375	0	1	2,25	6,25	-12,5	0	-
	→X1	3	250	1	0	-0,5	-2,5	25	0	-
	X6	0	1875	0	0	1,25	1,25	-62,5	1	-
Z(X) = 27625				0	0	5,75	23,75	12,5	0	Индекс строка

---

Естественно, 0-ой план не оптимален, так как коэффициенты в индексной строке отрицательные -3, -5, -4.Ведущий столбец содержит Х₂, а ведущая стока содержит Х₄, РЭ=0,2 находится на их пересечении. Формируем 1-ый план аналогично предыдущему примеру, в индексной строке только коэффициент при Х₁ отрицателен -0,5, поэтому ведущий столбец содержит Х₁. Строка, содержащая Х₅, становится ведущей , и после итерации получаем 2-ой план, все коэффициенты которого в индексной строке положительны. Это означает, что план Х= (250; 5375; 0; 0; 0; 1875) оптимален, и целевая функция при данных значениях Х имеет максимальное значение Z(X) =27625 тыс.руб.

Проанализируем полученное решение: для получения максимальной прибыли необходимо продать 250 ед. товаров группы А, 5375 ед. товаров группы В, товары группы С вообще не реализуются! В оптимальном плане среди базисных переменных находится Х₆. Это указывает на то, что 1875м² складских помещений не используются, то есть данный ресурс в исходном объеме избыточен, и данная его часть (1875м²) может быть применена в других целях.

Метод искусственного базиса.

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

a_i1 X₁ + a_i2 X₂ +…a_in X _n ≥ b_i (7)

или уравнений a_i1 X₁ + a_i2 X₂ +…a_in X _n = b_i (7*),

то невозможно получить опорный план в искомом виде. В этом случае для соблюдения равенств (7*) вводится искусственный базис Y_i , причем искусственные переменные не имеют непосредственного отношения к содержанию поставленной задачи, но позволяют построить опорный (стартовый) план:

a_i1 X₁ + a_i2 X₂ +…a_in X _n +Y_i = b_i (8).

Целевая функция при решении задачи на максимум запишется в виде:

Z(X) =∑C_jX_j+(-M)∑Y_i (9),

при решении аналогичной задач на минимум :

Z(X)=∑C_jX_j+(M)∑Y_i (9*),

где М – очень большое положительное число, своего рода штраф за использование искусственных переменных.

В случае неравенств (7) первоначально вводим дополнительные переменные Х_n+i со знаком минус. Их матрица не будет единичной, поэтому в каждое неравенство системы (7) вводим искусственные переменные У_i:

a_i1X₁+a_i2X₂+…a_inX_n–X_n+i+Y_i=b_i (10) Целевая функция при этом Z(X)=∑C_jX_j+0∑X_n+i+(-M)∑Y_i (для нахождения максимума). Применение искусственного базиса придает симплексному методу большую гибкость и позволяет использовать его для широкого круга задач.

Пример №4.

Определить максимальное и минимальное значение прибыли при выпуске двух видов продукции А и В, если затраты на производство и доходность от реализации единицы продукции приведены в таблице. Основным условием является полная занятость рабочих на предприятии.

---

Виды ресурсов	Нормы затрат на производство 1 т		Запасы ресурсов
	Группа А	Группа В
Сырье ,т	1,0	1,0	6
Рабочее время чел.-час	2,0	1,0	8
Доход с 1 т, тыс. руб.	3	2

Математически ограничения выпуска продукции запишутся в виде смешанной системы:

1Х₁ + 1Х₂≤ 6,

2Х₁ + 1Х₂ =8.

Введем для первого неравенства базисную переменную Х₃, а для второго уравнения искусственную переменную Y₁:

1Х₁ + 1Х₂+ Х₃ = 6,

2Х₁ + 1Х₂ +Y₁ =8.

Выразим из полученной системы уравнений Х₃ и Y₁ и для определения максимума целевую функцию представим:

Z(X)= 3X₁+ 2X₂+0X₃ –MY₁= 3X₁+ 2X₂ –M(8 -2X₁ –X₂)=

= 3X₁+ 2X₂ –8M +2MX₁ + MX₂ = (2M + 3)X₁ + (M + 2)X₂ -8M

Для опорного плана - Х=(0,0,6,8). Построим симплексную таблицу:

План	Базис	Ci/Cj	Знач. Xi	X1	X2	X3	Y1	Qmin
0	X3	0	6	1	1	1	0	6/1=6
	Y1	-M	8	2	1	0	1	8/2=4
Z(X) = -8M				-2M-3	-M-2	0	0	Индексная строка
1	X3	0	2	0	0,5	1	-0,5	2/0,5=4
	→X1	3	4	1	0,5	0	0,5	4/0,5=8
Z(X) = 3*4=12				0	- 0,5	0	М+1,5	Индексная строка
2	→X2	2	4	0	1	2	-1	-
	X1	3	2	1	0	-1	1	-
Z(X) =3*2+2*4=14				0	0	1	М+1	Индексная строка

Как правило, улучшение опорного плана начинается с выведения из базиса искусственной переменной Y₁ .Оптимальный план Х=(2,4,0,0) получен на второй итерации, при этом доход максимален 14тыс. руб. , а коэффициенты индексной строки неотрицательны. Легко убедиться, что в данной задаче при оптимальном плане ресурсы использованы полностью (2*1+4*1=6; 2*2+1*4=8).

При нахождении минимальной доходности иначе формулируем целевую функцию ( в качестве слагаемого вводится +MY₁ :

Z(X)= 3X₁+ 2X₂+0X₃ +MY₁= 3X₁+ 2X₂ +M(8 -2X₁ –X₂)=

= 3X₁+ 2X₂ +8M - 2MX₁ - MX₂ = (3 - 2M)X₁ + (2 - M )X₂ +8M

Опорный план тот же , но коэффициенты индексной строки в симплексной таблице иные. Ведущий столбец, по-прежнему, выбираем по наибольшему по абсолютному значению положительному коэффициенту при X_{1 ,} ведущая строка определяется по минимальному значению Q_min=4.При первой итерации из базиса выводится искусственная переменная Y₁.

План	Базис		Ci/Cj		Знач. Xi	X1	X2	X3	Y1	Qmin
0	X3		0		6	1	1	1	0	6/1=6
	Y1		M		8	2	1	0	1	8/2=4
Z(X) = 8М						2M-3	M-2	0	0	Индексная строка
1		X3		0	2	0	0,5	1	-0,5	2/0,5=4
		→X1		3	4	1	0,5	0	0,5	4/0,5=8
Z(X) = 3*4=12						0	- 0,5	0	-М+1,5	Индексная строка

---

Полученные отрицательные значения коэффициентов в индексной строке X_i свидетельствуют об оптимальности 1-ого плана, при этом минимальный доход 12 тыс. рублей.

Он обеспечивается только выпуском продукции А (продукция В не выпускается), сырье не используется полностью (остаток Х₃=2т), при этом выполнено основное условие - рабочие полностью заняты на производстве.

Пример №5.

Цех выпускает краску для наружных (А) и внутренних работ ( В), общие затраты на производство которой и доход от реализации представлены в таблице. Согласно исследованиям маркетингового отдела количество продаваемой краски день не менее 5 т. Определить максимальную доходность такого производства.

Виды ресурсов	Нормы затрат на производство 1 т		Запасы ресурсов
	Группа А	Группа В
Сырье ,т	3,0	2,0	12
Доход с 1 т, тыс. руб.	2	1

Математически ограничения выпуска продукции запишутся в виде системы неравенств:

3X₁ + 2X₂ ≤ 12,

X₁ + X₂ ≥ 5.

Введем для первого неравенства базисную переменную Х₃, а для второго уравнения отрицательную Х₄ и искусственную переменную Y₁:

3X₁ + 2X₂ + X₃ = 12,

X₁ + X₂ – X₄ + Y₁ = 5.

Выразим из полученной системы уравнений Х₃ и Y₁ и для определения максимума целевую функцию представим:

Z(X) = 2X₁+ 1X₂+0X₃ +0Х₄ –MY₁=2X₁+ 1X₂ –M*(5 - X₁ –X₂ + Х₄) =

= (2 + М)X₁+ (1 + М)X₂ –MХ₄ - 5M

Для нулевого опорного плана Х=( 0,0,12,5) построим симплексную таблицу:

План	Базис	Ci/Cj	Знач. Xi	X1	X2	X3	Х4	Y1	Qmin
0	X3	0	12	3	2	1	0	0	12/3=4
	Y1	-M	5	1	1	0	-1	1	5/1=5
Z(X) = - 5М				-M-2	-M-1	0	М	0	Индекс строка
1	→X1	2	4	1	2/3	1/3	0	0	4/(2/3)=6
	Y1	-M	1	0	1/3	-1/3	-1	1	1/(1/3)=3
Z(X) = 2*4 - M=8-M				0	-M/3+1/3	(M+2)/3	M	0	Индекс строка
2	X1	2	2	1	0	1	2	-2	-
	→X2	1	3	0	1	-1	-3	3	-
Z(X) = 2*2+1*3=7				0	0	2/3M+1	1	М-1	Индекс строка

Полученный план Х=(2,3,0,0), при этом доход максимален 7тыс. руб., ресурсы использованы полностью (2*3+3*2=12) и выполнено условие маркетинга (2*1+3*1=5).

Получение целочисленных решений

при решении оптимизационных задач.

Метод Гомори.

Значительная часть задач хозяйственной и коммерческой деятельности требует целочисленного решения, например, выпуск и распределение товаров, использование агрегатов при загрузке оборудования и т.д. Как быть, если симплекс-метод дает при оптимальном решении дробные значения основных переменных? В этом случае идет поиск наиболее близкого к оптимальному целочисленного решения. Применяются различные методики: 1) отсечения, 2) комбинированные, 3) приближенные. К числу первых относится известный метод Гомори.

---

Смотрите также файлы

• Происхождение термина Русь.docx

• Диплом ТОВАРОВЕДЫ.docx

• ХОО реферат.docx

• Методы оценки земельных ресурсов.docx

• Курсовая работа.docx