Пример выполнения лабораторной работы

 

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

 

Таблица 2.

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

 

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

 

Z = 3x1 + 4x2 + 5x3 –> max,

x1 + 2x2 + x3 ≤ 370,

3x1 + 2x3 ≤ 560,

x1 + 4x2 ≤ 420,

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

 

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

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

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

 

Таблица 3

 

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

 

Т(l)= 370λ1 + 560λ2 + 420l3 –> min,

λ1 + 3λ2 + λ3 ≥ 3,

1 + 4λ3 ≥ 4,

λ1 + 2λ2 ≥ 5,

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

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

 

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

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

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

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

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

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

 

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

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

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

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

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

 

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

.

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

 

Таблица 4.

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

 

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

 

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

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

.

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

1/4·∆С2-3/2·∆С3-2·∆С6≤7/2,

-1/2·∆С2 +2·∆С6 ≤ 2,

1/4·∆С2-1/2·∆С3 - ∆С6 ≤ 3/2.

Отсюда, если ∆С3=∆С6=0, то

-4≤∆С2≤6,

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

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

-7/3≤ ∆С3≤∞,

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

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

 

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

.

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

 

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

.

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

Матрица Рх-1 обратна к Рх. Последняя состоит из вектор-столбцов Р2, Р3, Р6 нового (оптимального) базиса, записанного в старом(исходном) базисе непосредственно из начальной СТ таблицы 3. Таким образом, Рх-1 есть матрица перехода к новому базису, и ее элементы без вычисления могут быть взяты из столбцов векторов Р4, Р5, Р6, которые составляли начальный базис, записанных в новом базисе, т.е. из конечной СТ таблицы 3. Поэтому:

.

Отсюда

-2∆b1+∆b2 ≤180,

-∆b2 ≤560,

2∆b1- ∆b2-∆b3 ≤ 240.

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

 

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

Z=3x1+4x2+5x3+3xn+1 –> max,

x1+2x2+x3+0,5xn+1≤370,

3x1 +2x3 + xn+1 ≤ 560,

x1+4x2 +2xn+1≤420,

xj≥0, j=1,2,3; xn+1≥0.

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

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

Поскольку оценка отрицательна, то выпуск дополнительной продукции является целесообразным. Вычислим компоненты вектора Pn+1 в базисе P2, P3, P6, который был оптимальным:

.

Прибавим соответствующий вектор столбцов, ассоциируемый с переменной х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.

 

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