Анализ задачи об оптимальном использовании сырья.

Исходя из специализации и своих технологических возможностей предприятие может выступать четыре вида продукции. Сбыт любого количества обеспечен. Для изготовления этой продукции используются трудовые ресурсы, полуфабрикаты и станочное оборудование. Общий объём ресурсов, расход каждого ресурса за единицу продукции, приведены в таблице 1. Требуется определить план выпуска, доставляющий предприятию максимум прибыли. Выполнить после оптимизационный анализ решения и параметров модели.

 

Ресурсы	Выпускаемая продукция	Объём Ресурсов
	Трудовые ресурсы, чел-ч
	Полуфабрикаты, кг
	Станочное оборудование, станко-ч
Цена единицы продукции, р.

 

 

Решение.

Пусть - объёмы продукции планируемый к выпуску; - сумма ожидаемой выручки.

Математическая модель пря мой задачи:

Математическая модель двойственной задачи:

По условиям примера найти:

1. Ассортимент выпускаемой продукции, обеспечивающий предприятию максимум реализации (максимум выручки)

2. Оценки ресурсов, используемых при производстве продукции.

 

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

После второй итерации все оценки оказались отрицательными, значит, найденный опорный план является оптимальным: ,

Основные переменные показывают, что продукциюи выпускать нецелесообразно, а продукции следует произвести 400 ед., - 500 ед.

Дополнительные переменные и показывают, что ресурсы используются полностью , а вот равенство свидетельствует о том, что 200 единиц продукции осталось неиспользованным.

 

 

Номера ит.	БП	Сб
		-65	-70	-60	-120
				1/2	1/4	1/4		1/8
			1/2	-1/4	7/4		-1/8
		-5	-40	-30
				5/12	-1/6			1/8	-1/24
			1/3	5/3				1/6
			-1/12	-19,6			-1/8	-7/24

 

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

Соответствие между переменными примет вид

Учитывая это соответствие, выпишем из индексной строки последней итерации компоненты искомого плана - двойственные оценки.

min f = max Z =84000.

Запишем это неравенство в развернутой форме:

48000*15 + 2400*5 + 1500*0 = 65*0 + 70*0 + 60*400 + 120*500

Учитывая, что компонеты представляют собой оценки ресурсов заключаем:

При оптимальном плане оценка ресурсов, затраченных на выпуск продукции, совпадает с оценкой произведенной продукции.

Теперь установим степень дефицитно­сти используемых ресурсов и обоснуем рентабельность оптимального плана.

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

0+2-400+500= 1300< 1500. Это означает, что расход ресурса мень­ше его запаса, т. е. ресурс избыточный. Именно поэтому в оптималь­ном плане двойственной задачи оценка этого ресурса равна нулю.

А вот оценки и ресурсов и выражаются положительными числами 15 и 5, что свидетельствует о дефицитности этих ресурсов: они при оптимальном плане используются полностью. В самом деле, ограни­чения по этим ресурсам выполняются как строгие равен­ства: 4.0+2.0+2.400+8.500=4800, 2-0+10.0+6.400=2400.

Поскольку 15>5, ресурс считается более дефицитным, чем ресурс .

На основе теоремы (о дополняющей нежесткости) нетрудно объяснить, почему не вошла в опти­мальный план продукция и : первое и второе ограничения двой­ственной задачи выполняются как строгие неравенства: 4-15+2-5+0>65, 2-15+10*5>70.

Это означает, что оценки ресурсов, расходуемых на изготовление единицы продукции и , превышают оценки единицы этой продукции. Понятно, что такую продукцию выпу­скать предприятию невыгодно. Что же касается продукции и , то выпуск ее оправдан, поскольку оценка израсходо­ванных ресурсов совпадает с оценкой произведенной продукции: 2*15+ +6*5+2*0=60, 8*15+0=120.

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

Рассмотрим возможность дальней­шего совершенствования оптимального ассортимента выпускаемой про­дукции.

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

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

Выясним экономический смысл оценок продукции ,,,.

По оптимальному плану выпускать следует продукцию и . Оценки и этих видов продукции равны нулю. Что это означает, практически станет ясно, если представить оцен­ки в развернутой записи:

Таким образом, нулевая оценка показывает, что эта продукция является неубыточной, поскольку оценка ресурсов, расходуемых на вы­пуск единицы такой продукции, совпадает с оценкой единицы изготовлен­ной продукции.

Что же касается продукции и являющейся, как установлено выше, убыточной, а потому и не вошедшей в оптимальный план, то для ее оценок и получаем:

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

 

 

§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<a[i,j0]

then s1:=a[i,j0];

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