Пример выполнения лабораторной работы. Сведем исходные данные варианта * в удобную для построения математической модели таблицу 2.

 

Сведем исходные данные варианта * в удобную для построения математической модели таблицу 2.

 

Таблица 2.

Ресурсы	Продукция	Объем ресурсов	Пn+1
П1	П2	П3
I					0,5
ІІ
ІІІ
Цена реализации единицы продукции Пi				–

 

1. Пусть Х=(х₁, х₂, х₃) – план выпуска продукции соответственно П₁, П_2, П₃. Z – сумма дохода от реализации готовой продукции. Тогда математическая модель задачи имеет вид.

 

Z = 3x₁ + 4x₂ + 5x₃ –> max,

x₁ + 2x₂ + x₃ ≤ 370,

3x₁ + 2x₃ ≤ 560,

x₁ + 4x₂ ≤ 420,

x_j ≥ 0, j = 1, 2, 3.

 

Решение задачи симплекс-методом, аналогичное полученному Вами в 1-й части работы, приведено в таблице 3. Для получения решения Вашего варианта (одного из 10-ти, предложенных в таблице 1) можно также использовать SimplexWin.exe с ограничениями – неравенствами.

Поскольку все оценки (m +1)-ой строки последней симплекс-таблицы 3 неотрицательные, отысканный опорный план является оптимальным. Х*=(0, 45, 280, 0, 0, 240), Z(Х*)=1580.

Основные переменные х*₁=0, х*₂=45, х*₃=280 показывают, что продукцию П₁ производить нецелесообразно; продукции П₂ нужно произвести 45 единиц, П₃ – 280 единиц. При этом, подставляя в ограничения, видим, что первый и второй ресурсы используются полностью, а третьего остается в избытке 240 единиц.

 

Таблица 3

 

2. Двойственная к данной задача имеет вид:

 

Т(l)= 370λ₁ + 560λ₂ + 420l₃ –> min,

λ₁ + 3λ₂ + λ₃ ≥ 3,

2λ₁ + 4λ₃ ≥ 4,

λ₁ + 2λ₂ ≥ 5,

λ_i ≥ 0, i = 1,2,3.

Ее решение отыщем в последней строке симплексной таблицы 3 из соотношения

 

Имеем оптимальные λ*=(2, 3/2, 0), Т(λ*)=1580.

Двойственные переменные показывают меру дефицитности ресурсов, они численно равняются изменению целевой функции при изменении соответствующего ресурса на единицу, следовательно, увеличение первого ресурса на единицу дает увеличение объема реализации на λ*₁ = 2, второго – на λ*₂ = 3/2. Третий ресурс является избыточным, поэтому его увеличение ни к чему не приведет (λ*₃ = 0).

Подставив вектор двойственных оценок λ* в систему ограничений двойственной задачи, имеем

1 · 2 + 3 · 3/2 + 1 · 0 = 11/2 > 3,

2 · 2 + 4 · 0 = 4 = 4,

1 · 2 + 2 · 3/2 = 5 = 5.

 

Первое ограничение двойственной задачи выполняется как строгое неравенство – это свидетельствует об убыточности продукции П₁, поэтому, согласно с оптимальным планом, ее нецелесообразно производить. Стоимость ресурсов, которые тратятся на единицу продукции П₁, превышает стоимость единицы этой продукции на 7/2. Стоимость ресурсов, которые используются при производстве единицы продукции П₂ и П₃ совпадает с их ценами, поэтому их выпуск экономически целесообразен.

Раскроем состав двойственных переменных, например,

λ*₁ = С _б· P ₃₊₁ – c₄ = 1/2 · 4 + 0·5 + (-2) · 0 = 2 (см. 3-й и 8-ой столбцы последней из симплекс-таблиц 3).

Это означает, что при увеличении первого ресурса на единицу выпуск продукции П₂ увеличится на 1/2, выпуск продукции П₃ не изменится, избыток третьего ресурса уменьшится на –2.

Аналогично можно раскрыть состав других двойственных переменных.

 

3. Коэффициенты взаимозаменяемости η_ik показывают, сколько единиц ресурса i необходимо дополнительно иметь, чтобы компенсировать уменьшение ресурса k на единицу, то есть, чтобы значение целевой функции не изменилось:

.

Построим матрицу взаимозаменяемости (таблица 4).

 

Таблица 4.

λ*i	λ*κ
λ*1=2	λ*2=3/2	λ*3=0
λ*1		3/4
λ*2	4/3
λ*3	∞	∞

 

Например, η₂₁=4/3 означает, что уменьшение первого ресурса на единицу можно компенсировать 4/3 единицами второго ресурса и т.д.; η₃₁=∞ означает, что уменьшение первого ресурса на единицу нельзя компенсировать никакими увеличениями третьего ресурса; η₁₃=0 означает, что, поскольку третий ресурс избыточен, его уменьшение на единицу ничем компенсировать не нужно.

 

4. Для определения границ изменения стоимости – коэффициентов целевой функции, при которых сохранится ассортимент и объем произведенной продукции, рассмотрим два случая:

а) анализ коэффициентов целевой функции при базисных переменных можно провести по соотношениям (здесь первые m переменных – оптимальный базис):

.

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

1/4·∆С₂-3/2·∆С₃-2·∆С₆≤7/2,

-1/2·∆С₂ +2·∆С₆ ≤ 2,

1/4·∆С₂-1/2·∆С₃ - ∆С₆ ≤ 3/2.

Отсюда, если ∆С₃=∆С₆=0, то

-4≤∆С₂≤6,

и коэффициент С₂ может оставаться в промежутке 0≤С₂≤10, при этом найденный план остается оптимальным.

Если же ∆С₂=∆С₆=0, тогда

-7/3≤ ∆С₃≤∞,

а коэффициент С₃ может оставаться в промежутке 8/3≤С₃≤∞.

Поскольку х₆ свободная дополнительная переменная, то коэффициент при ней в целевой функции С₆=0, поэтому вариации ∆С₆ всегда равняются 0.

 

б) Анализ коэффициентов целевой функции при небазисных переменных проводится по соотношениям

.

Для рассматриваемой задачи, поскольку С₄ и С₅ - коэффициенты при свободных дополнительных переменных, то их вариации равняются 0. Поэтому определяем только промежуток изменения коэффициента С₁, для которого, -∞≤∆С₁≤7/2. Следовательно, 0≤С₁≤13/2 потому, что цены на продукцию не могут быть отрицательными.

 

5. Определим границы изменения ресурсов, в которых структура оптимального плана сохранится, то есть выпуск продукции П₂ и П₃ остается рентабельным (т.е. все x*_{базисные} ³0). Для этого нужно проанализировать соотношения:

.

Вычитая, получим: .

Матрица Р_х^-1 обратна к Р_х. Последняя состоит из вектор-столбцов Р_2, Р₃, Р₆ нового (оптимального) базиса, записанного в старом(исходном) базисе непосредственно из начальной СТ таблицы 3. Таким образом, Р_х^-1 есть матрица перехода к новому базису, и ее элементы без вычисления могут быть взяты из столбцов векторов Р₄, Р₅, Р₆, которые составляли начальный базис, записанных в новом базисе, т.е. из конечной СТ таблицы 3. Поэтому:

.

Отсюда

-2∆b₁+∆b₂ ≤180,

-∆b₂ ≤560,

2∆b₁- ∆b₂-∆b₃ ≤ 240.

Если ∆b₂=∆b₃=0, то –90≤∆b₁≤120, а 280≤b₁≤490. Дальше, если ∆b₁=∆b₃=0, то –240≤∆b₂≤180, а 320≤b₂≤740. Аналогично, для ∆b₃ имеем –240≤∆b₃≤∞, а 180≤b₃≤∞. Следовательно, если один из ресурсов изменяется в определенных выше промежутках, а остальные остаются неизменными, то оптимальный базис исходной задачи сохранится, а значит оптимальный план двойственной задачи не изменяется (сохранится устойчивость двойственных оценок, поскольку в формуле λ*_i = С _б· P _m+i – c_m+i нет зависимости от b).

 

6. Рассмотрим рентабельность выпуска новой продукции, характеристики которой приведены в таблице 2: С_n+1=3, а_i,n+1=(0,5; 1; 2). Обозначив ее объем через х_n+1, имеем такую новую математическую модель задачи

Z=3x₁+4x₂+5x₃+3x_n+1 –> max,

x₁+2x₂+x₃+0,5x_n+1≤370,

3x₁ +2x₃ + x_n+1 ≤ 560,

x₁+4x₂ +2x_n+1≤420,

x_j≥0, j=1,2,3; x_n+1≥0.

Дополним последнюю СТ столбцом Р_n+1 и вычислим оценку ∆_n+1 по формуле

Тогда 0,5 · 2 + 1·3/2 + 2 · 0 – 3 = –1/2≤0.

Поскольку оценка отрицательна, то выпуск дополнительной продукции является целесообразным. Вычислим компоненты вектора P_n+1 в базисе P₂, P₃, P₆, который был оптимальным:

.

Прибавим соответствующий вектор столбцов, ассоциируемый с переменной х_n+1 к последней симплекс-таблицы в таблице 3 и получим новую таблицу 5. Выполнив только один шаг симплекс-метода, находим новый оптимальный план. Для контроля заново проведите (с помощью simplexWin) полное решение новой задачи из пункта 6. Сравните результаты.

 

Таблица 5

I	Б	С	Х
Р1	Р2	Р3	Р4	Р5	Р6	Рn+1
	Р2			-1/4			1/2	-1/4
	Р3			3/2				1/2		1/2
	Р6						-2
m+1				7/2				3/2		-1/2
	Р2			-1/4			1/2	-1/4
	Р3						1/2	1/4	-1/4
	Рn+1						-1	1/2	½
m+1							3/2	7/4	¼

 

Следовательно, Х*=(0, 45, 280, 0, 0, 0, 120), Z(Х*)=1640. Вместе с этим найдем и решение соответствующей двойственной задачи λ*=(3/2, 7/4, 1/4), Т(λ*)=1640.

 

7. Пусть недефицитный ресурс уменьшится на N = 60%. Тогда новый вектор ресурсов приобретет вид b =(370, 560, 168). Вычислим компоненты плана по формуле.

Имеем

Поскольку новое решение недопустимое, то осуществив один шаг двойственного симплекс-метода, получим новый план. На основе таблицы 3 имеем таблицу 6.

 

Таблица 6

I	Б	С	Х
Р1	Р2	Р3	Р4	Р5	Р6
	Р2			-1/4			1/2	-1/4
	Р3			3/2				1/2
	Р6		-12				-2
m+1				7/2				3/2
	Р2			1/4					1/4
	Р3			3/2				1/2
	Р4			-1				-1/2	-1/2
m+1				11/4				5/2

 

Следовательно, новый план Х*=(0, 42, 280), Z(Х*)=1568. Оптимальное решение двойственной задачи λ*=(0, 5/2, 1), Т(λ*)=1568.

 

Данный пример является шаблоном для заполнения отчета по Вашему варианту.