Экономико математические методы моделирования

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

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

 

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

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

 

 

 

 

 

 

 

 

 

 

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

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Калининград 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