войственный симплекс-метод

арианты 1.1-1.5

 

а) Фирма производит две модели книжных полок К₁ и К₂. Их производство ограничено наличием высококачественных досок А₁ и временем машинной обработки А₂. Для изготовления книжной полки j-й модели требуются a_1j, j=1,2 квадратных метров досок и a_2j, j=1,2 минут машинного времени. Фирма может в неделю получать от поставщика b₁ квадратных метров досок и использовать b₂ минут машинного времени. Книжная полка j-й модели приносит прибыль c_j, j=1,2 денежных единиц. Сколько полок каждой модели следует выпускать в неделю, чтобы получить максимальную прибыль? Спрос не ограничен.

б) Спрос на полки ограничен в неделю числом b. Как при этом изменится оптимальное решение?

в) Качество книжных полок можно улучшить, введя их дополнительную обработку А₃; на каждую полку j-й модели требуется a_3j, j=1,2 минут дополнительного времени, ресурс которого ограничен числом b₃ минут. Прибыль от реализации полок возрастает до величины c_j¢, j=1,2. Имеет ли смысл вводить дополнительную обработку? Спрос не ограничен.

г) Фирма анализирует возможность выпуска третьей модели полок К₃, которая может принести прибыль c₃. Затраты ресурсов при этом составляют a₁₃ (м²) и a₂₃ (мин) на одну полку. Введение новой модели потребует переналадки оборудования, при этом изменяются a₂₁ на а₂₁¢ и a₂₂ на a₂₂. Ресурсы b₁ и b₂ остаются прежними. Спрос не ограничен.

Определите, какой из вариантов а, в, или г наиболее выгоден для фирмы в смысле максимума прибыли?

1.1

 

	K1	K2	K3	bi
A1
A2			20
A3	3,5		-
cj
cj¢	2,2	4,5	-

 

b=450 a₂₁¢=16 a₂₂¢=32

1.2

 

	K1	K2	K3	bi
A1
A2			18
A3			-
cj		3,5	4,5
cj¢			-

 

b=400 a₂₁¢=14 a₂₂¢=30

1.3

	K1	K2	K3	bi
A1	3,2
A2			15
A3			-
cj		3,5
cj¢	2,2	3,8	-

 

b=600 a₂₁¢=10 a₂₂¢=20

 

1.4

 

	K1	K2	K3	bi
A1	7,5	7,5
A2	4,5		10
A3			-
cj		3,5
cj¢	2,2	3,8	-

 

b=700 a₂₁¢=5 a₂₂¢=10

1.5

 

	K1	K2	K3	bi
A1
A2
A3			-
cj	2,5
cj¢			-

 

b=700 a₂₁¢=12 a₂₂¢=18

 

 

арианты 2.1-2.5

 

а) Фирма производит два типа подшипников П₁ и П₂, каждый из которых должен быть обработан на двух станках A_i, i=1,2. Время, требуемое для каждой стадии обработки, равно a_ij, j=1,2 часов. Ресурсы времени каждого станка равны b_i, i=1,2 часов. Каждый подшипник j-го типа приносит прибыль c_j, j=1,2 денежных единиц. Фирма хочет производить подшипники в количестве, максимизирующем её прибыль. Спрос не ограничен.

б) Спрос на подшипники ограничен числом b. Как при этом изменится оптимальное решение?

в) Для повышения качества подшипников фирма может ввести их дополнительную обработку на станке A₃. На каждый подшипник j-го типа требуется a_3j, j=1,2 часов; ресурс времени станка А₃ равен b₃ часов. Прибыль от реализации подшипника j-го типа станет равной c_j¢, j=1,2 денежных единиц. Стоит ли вводить дополнительную обработку? Спрос не ограничен.

г) Фирма может начать производство третьего типа подшипников П₃ на прежнем оборудовании. Прибыль от реализации единицы П₃ составляет c₃ денежных единиц. Ресурсы b₁ и b₂ остаются прежними. Спрос не ограничен.

Определите, какой из вариантов а, в или г наиболее выгоден для фирмы в смысле максимальной прибыли?

2.1

	П1	П2	П3	bi
A1	0,01	0,02	0,04
A2	0,02	0,01	0,03
A3	0,03	0,07	-
cj	12,5
cj¢			-

 

b=8000

2.2

	П1	П2	П3	bi
A1	0,01	0,02	0,04
A2	0,012	0,01	0,015
A3	0,02	0,01	-
cj
cj¢			-

 

b=9000

 

2.3

	П1	П2	П3	bi
A1	0,02	0,01	0,008
A2	0,012	0,018	0,009
A3	0,01	0,015	-
cj
cj¢			-

 

b=9000

2.4

	П1	П2	П3	bi
A1	0,025	0,02	0,02
A2	0,02	0,008	0,04
A3	0,02	0,03	-
cj
cj¢		2,5	-

 

b=9500

2.5

 

	П1	П2	П3	bi
A1	0,018	0,01	0,009
A2	0,01	0,02	0,04
A3	0,015	0,01	-
cj
cj¢			-

 

b=11000

 

 

арианты 3.1-3.5

 

а) В цехе производится ткань двух артикулов Т₁ и Т₂ на ткацком станке А₁. Ресурс времени станка равен b₁ часов. Для изготовления ткани требуется пряжа А₂, ресурс ее ограничен величиной b₂ (м пряжи). Затраты времени на производство ткани j-го вида составляют a_1j, j=1,2 (ч/м ткани); нормы расхода пряжи – a_2j, j=1,2 (м пряжи/м ткани). Прибыль от реализации 1м ткани j-го артикула составляет c_j, j=1,2 денежных единиц. Необходимо определить оптимальный ассортимент, максимизирующий прибыль цеха. Спрос не ограничен.

б) Спрос на ткань ограничен числом b. Как при этом изменится оптимальное решение?

в) Руководство цеха решило производить окраску ткани у себя. Для этого ему нужно закупать красители А₃, которых требуется a_3j, j=1,2 (кг/м ткани). Количество красителей ограничено величиной b₃ (кг). Есть ли смысл производить окраску ткани, если прибыль от реализации 1м окрашенной ткани возрастает до c_j¢? Спрос не ограничен.

г) В производство на том же оборудовании можно ввести еще один артикул ткани Т₃. Выгодно ли это с точки зрения максимизации прибыли, если расход ресурсов на изготовление 1м ткани составляет a_i3, i=1,2 при тех же запасах, а прибыль от реализации 1м ткани Т₃ равна c₃? Спрос не ограничен.

Какого из вариантов а, в или г лучше придерживаться руководству цеха?

3.1

 

	Т1	Т2	Т3	bi
A1	0,045	0,015	0,03
A2	0,3	0,6	0,3
А3	0,04	0,02	-
cj
cj¢			-

 

b=2500

 

3.2

 

	Т1	Т2	Т3	bi
A1	0,015	0,045	0,03
A2	0,9	0,6	0,6
А3	0,025	0,035	-	87,5
cj
cj¢			-

 

b=2500

 

3.3

 

	Т1	Т2	Т3	bi
A1	0,04	0,02	0,045
A2	0,6	0,9	0,5
А3	0,025	0,03	-
cj
cj¢			-

 

b=2500

 

3.4

 

	Т1	Т2	Т3	bi
A1	0,03	0,015	0,015
A2	0,2	0,4	0,8
А3	0,03	0,012	-
cj
cj¢			-

 

b=3500

3.5

 

	Т1	Т2	Т3	bi
A1	0,04	0,02	0,04
A2	0,32	0,4	0,4
А3	0,025	0,04	-
cj
cj¢			-

 

b=3000

 

 

арианты 4.1-4.5

 

а) Фирма выпускает радиаторы двух моделей Р₁ и Р₂ для центрального отопления. Ограничения на число выпускаемых радиаторов обусловлено наличием рабочей силы А₁ (чел.-ч) и количеством стальных листов А₂ (м²), т.е. величинами b₁ и b₂. На каждый радиатор j-й модели затрачивается a_ij единиц ресурса А_i, i=1,2; j=1,2. Прибыль от реализации одного радиатора j-й модели составляет c_j, j=1,2 денежных единиц. Требуется составить такой план выпуска радиаторов, который максимизирует прибыль с учётом ограничений по материалу и рабочей силе. Спрос не ограничен.

б) Спрос на радиаторы ограничен величиной b. Как изменится оптимальный план?

в) Фирма может улучшить качество радиаторов, применяя специальное покрытие А₃, которое закупается в количестве b₃; затраты этого материала составляют a_3j, j=1,2 единиц на каждый радиатор j-й модели. При этом прибыль от реализации каждого радиатора возрастает на 10%. Стоит ли покрывать радиаторы специальным составом? Спрос не ограничен.

г) Фирма решила ввести в производство третий тип радиаторов Р₃. Затраты ресурсов на каждый радиатор составляют a₁₃ и a₂₃ единиц соответственно. Прибыль от реализации радиатора Р₃ составляет c₃ денежных единиц. Ресурсы b₁ и b₂ остаются прежними. Спрос не ограничен.

Определите, какой из вариантов а, в или г выгоднее для фирмы?

 

4.1

 

	P1	P2	P3	bi
А1	1,5	0,5	0,5
А2	0,5	0,6	1,2
А3			-
cj			5

 

b=100

 

4.2

 

	P1	P2	P3	bi
А1	0,8	1,6	0,8
А2	0,3	0,2	0,6
А3	0,9	1,0	-
cj			4

 

b=90

 

4.3

 

	P1	P2	P3	bi
А1	0,9	1,3	0,3
А2	0,6	0,5	0,4
А3			-
cj

 

b=100

 

4.4

 

	P1	P2	P3	bi
А1	1,2	0,6	0,3
А2	0,2	0,3	0,8
А3			-
cj			4

 

b=80

4.5

 

	P1	P2	P3	bi
А1	0,5	1,5
А2		0,5	0,8
А3			-
cj

 

b=90

арианты 5.1-5.5

а) Фирма выпускает два вида ваз В₁ и В₂. В процессе производства используются две технологические операции А₁ и А₂. Длительность i-й технологической операции при изготовлении вазы j-го вида составляет а_ij, i=1,2; j=1,2 минут. Фонд рабочего времени, в течение которого i-я операция может быть применена для производства ваз, равен b_i, i=1,2 минут. Прибыль от продажи вазы j-го вида составляет c_j, j=1,2 денежных единиц. Найти план производства ваз, обеспечивающий максимальную прибыль. Спрос не ограничен.

б) Спрос на вазы ограничен величиной b. Как изменится оптимальный план?

в) Фирма может улучшить качество ваз, используя третью технологическую операцию А₃; на каждую вазу j-го вида требуется а_3j, j=1,2 минут. Фонд рабочего времени, в течение которого операция А₃ может быть применена для производства ваз, равен b₃ минут. Прибыль от продажи одной вазы j-го вида возрастает до c_j, j=1,2 денежных единиц. Стоит ли использовать третью технологическую операцию? Спрос не ограничен.

г) Фирма может начать производство третьего вида ваз В₃; прибыль от реализации одной вазы составляет c₃ денежных единиц. Длительность i-й технологической операции при изготовлении вазы В₃ составляет а_i3, i=1,2 минут. Ресурсы b₁ и b₂ остаются прежним. Спрос не ограничен.

Какой из вариантов а, в или г наиболее выгоден для фирмы?

5.1

 

	В1	В2	В3	bi
A1	0,8	0,5	0,6
A2	0,4	0,5	0,6
A3	0,5	0,6	-
cj	6,5		6,5
cj¢	7,5		-

 

b=1200

5.2

	В1	В2	В3	bi
A1	0,8	0,4	0,5
A2	0,6	0,9	0,8
A3	0,4	0,6	-
cj			6,5
cj¢			-

 

b=1000

5.3

	В1	В2	В3	bi
A1	0,4	0,8	0,3
A2	0,6	0,5	0,7
A3	0,8	0,4	-
cj
cj¢			-

 

b=900

 

5.4

	В1	В2	В3	bi
A1	0,9	0,5	0,5
A2	0,4	0,8	0,6
A3	0,6	0,4	-
cj
cj¢			-

 

b=1000

5.5

 

	В1	В2	В3	bi
A1	0,5	0,4	0,5
A2	0,4	0,8	0,5
A3	0,4	0,8	-
cj
cj¢			-

 

b=1100

4. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

войственный симплекс-метод

Двойственный симплекс-метод представляет собой итерационный метод решения задач ЛП, при использовании которого сначала получается недопустимое, но «лучшее, чем оптимальное», решение (в обычном симплекс-методе сначала находится допустимое, но неоптимальноерешение). Когда полученное решение оказывается допустимым, итерационный процесс вычислений заканчивается, так как это решение является и оптимальным.

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

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

Условие оптимальностибазисного решения формулируется следующим образом: все компоненты базисного решения являются неотрицательными.

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

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

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

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

1. Новое ограничение при полученном решении выполняется, поэтому решение остаётся неизменным.

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

Пример.Дана задача ЛП:

Найдём её решение с помощью симплекс-метода. Для этого преобразуем задачу к канонической форме, вводя дополнительные переменные x₃ и x₄:

Итоговая симплекс-таблица представлена табл. 1.

Таблица 1

 

Базис	Св. член	x1	x2	x3	x4
x1				4/5	-1/5
x2				-3/5	2/5
f				1/5	1/5

 

Таким образом, задача ЛП имеет решение x^*=(1, 3), при этом f(x^*)=4.

Пусть к предыдущей задаче добавлено ограничение

x₁ +2x₂4.

Новое ограничение при полученном решении не выполняется (x₁^*+2x₂^*=7>4), поэтому найдём новое решение.

Добавляем в новое ограничение дополнительную переменную x₅, которую затем введём в базис:

x₁ +2x₂+x₅ =4, x₅0.

Используя итоговую симплекс-таблицу исходной задачи, выражаем базисные переменные, содержащиеся в новом ограничении, через свободные переменные:

 

и подставляем полученные выражения в новое ограничение:

 

 

В качестве базисных выбираем переменные x₁, x₂, x₅. Таким образом, Б₀={x₁, x₂, x₅}. В результате получаем табл. 2.

Таблица 2

	Базис	Св. член	x1	x2	x3	x4	x5
	x1				4/5	-1/5
	x2				-3/5	2/5
	x5	-3			2/5	-3/5
	f				1/5	1/5
						1/3

Из табл. 2 следует, что начальное базисное решение имеет вид БР₀={x₁=1, x₂=3, x₅= 3}. БР₀ не является допустимым, поскольку в столбце свободных членов есть отрицательный коэффициент Задача разрешима, поскольку в строке x₅ есть отрицательный коэффициент. Находим Б₁:

x₅ выводим из базиса;

Таким образом, Б₁={x₁, x₂, x₄}. В результате получаем табл. 3.

Таблица 3

 

Базис	Св. член	x1	x2	x3	x4	x5
x1				2/3		-1/3
x2				-1/3		2/3
x4				-2/3		-5/3
f				1/3		1/3

 

Из табл. 3 следует, что БР₁={x₁=2, x₂=1, x₄=5}. БР₁ является допустимым и, следовательно, оптимальным решением.

Таким образом, задача ЛП

имеет решение x*=(2, 1), при этом f(x*)=3.