Контрольная работа по "Экономико-математическое моделирование"

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ 

БАЛТИЙСКИЙ ФЕДЕРАЛЬНЫЙ  УНИВЕРСИТЕТ ИМ. И.КАНТА

 

Экономический факультет

кафедра менеджмента

 

 

 

 

 

 

 

 

 

 

КОНТРОЛЬНАЯ РАБОТА

 

По дисциплине: «Экономико–математические методы В УПРАВЛЕНИИ»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Калининград 2012г.

 

СОДЕРЖАНИЕ

 

Двойственные задачи линейного программирования.	3
2. Задача 3.1	6
3. Задача 7.2	9
4. Задача 10.2	12
Используемая литература	14

 

 

 

 

3. Двойственные задачи линейного программирования.

В связи с развитием техники, ростом промышленного производства и с появлением ЭВМ все большую  роль начали играть задачи отыскания  оптимальных решений в различных  сферах человеческой деятельности. Основным инструментом при решении этих задач  стало математическое моделирование - формальное описание изучаемого явления  и исследование с помощью математического  аппарата.

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

В большинстве случаев первой степенью приближения к реальности является модель, в которой все зависимости  между переменными, характеризующими состояние объекта, предполагаются линейными. Здесь имеется полная аналогия с тем, как весьма важна  и зачастую исчерпывающая информация о поведении произвольной функции  получается на основе изучения ее производной - происходит замена этой функции в  окрестности каждой точки линейной зависимостью. Значительное количество экономических, технических и других процессов достаточно хорошо и полно  описывается линейными моделями.

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

Рассмотрим задачу об использовании  ресурсов (экономико-математическая модель представлена в таблице №1

В приведенной  модели (i = 1,2..... m) обозначает запас ресурса Si, - число едениц ресурса Si, потребляемого при производстве единицы продукции Pj (j =1,2,. n); cj —n прибыль (выручка) от реализации единицы продукции Pj (или цена продукции Pj).

 

Предположим, что некоторая организация решила закупить ресурсы S1,S2,..Sm предприятия и необходимо установить оптимальные цены на эти ресурсы у1, у2,… уm.

Очевидно, что  покупающая организация заинтересована в том, чтобы затраты на все  ресурсы Z в количествах b1, b2,..., bm по ценам соответственно у1, у2,..., уm были минимальны, т.е.

 

 

 

таблица №1

Задача 1	Задача 2
При ограничениях и условии  неотрицательности Составить такой план выпуска  продукции X = (x1,x2, ...xn), при котором прибыль (выручка) от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов.	При ограничениях и условии  неотрицательности Найти такой набор цен (оценок) ресурсов У = (y1, y1… ), при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции

 

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

На изготовление единицы продукции Р1 расходуется а11 единиц ресурса Si, а21 единиц ресурса S2,..., ai1 единиц ресурса Si,..., аmi единиц ресурса Sm по цене соответственно у1, у2,..., yi..., уm. Поэтому для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении единицы продукции Р1 должны быть не менее ее цены с1 т.е.

Аналогично  можно составить ограничения  в виде неравенств по каждому виду продукции Р1 Р2, ...Рn. Экономико-математическая модель и содержательная интерпретация полученной таким образом двойственной задачи 2 приведены в правой части таблицы №1.

 

Рассмотрим  формально две задачи 1 и 2 линейного программирования, представленные в таблице №1.

Обе задачи обладают следующими свойствами:

В одной задаче ищут максимум линейной функции, в другой — минимум.

Каждая из задач задана в стандартной форме, причем в задаче максимизации все  неравенства вида « », а в задаче минимизации - все неравенства вида « »

а в задаче минимизации — все неравенства  вида «>».

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

4. Матрицы  коэффициентов при переменных  в системах ограничений обеих  задач являются транспонированными друг к другу:

 

Для задачи 1 :

 

Для задачи 2 :

Число неравенств в системе ограничений одной  задачи совпадает с числом переменных в другой задаче.

Условия неотрицательности  переменных имеются в обеих задачах.

Две задачи 1 и 2 линейного программирования, обладающие указанными свойствами, называются симметричными взаимно двойственными задачами или просто двойственными задачами.

Исходя из определения, можно предложить следующий  алгоритм составления двойственной задачи:

1. Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду « », а если минимум — к виду « »

Для этого  неравенства, в которых данное требование не выполняется, умножить на  -1.

2. Составить расширенную матрицу задачи А1 в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.
3. Найти матрицу А'1 транспонированную к матрице А1.
4. Сформулировать двойственную задачу на основании полученной матрицы А'1и условия неотрицательности переменных.

 

 

2. Задача 3.1 на тему «двойственные задачи линейного программирования»

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

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

Вид сырья	Нормы расхода сырья на одно изделие, кг		Общее количество сырья, кг
	А	В
I	12	4	300
II	4	4	120
III	3	12	252
Прибыль от реализации одного изделия, ден. ед.	30	40

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

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

Решение:

 

   Экономико-математическая  модель (ЭММ): Пусть произведено  единиц изделий А и единиц изделий В. Тогда имеем следующую систему ограничений:

                 12X₁ + 4X₂  ≤ 300

                   4X₁ + 4X₂ ≤ 120

                   3X₁ + 12X₂ ≤ 252      

                         X₁ ≤ X₂

                 X₁³0, X₂³0

                 

              Z=30X₁+40X₂  -> max

Запишем задачу в каноническом виде:

                 12X₁ + 4X₂  ≤ 300

                   4X₁ + 4X₂ ≤ 120

                   3X₁ + 12X₂ ≤ 252              (1)          

                    X₁ -   X₂  ≤ 0      

                    X₁³0, X₂³0

                 

              Z=30X₁+40X₂  -> max

 

 

 

 

 

  Сведем систему неравенств к виду системы уравнений, введя неотрицательные переменные X₃, X₄, X₅, X₆:

               12X₁ + 4X₂ + X₃ = 300

               4X₁ + 4X₂ + X₄ = 120

                 3X₁ +12X₂ + X₅ = 252

                X₁ - X₂  + X₆ = 0

                 X₁³0, X₂³0, X₃³0, X₄³0, X₅³0, X₆³0

                   Z=30X₁+40X₂ -> max

 

Первая симплексная таблица:

Базис	X1	X2	X3	X4	X5	X6	B
X3	12	4	1	0	0	0	300
X4	4	4	0	1	0	0	120
X5	3	12	0	0	1	0	252
X6	1	-1	0	0	0	1	0
Z	-30	-40	0	0	0	0	0

 

В строке Z есть отрицательные коэффициенты, и в соответствии с критерием оптимальности, мы не достигли точки max. Введем в базис X₂ ( наименьший отрицательный коэффициент в строке Z) вместо X₅ (т.к.min(300:4,120:4,252:12)=252:12). Воспользуемся правилом прямоугольника и составим 2-ю симплексную таблицу:

 

Базис	X1	X2	X3	X4	X5	X6	B
X3	11	0	1	0	-1/3	0	216
X4	3	0	0	1	-1/3	0	36
X2	1/4	1	0	0	1/12	0	21
X6	5/4	0	0	0	1/12	1	21
Z	-20	0	0	0	10/3	0	840

 

В строке Z есть отрицательные коэффициенты, и в соответствии с критерием оптимальности, мы не достигли точки max. Введем в базис X₁ (отрицательный коэффициент в строке Z) вместо X₄ (т.к.min(216:11,36:3,21:(1/4),21:(5/4))= =36:3).Воспользуемся правилом прямоугольника и составим 3-ю симплексную таблицу:

 

Базис	X1	X2	X3	X4	X5	X6	B
X3	0	0	1	-11/3	8/9	0	84
X1	1	0	0	1/3	-1/9	0	12
X2	0	1	0	-1/12	1/9	0	18
X6	0	0	0	-5/12	2/9	1	6
Z	0	0	0	20/3	10/9	0	1080

   В последней строке Z нет отрицательных коэффициентов, и в соответствии с критерием оптимальности, мы достигли точки max.

 

  То есть Z_max достигается при X₁=12, X₂=18 и Z_max=1080.

 

Симметричная двойственная задача линейного программирования (ДЗЛП):

                      

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

                  12y₁+4y₂+3y₃+y₄   ³ 30

                  4y₁+4y₂+12y₃-y₄   ³ 40                 (2)

                    y₁³0,y₂³0,y₃³0,y₄³0

 

Соответствие между переменными, при котором базисным переменным одной задачи отвечают свободные  переменные другой задачи:

 

 

    По основной теореме  двойственности, задача (2) имеет решение и            S_min= =Z_max=1080. С учетом   и второй теоремы двойственности оптимальное решение задачи (2) находится из условия:

 

y₁=0

y₂=20/3

y₃=10/9

y₄=0             

                  

                     12∙ (12y₁+4y₂+3y₃+y₄ - 30) = 0

                      18∙ (4y₁+4y₂+12y₃-y₄ - 40) = 0

                     y₁∙ (12∙12+4∙18-300) = 0                 ó

                     y₂∙ (4∙12+ 4∙18 -120) = 0

                      y₃∙ (3∙12+ 12∙18-252) = 0

                      y₄∙ (12-18-0)=0

 

   Решение можно найти также  на основании правила соответствия  между переменными с учетом  последней симплексной таблицы:  и в последней строке (выделено жирным) имеем: .

  Таким образом,  и S_min= 1080 – решение ДЗЛП.

 

Вывод: Оптимально производить 12 единиц изделий вида А и 18 единиц изделия вида В. Тогда прибыль максимальна и составит Z_max=1080 ден.ед.

 

 

 

 

3. Задача 7.2 на тему «модели динамического программирования»

Планируется деятельность двух отраслей производства на n лет. Начальные ресурсы =10000 у.е. Средства х, вложенные в I отрасль в начале года, дают в конце года прибыль и возвращаются в размере <x; аналогично для II отрасли функция прибыли равна , а возврата - , причем <х. В конце года все возвращенные средства заново перераспределяются между I и II отраслями, новые средства не поступают, прибыль в производство не вкладывается.

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

Необходимо: 1). Построить модель динамического  программирования для этой задачи и  вычислительную схему; 2). Решить задачу при условии, что  =0,6х, =0,5х, =0,7х, =0,8х, n=4.

 

Решение:

 

   Управление – выделение  средств каждой из двух отраслей  в очередном году. Решения принимаются  в начале каждого из 4-х лет.  Вся процедура делится на шаги: номер шага – номер года. Параметры состояния к началу k-ого года - ( ) – количество средств, подлежащих распределению. Переменных управления на каждом шаге две:

  - количество средств, выделенных 1-ой отрасли;

  - количество средств, выделенных 2-ой отрасли.

Так как все  средств распределяется, то , откуда .

Таким образом, управление на k-ом шаге зависит от одной переменной , то есть .

Уравнения состояний  выражают остаток средств, возвращенных в конце k-ого года.

Показатель эффективности  k-ого шага – прибыль, полученная в конце k-ого года от обеих отраслей:  .

Суммарный показатель эффективности  – прибыль за 4 года:

.

Обозначим - условная оптимальная прибыль за лет, начиная с k-ого года 4-ого года включительно, при улови, что имеющиеся на начало k-ого года средства в дальнейшем распределялись оптимально. Тогда оптимальная прибыль за 4 года составит .

Уравнения Беллмана:

 

 

    ( )

 

в нашем случае примут вид:

 

 

    ( )

 

Проведем условную оптимизацию.

 

4 шаг. Функция - линейная, возрастающая и максимум достигается на конце интервала и, следовательно,   при .

 

 

3 шаг: . Так как , то

.

Функция - линейная, возрастающая и максимум достигается на конце интервала и, следовательно,   при .

 

 

2 шаг: . Так как , то

.

Функция - линейная, убывающая и максимум достигается при : при .

 

 

 

 

1 шаг: . Так как , то

.

Функция - линейная, убывающая и максимум достигается при : при .

 

Условная оптимизация  закончена. Получили: .

Распределение средств по годам:

1. .

2. .

3. .

4. .

 

Вывод: Оптимальная прибыль за 4 года, полученная от 2 отраслей составит 15528 у.е. при вложенных 10000  у.е. Распределение средств по годам для 1 отрасли – 0,0,6400,4480, для 2 отрасли – 10000,8000,0,0.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Задача 10.2 на тему «модели управления запасами»

 

Кондитерское  предприятие торгует вразвес  своими тортами. Каждый килограмм торта приносит 2 ден. ед. прибыли. Все торты можно продать на следующий день со скидкой 0,2 ден.ед. На основании опыта получено распределение спроса на торты, представленное в таблице, где r- спрос, а p(r) – статистическая вероятность. Найти оптимальную дневную выработку тортов.

 

r	0	1	2	3	4	5	6
p(r)	0,1	0,2	0,2	0,3	0,1	0,1	0,0

 

 

 

Решение:

 

       В большинстве  задач с запасами участвуют  различные случайные величины: спрос со стороны клиентов, сроки доставки товара поставщиками. В то же время вводятся издержки хранения. Товарам не дают залежаться: их пытаются распродать; наконец такая задача может быть объектом математического рассмотрения лишь тогда, когда определены издержки от нехватки (товарного голода), т. е. объективно - сумма денег, убыток, проистекающий из-за неудовлетворенного спроса (эта оценка часто бывает очень субъективной).

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

 В первом случае средний  запас равен:  .

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

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

Если спрос  , то издержки хранения будут равны:  и к ним добавятся издержки от нехватки: .

Считая, что спрос не ограничен, суммируя по , найдем общие издержки:

                       

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

  В нашем случае издержки  за хранение составляют  ден.ед. – фактически это потери при продаже на следующий день. Издержки от нехватки ден.ед. -  фактически это потерянная прибыль.

Для определения оптимального запаса составим расчетную таблицу:

 

0	0	0,1	-	-	-	0,0	-
1	1	0,2	0,200	0,445	0,2225	0,1	0,3225
2	2	0,2	0,100	0,245	0,3675	0,3	0,6675
3	3	0,3	0,100	0,145	0,3625	0,5	0,8625
4	4	0,1	0,025	0,045	0,1575	0,8	0,9575
5	5	0,1	0,020	0,020	0,0900	0,9	0,9900
≥6	≥6	0	0,000	0,000	0,0000	1,0	1,0000

 

С учетом того, что  , видим, что , так как

, то есть .

 

Вывод: Оптимальная дневная выработка тортов - 3 штуки.

 

 

 

5. Список использованных источников

 

1. Шапкин А.С., Мазаева Н.П. Математические методы и модели исследования операций: Учебник. – 3-е изд. – М.: ИТК «Дашков и К^о», 2006. – 400 с.
2. Замков О.О., Толстопятенко А.В., Черемных  Ю.Н. Математические методы в экономике. - М.: ДИС. 1997.
3. Исследование операций в экономике / Под ред. Н.Ш. Кремера. - М.: Банки и биржи, ЮНИТИ, 1997.
4. Акулич И.А. Математическое программирование в примерах и задачах. – М.:  Высш. школа, 1993. – 336 с.
5. Солодовников А.С. «Введение в линейную алгебру и линейное программирование» Москва, «Просвещение», 1996 г.