Анализ экономических задач симплексным методом - Экономико-математическое моделирование - Скачать бесплатно
|Выпускаемая продукция |Объём |
| | |Ресурсов |
| |[pic|[pic|[pic|[pic] | |
| |] |] |] | | |
|[pic|Трудовые ресурсы, чел-ч |4 |2 |2 |8 |4800 |
|] | | | | | | |
|[pic|Полуфабрикаты, кг |2 |10 |6 |0 |2400 |
|] | | | | | | |
|[pic|Станочное оборудование, |1 |0 |2 |1 |1500 |
|] |станко-ч | | | | | |
|Цена единицы продукции, р. |65 |70 |60 |120 |
Решение.
Пусть [pic]- объёмы продукции [pic]планируемый к выпуску; [pic]- сумма
ожидаемой выручки.
Математическая модель пря мой задачи:
[pic]
Математическая модель двойственной задачи:
[pic]
[pic]
[pic]
По условиям примера найти:
1. Ассортимент выпускаемой продукции, обеспечивающий предприятию максимум
реализации (максимум выручки)
2. Оценки ресурсов, используемых при производстве продукции.
Симплексным методом решаем прямую задачу, модель которой составлена выше в
таблице1.
После второй итерации все оценки оказались отрицательными, значит,
найденный опорный план является оптимальным: [pic], [pic]
Основные переменные [pic]показывают, что продукцию[pic]и [pic] выпускать
нецелесообразно, а продукции [pic] следует произвести 400 ед., [pic]- 500
ед.
Дополнительные переменные [pic]и [pic] показывают, что ресурсы используются
полностью [pic], а вот равенство [pic] свидетельствует о том, что 200
единиц продукции [pic] осталось неиспользованным.
|Номера|БП |Сб |[pic]|[pic]|[pic]|[pic|[pic|[pic|[pic]|[pic|
|ит. | | | | | |] |] |] | |] |
| | | | |65 |70 |60 |120 |0 |0 |0 |
|0 |[pic]|0 |4800 |4 |2 |2 |8 |1 |0 |0 |
| |[pic]|0 |2400 |2 |10 |6 |0 |0 |1 |0 |
| |[pic]|0 |1500 |1 |0 |2 |1 |0 |0 |1 |
| |[pic] |0 |-65 |-70 |-60 |-120|0 |0 |0 |
|1 |[pic]|120|600 |1/2 |1/4 |1/4 |1 |1/8 |0 |0 |
| |[pic]|0 |2400 |2 |0 |6 |0 |0 |1 |0 |
| |[pic]|0 |900 |1/2 |-1/4 |7/4 |0 |-1/8|0 |1 |
| |[pic] |72000|-5 |-40 |-30 |0 |15 |0 |0 |
|2 |[pic]|120|500 |5/12 |-1/6 |0 |1 |1/8 |-1/24|0 |
| |[pic]|60 |400 |1/3 |5/3 |1 |0 |0 |1/6 |0 |
| |[pic]|0 |200 |-1/12|-19,6|0 |0 |-1/8|-7/24|1 |
| |[pic] |84000|5 |10 |0 |0 |15 |5 |0 |
Выпишем из таблицы2. Компоненты оптимального плана двойственной задачи –
двойственные оценки. В канонической форме прямой задачи переменные [pic] -
являются свободными, а дополнительные переменные [pic]- базисными. В
канонической форме двойственной задачи свободными будут переменные [pic]- а
базисными [pic]
Соответствие между переменными примет вид
[pic]
Учитывая это соответствие, выпишем из индексной строки последней итерации
компоненты искомого плана [pic] - двойственные оценки.
min f = max Z =84000.
Запишем это неравенство в развернутой форме:
48000*15 + 2400*5 + 1500*0 = 65*0 + 70*0 + 60*400 + 120*500
Учитывая, что компонеты представляют собой оценки ресурсов заключаем:
При оптимальном плане оценка ресурсов, затраченных на выпуск продукции,
совпадает с оценкой произведенной продукции.
Теперь установим степень дефицитности используемых ресурсов и обоснуем
рентабельность оптимального плана.
Мы нашли оптимальный план [pic]выпуска продукции. При этом плане третье
ограничение прямой задачи выполняется как строгое неравенство:
0+2-400+500= 1300< 1500. Это означает, что расход ресурса [pic] меньше его
запаса, т. е. ресурс [pic] избыточный. Именно поэтому в оптимальном плане
[pic] двойственной задачи оценка [pic] этого ресурса равна нулю.
А вот оценки [pic] и [pic] ресурсов [pic] и [pic] выражаются положительными
числами 15 и 5, что свидетельствует о дефицитности этих ресурсов: они при
оптимальном плане используются полностью. В самом деле, ограничения по этим
ресурсам выполняются как строгие равенства: 4.0+2.0+2.400+8.500=4800, 2-
0+10.0+6.400=2400.
Поскольку 15>5, ресурс [pic] считается более дефицитным, чем ресурс [pic].
На основе теоремы (о дополняющей нежесткости) нетрудно объяснить, почему не
вошла в оптимальный план продукция [pic]и [pic]: первое и второе
ограничения двойственной задачи выполняются как строгие неравенства: 4-15+2-
5+0>65, 2-15+10*5>70.
Это означает, что оценки ресурсов, расходуемых на изготовление единицы
продукции [pic] и [pic], превышают оценки единицы этой продукции. Понятно,
что такую продукцию выпускать предприятию невыгодно. Что же касается
продукции [pic] и [pic] [pic], то выпуск ее оправдан, поскольку оценка
израсходованных ресурсов совпадает с оценкой произведенной продукции: 2*15+
+6*5+2*0=60, 8*15+0=120.
Таким образом, в оптимальный план войдет только та продукция, которая
выгодна предприятию, и не войдет убыточная продукция. В этом проявляется
рентабельность оптимального плана.
Рассмотрим возможность дальнейшего совершенствования оптимального
ассортимента выпускаемой продукции.
Выше установлено, что ресурсы [pic] и [pic] являются дефицитными. В связи с
этим на основе теоремы (об оценках) можно утверждать, что на каждую единицу
ресурса [pic], введенную дополнительно в производство, будет получена
дополнительная выручка [pic], численно равная [pic]. В самом деле, при
[pic]получаем [pic]. По тем же причинам каждая дополнительная единица
ресурса[pic]обеспечит прирост [pic] выручки, равный 5 р. Теперь становится
понятно, почему ресурс [pic]считается более дефицитным по сравнению с
ресурсом [pic]: он может содействовать получению большей выручки.
Что же касается избыточного ресурса [pic], то увеличение его запаса не
приведет к росту выручки, поскольку [pic]. Из приведенных рассуждений
следует, что оценки ресурсов позволяют совершенствовать план выпуска
продукции.
Выясним экономический смысл оценок [pic]продукции [pic],[pic],[pic],[pic].
По оптимальному плану [pic]выпускать следует продукцию [pic]и [pic]. Оценки
[pic] и [pic] этих видов продукции равны нулю. Что это означает,
практически станет ясно, если представить оценки в развернутой записи:
[pic]
[pic]
Таким образом, нулевая оценка показывает, что эта продукция является
неубыточной, поскольку оценка ресурсов, расходуемых на выпуск единицы такой
продукции, совпадает с оценкой единицы изготовленной продукции.
Что же касается продукции [pic] и [pic] являющейся, как установлено выше,
убыточной, а потому и не вошедшей в оптимальный план, то для ее оценок
[pic] и [pic]получаем:
[pic]
[pic]
Отсюда видно, что оценка убыточной продукции показывает, насколько будет
снижать каждая единица такой продукции достигнутый оптимальный уровень.
§8. Программа и расчеты.
{Программа составлена для решения задачи линейного программирования
симплексным методом}
uses crt;
const n=2;{число неизвестных исходной задачи}
m=3;{число ограничений}
m1=0;{последняя строка равенств}
m2=1;{последняя строка неравенств вида >=}
label 5,15,20,10;
var b,cb:array[1..m] of real;c,x,e:array[1..50] of real;a:array[1..m,1..50]
of real;
s0,max,mb,s1:real;i,j,k,i0,j0,m21,nm1,n1:integer; Bi:array[1..m] of
integer;
begin
clrscr;
writeln;
writeln (' Симплексный метод решения задачи линейного
программирования:');
writeln;
writeln (' Проведем некоторые преобразования с данной задачей:');
writeln;
writeln (' Подготовьте матрицу: сначала равенства, потом неравенства
вида >= и неравенства вида <=;');
writeln (' Целевая функция должна быть на минимум (привести ее к
такому виду); ');
writeln (' Вектор b должен состоять только из положительных элементов
(привести его к та- кому виду);');
writeln(' Введите матрицу А ',m,'*',n,' построчно:');
for i:=1 to m
do begin for j:=1 to n
do read (a[i,j]);
readln
end;
writeln (' Введите в виде строки вектор b, состоящий из ',m,'
компонент:');
for i:=1 to m
do read (b[i]);
writeln(' Введите теперь вектор с, состоящий из ',n,' компонент:');
for i:=1 to n
do read (c[i]);
m21:=m2-m1+n;nm1:=n+m-m1;n1:=n+m-m1+m2;
for i:=1 to m
do for j:=n+1 to n1
do a[i,j]:=0;
{переход к равенствам в неравенствах >=}
for i:=m1+1 to m2
do a[i,n+i-m1]:=-1;
{переход к равенствам в неравенствах <=}
for i:=m2+1 to m
do a[i,m21+i-m2]:=1;
{создание искуственного базиса}
for i:=1 to m2
do a[i,nm1+i]:=1;
{ввод mb в вектор с}
mb:=12345;
for i:=n+1 to nm1
do c[i]:=0;
for i:=nm1+1 to n1
do c[i]:=mb;
{выписать cb}
for i:=1 to m2
do begin cb[i]:=mb; Bi[i]:=nm1+i end;
for i:=m2+1 to m
do begin Bi[i]:=m21+i-m2;
cb[i]:=0;
end;
for i:=1 to n1
do x[i]:=0;
writeln(' Решение задачи:');
{применяем симплексный метод, вычисляем оценки}
5: for j:=1 to n1
do begin s0:=0;
for i:=1 to m
do s0:=s0+cb[i]*a[i,j];
e[j]:=s0-c[j]
end;
max:=e[1];j0:=1;
for i:=2 to n1
do if e[i]>max
then begin max:=e[i];
j0:=i
end;
{получили столбец с максимальной оценкой}
if max<=0
then begin for i:=1 to m
do x[Bi[i]]:=b[i];
goto 15
end;
s1:=a[1,j0];
for i:=2 to m
do if s1<=0
then goto 10;
s1:=mb;
for i:=1 to m
do if a[i,j0]>0
then if s1>b[i]/a[i,j0]
then begin
s1:=b[i]/a[i,j0];
i0:=i
end;
{главный элемент a[i0,j0]}
s0:=a[i0,j0]; Bi[i0]:=j0;
for j:=1 to n1
do a[i0,j]:=a[i0,j]/s0;
b[i0]:=b[i0]/s0;
for i:=1 to m
do if i<>i0
then begin s1:=-a[i,j0];
b[i]:=b[i]+b[i0]*s1;
for j:=1 to n1
do a[i,j]:=a[i,j]+a[i0,j]*s1
end;
cb[i0]:=c[j0];
goto 5;
10: writeln(' Нет оптимального плана, функция неограничена');
goto 20;
{просмотр иск. переменных}
15: for i:=nm1+1 to n1
do if x[i]>0
then begin writeln(' Пустое множество планов');
goto 20
end;
for i:=1 to n
do writeln(' x[',i,']=',x[i]:7:4);
20:readkey
end.
Содержание
Введение………………………………………………………………………………1
§1. Задача линейного программирования и свойства её решений…………….…4
§2. Графический способ решения
задачи линейного программирования……………………………………….…6
§3. Симплексный метод……………………………………………………………..8
§4. Понятие двойственности……………………………………………………….11
§5. Основные теоремы двойственности
и их экономическое содержание………………………………………….……14
§6. Примеры экономических задач………………………………………………..16
§7. Анализ задачи об оптимальном использовании сырья………………………19
§8. Программа и расчеты…………………………………………………………..25
|
