РефератБар.ру: | Главная | Карта сайта | Справка
Анализ экономических задач симплексным методом. Реферат.
Полнотекстовый поиск:




     Страница: 2 из 2
     <-- предыдущая следующая -->

Перейти на страницу:
скачать реферат | 1 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;beginclrscr;writeln;writeln (' Симплексный метод решения задачи линейного программирования:');writeln;writeln (' Проведем некоторые преобразования с данной задачей:');writeln;writeln (' Подготовьте матрицу: сначала равенства, потом неравенства вида
>= и неравенства вида
<=;');writeln (' Целевая функция должна быть на минимум (привести ее к такому виду); ');writeln (' Вектор b должен состоять только из положительных элементов (привести его к та- кому виду);');writeln(' Введите матрицу А ',m,'*',n,' построчно:');for i:=1 to mdo begin for j:=1 to ndo read (a[i,j]);readlnend;writeln (' Введите в виде строки вектор b, состоящий из ',m,' компонент:');for i:=1 to mdo read (b[i]);writeln(' Введите теперь вектор с, состоящий из ',n,' компонент:');for i:=1 to ndo read (c[i]);m21:=m2-m1+n;nm1:=n+m-m1;n1:=n+m-m1+m2;for i:=1 to mdo for j:=n+1 to n1do a[i,j]:=0;
{переход к равенствам в неравенствах
>=}for i:=m1+1 to m2do a[i,n+i-m1]:=-1;
{переход к равенствам в неравенствах
<=}for i:=m2+1 to mdo a[i,m21+i-m2]:=1;
{создание искуственного базиса}for i:=1 to m2do a[i,nm1+i]:=1;
{ввод mb в вектор с}mb:=12345;for i:=n+1 to nm1do c[i]:=0;for i:=nm1+1 to n1do c[i]:=mb;
{выписать cb}for i:=1 to m2do begin cb[i]:=mb; Bi[i]:=nm1+i end;for i:=m2+1 to mdo begin Bi[i]:=m21+i-m2;cb[i]:=0;end;for i:=1 to n1do x[i]:=0;writeln(' Решение задачи:');
{применяем симплексный метод, вычисляем оценки}
5: for j:=1 to n1do begin s0:=0;for i:=1 to mdo s0:=s0+cb[i]*a[i,j];e[j]:=s0-c[j]end;max:=e[1];j0:=1;for i:=2 to n1do if e[i]
>maxthen begin max:=e[i];j0:=iend;
{получили столбец с максимальной оценкой}if max
<=0then begin for i:=1 to mdo x[Bi[i]]:=b[i];goto 15end;s1:=a[1,j0];for i:=2 to mdo if s1
<=0then goto 10;s1:=mb;for i:=1 to mdo if a[i,j0]
>0then if s1
>b[i]/a[i,j0]then begins1:=b[i]/a[i,j0];i0:=iend;
{главный элемент a[i0,j0]}s0:=a[i0,j0]; Bi[i0]:=j0;for j:=1 to n1do a[i0,j]:=a[i0,j]/s0;b[i0]:=b[i0]/s0;for i:=1 to mdo if i
<
>i0then begin s1:=-a[i,j0];b[i]:=b[i]+b[i0]*s1;for j:=1 to n1do a[i,j]:=a[i,j]+a[i0,j]*s1end;cb[i0]:=c[j0];goto 5;
10: writeln(' Нет оптимального плана, функция неограничена');goto 20;
{просмотр иск. переменных}
15: for i:=nm1+1 to n1do if x[i]
>0then begin writeln(' Пустое множество планов');goto 20end;for i:=1 to ndo writeln(' x[',i,']=',x[i]:7:4);
20:readkeyend.


Содержание


Введение………………………………………………………………………………1
§1. Задача линейного программирования и свойства её решений…………….…4
§2. Графический способ решениязадачи линейного программирования……………………………………….…6
§3. Симплексный метод……………………………………………………………..8
§4. Понятие двойственности……………………………………………………….11
§5. Основные теоремы двойственностии их экономическое содержание………………………………………….……14
§6. Примеры экономических задач………………………………………………..16
§7. Анализ задачи об оптимальном использовании сырья………………………19
§8. Программа и расчеты…………………………………………………………..25


1


2



     Страница: 2 из 2
     <-- предыдущая следующая -->

Перейти на страницу:
скачать реферат | 1 2 

© 2007 ReferatBar.RU - Главная | Карта сайта | Справка