Курсовая: Анализ экономических задач симплексным методом

Курсовая: Анализ экономических задач симплексным методом

Все эти виды ограничивающих факторов называют ингре­диентами

. Пусть их число равно m; припишем им индекс i

. Они ограничены, и их количества равны соответственно

условных единиц. Таким обра­зом,

- вектор ресурсов. Известна экономическая выгода (мера полезности) производства

продукции каждого вида, исчисляемая, скажем, по отпуск­ной цене товара, его

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

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

, т. е. —

вектор цен. Известны также технологические коэффициенты

, кото­рые указывают, сколько единиц i–го ресурса требуется для производства

единицы продукции j-го вида. Матрицу коэффициентов

называют технологической и обо­значают буквой А. Имеем

. Обозначим через

план производства, показывающий, какие виды товаров

нужно произво­дить и в каких количествах, чтобы обеспечить предприя­тию максимум

объема реализации при имеющихся ре­сурсах.

Так как - цена

реализации единицы j'-й продукции, цена реализованных

единиц будет равна ,

а общий объем реализации

Это выражение — целевая функция, которую нужно мак­симизировать.

Так как - расход

i-го ресурса на производство

единиц j-й продукции, то, просуммировав расход i-го ресурса на выпуск всех n

видов продукции, получим общий расход этого ресурса, который не должен

превосхо­дить

единиц:

Чтобы искомый план

был реализован, наряду с ограничениями на ресурсы нужно наложить условие

неотрицательности на объёмы

выпуска продукции:

.

Таким образом, модель задачи о наилучшем использовании ресурсов примет вид:

(1)

при ограничениях:

(2)

(3)

Так как переменные

входят в функцию и

систему ограничений только в первой степени, а показатели

являются постоянными в планируемый период, то (1)-(3) – задача линейного

программирования.

5.2 Задача о смесях.

В различных отраслях народного хозяйства возникает проблема составления таких

рабочих смесей на основе исходных материалов, которые обеспе­чивали бы

получение конечного продукта, обладающего определенными свойствами. К этой

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

животноводстве, шихт в металлургии, горючих и сма­зочных смесей в

нефтеперерабатывающей промышлен­ности, смесей для получения бетона в

строительстве и т. д. Высокий уровень затрат на исходные сырьевые материалы

и необходимость повышения эффективности производства выдвигает на первый план

следующую задачу: получить продукцию с заданными свойствами при наименьших

за­тратах на исходные сырьевые материалы.

5.3 Задача о раскрое материалов.

Сущность задачи об оптимальном раскрое состоит в разработке таких

техно­логически допустимых планов раскроя, при которых полу­чается

необходимый комплект заготовок, а отходы (по длине, площади, объему, массе

или стоимости) сводятся к минимуму. Рассмотрим простейшую модель раскроя по

одному измерению. Более сложные постановки ведут к задачам целочисленного

программирования.

5.4 Транспортная задача.

Рассмотрим простейший ва­риант модели транспортной задачи, когда речь идет о

рациональной перевозке некоторого однородного продукта от производителей к

потребителям; при этом имеется ба­ланс между суммарным спросом потребителей и

возмож­ностями поставщиков по их удовлетворению. Причем по­требителям

безразлично, из каких пунктов производства будет поступать продукция, лишь бы

их заявки были пол­ностью удовлетворены. Так как от схемы прикрепления

потребителей к поставщикам существенно зависит объем транспортной работы,

возникает задача о наиболее рацио­нальном прикреплении, правильном

направлении перево­зок грузов, при котором потребности полностью

удовлетворяются, вся продукция от поставщиков вывозится, а затраты на

транспортировку минимальны.

5.5 Задача о размещении заказа.

Речь идет о задаче рас­пределения заказа (загрузки взаимозаменяемых групп

оборудования) между предприятиями (цехами, станками, исполнителями) с

различными производственными и тех­нологическими характеристиками, но

взаимозаменяемыми в смысле выполнения заказа. Требуется составить план

размещения заказа (загрузки оборудования), при кото­ром с имеющимися

производственными возможностями заказ был бы выполнен, а показатель

эффективности до­стигал экстремального значения.

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

Исходя из специализации и своих технологических возможностей предприятие

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

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

станочное оборудование. Общий объём ресурсов, расход каждого ресурса за

единицу продукции, приведены в таблице 1. Требуется определить план выпуска,

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

анализ решения и параметров модели.

Ресурсы		Выпускаемая продукция							Объём Ресурсов
	Трудовые ресурсы, чел-ч	4		2		2		8	4800
	Полуфабрикаты, кг	2		10		6		0	2400
	Станочное оборудование, станко-ч	1		0		2		1	1500
Цена единицы продукции, р.		65		70		60		120

Решение.

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

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

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

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

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

максимум реализации (максимум выручки)

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

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

таблице1.

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

опорный план является оптимальным:

,

Основные переменные

показывают, что продукцию

и выпускать

нецелесообразно, а продукции

следует произвести 400 ед.,

- 500 ед.

Дополнительные переменные

и показывают, что

ресурсы используются полностью

, а вот равенство

свидетельствует о том, что 200 единиц продукции

осталось неиспользованным.

Номера ит.	БП	Сб
				65	70	60	120	0	0	0
0		0	4800	4	2	2	8	1	0	0
		0	2400	2	10	6	0	0	1	0
		0	1500	1	0	2	1	0	0	1
			0	-65	-70	-60	-120	0	0	0
1		120	600	1/2	1/4	1/4	1	1/8	0	0
		0	2400	2	0	6	0	0	1	0
		0	900	1/2	-1/4	7/4	0	-1/8	0	1
			72000	-5	-40	-30	0	15	0	0
2		120	500	5/12	-1/6	0	1	1/8	-1/24	0
		60	400	1/3	5/3	1	0	0	1/6	0
		0	200	-1/12	-19,6	0	0	-1/8	-7/24	1
			84000	5	10	0	0	15	5	0

Выпишем из таблицы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

Страницы: 1, 2