Задача оптимального использования ресурсов icon

Задача оптимального использования ресурсов




Скачати 212.82 Kb.
НазваЗадача оптимального использования ресурсов
Дата05.07.2013
Розмір212.82 Kb.
ТипЗадача

Задача1 (задача оптимального использования ресурсов)

Составить экономическую модель задачи оптимального использования ресурсов (4 вида ресурсов, 2 вида продукции).

Составить математическую модель задачи оптимального использования ресурсов.

Решить задачу геометрически и сделать экономические выводы.

Решить задачу симплекс-методом. Сравнить полученные результаты с геометрическим решением.

Составить экономическую и математическую модели двойственной задачи.

Найти решение двойственной задачи, используя решение исходной задачи.

Установить конкретное экономическое содержание двойственных оценок данной задачи.

Охарактеризовать изменение прибыли предприятия при изменении запасов соответствующих ресурсов на 1 единицу?

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


1.


Виды

сырья

Запасы

сырья

Расход сырья на единицу продукции

p1

p2

С1

3

2

1

С2

6

2

3

С3

9

0

2

С4

6

2

0

Доход от реализации единицы продукции (P)

15

30

В соответствии с данными таблицы необходимо так организовать выпуск продукции П1 и П2, чтобы общая прибыль от реализации продукции была максимальной.


2. Пусть x1 и x2 – количество единиц продукции p1 и p2 соответственно. Тогда в соответствии с условием задачи получаем :

F=15 +30 →max (1)

(2)

Здесь функция F выражает прибыль от реализации продукции П1 и П2, ограничения-неравенства (2) вытекают из экономического содержания задачи оптимального использования сырья.

3. В плоскости Оx1x2 изобразим область допустимых значений неизвестных (план). Каждое из неравенств (2) представляет собой на плоскости Оx1x2 полуплоскость. Чтобы выяснить, какая из двух возможных полуплоскостей, которые возникают при проведении соответствующей прямой, удовлетворяет заданному неравенству, достаточно подставить в это неравенство точку . Очевидно, точка О(0, 0) удовлетворяет первым четырем неравенствам (2) и, следовательно, принадлежит соответствующим полуплоскостям. Полуплоскости, описываемые неравенствами и лежат правее оси x2 и выше оси x1 соответственно.

Искомый план заштрихован на рисунке.

http://www4a.wolframalpha.com/calculate/msp/msp166711a4aia5ahafic4h4000011ai216e89bgdcah?mspstoretype=image/gif&s=60&w=400&h=36



Известно, что максимальное значение функции ^ F достигается на границе области, а точнее в одной из вершин четырёхугольника ОАВСD. Чтобы найти оптимальную вершину, проведем прямую F=0 (15+30. Возрастание функции F будет происходить в направлении вектора , перпендикулярного прямой F=0. Из рисунка видно, что в точке О достигается минимальное значение функции F (это соответствует началу производства, здесь ). Двигаясь в направлении вектора , убеждаемся, что крайней точкой заштрихованной области есть точка ^ С. Следовательно, .

Найдем координаты точки С, которая является пересечением прямых (I) и (II). Решаем систему уравнений



Значение функции F в точке С равно

.

Экономические выводы из геометрического решения.

Максимальная прибыль, равная 56.25 усл. ед., достигается при производстве 0.75 ед. продукции p1 и 1.5 ед. продукции p2. При этом сырье 1-го и 2-го видов будет израсходовано полностью, а сырье 3-го и 4-го видов – не полностью. Остаток сырья 3-го вида составит 9-ед., а остаток сырья 4-го вида будет ед.

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


4. Для решения задачи симплекс-методом запишем первые четыре ограничения-неравенства (1.2) в виде ограничений-равенств путем добавления новых неотрицательных переменных , . В результате получаем следующую задачу линейного программирования: найти максимальное значение переменной F при неотрицательных значениях других переменных, если все переменные удовлетворяют системе линейных уравнений



В качестве первоначального опорного плана выберем



Здесь переменные x3, x4, x5, x6 являются базисными, переменные x1, x2 – свободными (на опорном плане свободные переменные равны нулю).

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



Выбран ключевой элемент (2,2)





Поскольку в последней строке нет отрицательных оценок, то ^ Х1– оптимальный план.

.

Необходимо изготовить 2 ед. продукции p2. При этом сырье 2-го вида израсходуется полностью (х4=0). Неизрасходованными остаются 1 ед. сырья 1-го вида (х3=1) , 5 ед. сырья 3-го вида (х5=5) и 6 ед. сырья 4-ого вида (х6=6).


5. Предположим, что некоторая фирма хочет купить сырье С1, С2, С3, С4 у предприятия, готового выпускать продукцию П1 и П2. Как должны вести себя обе стороны?

Заинтересовать покупателя: общая стоимость сырья должна быть как можно меньше.

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

Пусть y1, y2, y3, y4 – стоимости единицы сырья С1, С2, С3, С4 соответственно. Тогда в соответствии с условием задачи оптимального использования сырья и интересами обеих сторон, приходим к следующей задаче линейного программирования:

(3)

(4)


Задача (3) - (4) называется двойственной к исходной задаче (1)-(2).

Если одна из двойственных задач имеет оптимальное решение, то и другая также имеет оптимальное решение, причем .


6. Запишем первые два ограничения-неравенства (4) двойственной задачи в виде ограничений-равенств путем вычитания новых неотрицательных переменных у5 и у6 соответственно. Тогда двойственная задача приобретает вид



Между переменными прямой и двойственной задач установим следующее соответствие:




Тогда оптимальное решение двойственной задачи можно получить из последней симплекс-таблицы прямой задачи. Оно записано в последней строке этой таблицы. Имеем:

На оптимальном плане Yопт двойственной задачи



Как видим, оценивается только сырье 2-го вида, сырье 1-го, 3-го и 4-го видов отдаются покупателю бесплатно.


7. Значения на оптимальном плане Yопт обозначают двойственные оценки сырья С1, C2, С3 и С4 соответственно. y2*0, сырье С2 полностью иcпользуются при оптимальном плане производства. y1*=0 , y3*=0 и y4*=0, сырье С1, С3 и С4 не полностью иcпользуются при оптимальном плане производства.

Таким образом, положительную двойственную оценку имеют лишь те виды сырья, которые полностью используются при оптимальном плане производства. Чтобы удовлетворить интересы и продавца и покупателя фактически продаются лишь те виды сырья, которые имеют положительные двойственные оценки при оптимальном плане производства; сырье с нулевой двойственной оценкой как бы отдается даром.

8. Базисные переменные y2 и y3 двойственной задачи, соответствующие оптимальному плану Yопт , можно выразить через свободные переменные y3, y4, y5 и y6, исходя из последней симплекс-табл. прямой задачи.



Учитываем, что y2*=10 и y5*=5 - стоимости единиц сырья С2 и С соответственно на оптимальном плане Yопт (1.9). Тогда:

Увеличение количества сырья С2 на 1 единицу приведет к тому, что появится возможность найти новый оптимальный план производства, при котором



При этом из выражения для у2 можно сделать вывод, что указанное увеличение общего дохода может быть достигнуто за счет увеличения выпуска p1 на 1/2 ед. и прекращение выпуска p2. Вследствие этого затраты сырья С1 уменьшатся на 1 ед. и затраты сырья С4 уменьшатся на 1 ед.

При увеличении количества сырья С3 прибыль останется неизменной


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

Достаточно установить, при каких условиях оптимальному плану исходной задачи отвечали бы одни и те же базисные переменные при незначительном изменении запасов ресурсов (правых частей ограничений-неравенств исходной задачи).

Пусть – оптимальный план исходной задачи, b- столбец правых частей, P - матрица, составленная из первоначальных компонент векторов базиса, которые определяют оптимальный план.

Нетрудно проверить справедливость соотношения P=^ B, имеющего место в общем случае. Отсюда находим = Р-1b.

Обратная матрица Р-1 может быть записана непосредственно на основании данных последней симплекс-таблицы. Элементы обратной матрицы Р-1 находятся в столбцах табл.1.5, отвечающим переменным х2, х3, х5, х6. Имеем


P =

1 1 0 0

3 0 0 0

2 0 1 0

0 0 0 1


InversP =

0 0.3333 0 0

1.0000 -0.3333 0 0

0 -0.6667 1.0000 0

0 0 0 1.0000


B =

3

6

9

6


X =

2

1

5

6



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

В+В=

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

, (5)

где у1*, у2*, у3*, у4* -двойственные оценки при оптимальном плане (они сохраняют свои значения). Поскольку из экономического содержания задачи об использовании ресурсов следует Неотрицательность переменных, то новые оптимальные планы при изменении запасов ресурсов должны удовлетворять условию неотрицательности (В+В)0

или в развернутом виде

0

Последнее матричное неравенство запишем в виде системы неравенств

(6)

Таким образом, изменяя запасы ресурсов в соответствии с системой ограничений-неравенств (6) , можно сохранять значения двойственных оценок у1*, у2*, у3*, у4* при оптимальных планах неизменными и рассчитывать изменение максимальной прибыли, не решая новую задачу линейного программирования, воспользовавшись формулой (5).

Например, изменяя запасы сырья по правилу



мы удовлетворяем системе неравенств (6). Изменение максимальной прибыли в соответствии с (5) равно

,

т.е. если запасы сырья С1, С2, С3, С4 составляют 4, 7, 8 и 6 единиц соответственно, то максимальная прибыль от реализации произведенной продукции составит 70 усл. ед.


Задача 3 (закрытая транспортная задача)

  1. Составить экономическую модель закрытой транс-портной задачи (3 поставщика, 5 потребителей).

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

  3. Методом наименьшей стоимости построить первоначальный опорный план и вычислить соответствующее ему значение общей стоимости перевозок.

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

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

  6. Если первоначальный опорный план не является оптимальным, то осуществить переход от одного опорного плана транспортной задачи к другому? Найти оптимальный план данной транспортной задачи.

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



1. Пусть на трёх базах сосредоточен однородный груз в количествах a1=170, a2=190, a3=250, который нужно перевезти в пять пунктов назначения в количествах b1=90, b2=30, b3=110, b4=70, b5=310. Известны стоимости доставок единицы товара с пунктов отправления в пункты назначения, которые задаются матрицей стоимостей перевозок

.

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

2. Обозначим xij – количество единиц товара, что перевозится с пункта отправки Ai в пункт доставки Bj. Если известна стоимость cij перевозки единицы товара из пункта Ai в пункт Bj, то стоимость перевозки количества xij из Ai в Bj, очевидно, равна cijxij, так что общая стоимость перевозок определяется как сумма всех возможных произведений этого вида. Следовательно, целевая функция



Система ограничений на переменные xij вытекает из условий полного вывоза товара из пунктов Ai и полного удовлетворения потребностей пунктов Bj, то есть имеем две группы ограничений:

(7)

(8)

Считаем, что перевозка товара из пунктов Bj в пункты Ai не допускается, тогда естественно допустить, что все переменные

Обратим внимание на тот важный факт, что согласно условию задачи сумма всего вывезенного товара из пунктов Ai равна сумме всех поставок в пункты Bj (170+190+250=
=90+30+70+110+310=610) то есть .








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

Следуя методу наименьшей стоимости, приходим к опорному плану

Поставщики

Потребители

Запасы

В1

В2

В3

В4

В5




А1

90 12

18

25

30

80 19

170

А2

26

30 15

27

110 10

50 40

190

А3

45

38

70 17

46

180 23

200

Потребности

90

30

70

110

310

610



Имеем, 3+5-1=7 уравнений, следовательно, фиктивная поставка не нужна.

Подсчитаем функцию затрат:

F=12*90+19*80+15*30+10*110+40*50+17*70+23*180=11480

Решим методом потенциалов.

Система уравнений для неизвестных потенциалов содержит 7 уравнений с 8 неизвестными. Одному из потенциалов можно придавать произвольное значение. Обычно задают u1=0 и затем однозначно определяют остальные потенциалы (ранг системы уравнений здесь равен 7 - рангу системы уравнений транспортной задачи).

Система уравнений для потенциалов

Возьмём: =0. Тогда: =21,=4, =-12,=--6,=-13,= -11,=19

Составим матрицу d (d=)

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (2;1): 26
Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».



Поставщики

Потребители

Запасы

В1

В2

В3

В4

В5




А1

90 12

-

18

25

30

80 19

+

170

А2

26

+

30 15

27

110 10

50 40
-


190

А3

45

38

70 17

46

180 23

200

Потребности

90

30

70

110

310

610



Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 5) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Поставщики

Потребители

Запасы

В1

В2

В3

В4

В5




А1

0 12

18

25

30

130 19

130

А2

80 26

10 15

27

80 10

10 40

180

А3

45

38

160 17

46

40 23

200

Потребности

80

10

160

80

180

510



F=19*130+26*80+150+800+400+17*160+23*40=9540.


Возьмём =0. Тогда: =19, =40,=23, =-14,=-25,=-6,=-30


d=

В матрице d есть отрицательные значения,значит, этот план не является оптимальным. Поэтому сделаем перераспределение поставок.


Поставщики

Потребители

Запасы

В1

В2

В3

В4

В5




А1

12

18

25

30

130 19

130

А2

80 26

10 15

10 27

80 10

0 40

180

А3

45

38

150 17

46

50 23

200

Потребности

80

10

160

80

180

510



F=19*130+26*80+150+270+800+17*150+23*50=9470

Возьмём =0. Тогда: =19, =33,=23, =-7,=-18,=-6,=-23

d=

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.
Минимальные затраты составят:
F(x) = 12*40 + 19*130 + 26*50 + 15*30 + 10*110 + 17*70 + 23*180 = 11130


4. Следуя теории двойственности, поставим в соответствие каждому из трёх уравнений (7) переменную αi (i=1, 2, 3), а каждому из пяти уравнений (8) переменную βj (j=1, 2, 3, 4, 5). Переменную αi называют потенциалом пункта Аi, а переменную βj- потенциалом пункта Вj.

Поскольку все основные ограничения транспортной задачи (7) и (8) есть ограничения-равенства, то потенциалы αi и βj могут принимать любые значения (они могут быть положительными, отрицательными или равными нулю). Каждой переменной транспортной задачи должно соответствовать одно ограничение – неравенство двойственной задачи


,


так как переменная xij входит лишь один раз в подсистему (7) и один раз в подсистему (8)

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

.



, , ,

, , ,

, , ,

, , ,

, , .

Здесь на переменные αi и βj не накладываются ограничения на знак.


5. Оптимальный план транспортной задачи находится среди её опорных планов.

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



для базисных клеток и условиям

(9)

для свободных клеток. Здесь величину называют кос-венным тарифом, а величину -истинным тарифом клетки (i,j).


Поставщики

Потребители

Запасы

αi

В1

В2

В3

В4

В5

А1

12

18

25

30

130 19

130

α1=-4

А2

80 26

10 15

10 27

80 10

0 40

180

α2=10

А3

45

38

150 17

46

50 23

200

α3=0

Потребности

80

10

160

80

180

510




βj

β1=16

β2=5

β3=17

β4=0

β5=23





Cравним косвенные и истинные тарифы свободных клеток, то есть проверим справедливость неравенств (9) для незаполненных клеток. Сравнение косвенных и истинных тарифов свободных клеток табл. показывает, что условию оптимальности (9) удовлетворяют все клетки. Таким образом, опорный план Х3 является оптимальным.

F(x) = 12*40 + 19*130 + 26*50 + 15*30 + 10*110 + 17*70 + 23*180 = 11130

7. Минимальная стоимость перевозок, равная 9470 усл. ед., обеспечивается при следующих перевозках:


, , , , , , .


При таких перевозках весь товар будет вывезен из пунктов отправки (а1=130, а2=80+10+10+80=180, а3=150 +50 =200) и все потребности пунктов назначения будут удовлетворены (b1=80, b2= 10, b3=10+150=160, b4=80, b5=50+130=180).



Схожі:

Задача оптимального использования ресурсов iconЗадача оптимального использования ресурсов
Составить экономическую модель задачи оптимального использования ресурсов (4 вида ресурсов, 2 вида продукции)
Задача оптимального использования ресурсов iconЗадача оптимального использования ресурсов
Составить экономическую модель задачи оптимального использования ресурсов (4 вида ресурсов, 2 вида продукции)
Задача оптимального использования ресурсов iconЗадача оптимального использования ресурсов
Составить экономическую модель задачи оптимального использования ресурсов (4 вида ресурсов, 2 вида продукции)
Задача оптимального использования ресурсов iconШавурская Е. В., аспирант Житомирский государственный технологический университет бухгалтерский учет недревесных лесных активов: состояние и перспективы
Одним из условий сохранения и рационального использования лесных ресурсов является формирование системы учетно-аналитического обеспечения...
Задача оптимального использования ресурсов iconЛекция 7 Тема особенности возобновимых ресурсов и моделирования их эффективного использования
Наиболее важным моментом в классификации природных ресурсов является то, насколько текущий уровень потребления этого ресурса влияет...
Задача оптимального использования ресурсов iconФедчак О. М. Фінансове забезпечення раціонального використання та охорони природних ресурсів в Україні
Ресурсов Украины. Исследованы особенности формирования организационно-финансового механизма регулирования природопользования и природоохранной...
Задача оптимального использования ресурсов iconФедчак О. М. Фінансове забезпечення раціонального використання та охорони природних ресурсів в Україні
Ресурсов Украины. Исследованы особенности формирования организационно-финансового механизма регулирования природопользования и природоохранной...
Задача оптимального использования ресурсов iconВ посттрансформационной экономике
Институциональное регулирование формирования и использования финансовых ресурсов государства
Задача оптимального использования ресурсов iconПерелік публікацій кафедри «Економіка підприємства» за 2007 рік
Инновационная модель обеспечения эффективного использования региональных ресурсов
Задача оптимального использования ресурсов iconПерелік публікацій кафедри «Економіка підприємства» за 2007 рік
Инновационная модель обеспечения эффективного использования региональных ресурсов
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи