"Симплексный метод в экономических задачах" (стр. 1 )

УДК. 338679/45 ББК 65.9(1)28

Учебное пособие:

"Симплексный метод в экономических задачах", 34 стр. Рецензенты: проф. , проф.

Авторы: , .

Овладение методами математического моделирования, и, в частности, математической статистики и оптимизации сегодня является стандартом подготовки специалиста любого профиля.

Настоящее пособие посвящено освоению теоретических и практических основ одного из наиболее эффективных и широко известных методов оптимального планирования (линейного программирования)_ необходимого  для  понимания  принципов  формирования экономико-математических моделей и решения  их с использованием вычислительной техники, всестороннего анализа  двойственной пары задач и  принятия  оптимального решения.

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

© МИТХТ им. .

СОДЕРЖАНИЕ  стр.

Введение          3

Методические указания         3

Условия задачи         4

1. ГРАФИЧЕСКАЯ  ИНТЕРПРЕТАЦИЯ  СИМПЛЕКСНОГО        

МЕТОДА  5

1.1. .Графическое решение прямой задачи         5

1.2. Графическое решение двойственной задачи          9

_ 2.АЛГЕБРАИЧЕСКАЯ  ИНТЕРПРЕТАЦИЯ  СИМПЛЕКСНОГО

МЕТОДА         13

3. РЕШЕНИЕ  ЗАЛА ЧИ  СИМПЛЕКСНЫМ  МЕТОДОМ

(практическая часть)         19

4. Заключение         28

5. Литература         28

6. Варианты заданий  29

ВВЕДЕНИЕ

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

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

Линейное программирование - это метод оптимизации линейной целевой функции при заданных линейных ограничениях (неравенствах и уравнениях) и неотрицательности переменных. Оно тесно связано с другими математическими методами и широко используется для решения широкого спектра оптимизационных экономических и технико-экономических задач в промышленности, сельском хозяйстве, транспорте, военном деле, медицине, науке и пр. История возникновения и пути развития линейного программирования подробно описаны в литературе [1-11|.

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

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

Симплексным        методом решают различные оптимизационные задачи, в гом числе: выбора оптимальной структуры потребляемого сырья и производственной программы предприятия, календарного планирования, разработки плана развития и территориального размещения новых и действующих производств, оценки и выбора оптимальных инвестиционных (финансовых) проектов, формирования оптимальной структуры портфеля ценных бумаг и множество других экономических и управленческих задач текущего и перспективного характера. Указанные задачи представлены в ряде пособий кафедры ЭиОП.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Каждый студент получает свой  вариант задания (стр. 29 - "Варианты заданий"). Условия настоящего примера соответствуют первому варианту заданий (У1).

Условия задачи.

Исходные параметры задачи  приведены в Таблице 1.

  Таблице 1

Вариант “У1”
bi /Xj	X1	X2
b1=400	a11= 5	a12= 20
b2=450	a21= 10	a22 15
cj	45	80

Как следует из приведенных данных условия задачи максимально упрощены - предприятие выпускает только два вида продукции (Xj, j=1,2) и использует два типа ресурсов (bi, i=1,2). Необходимо определить, какую продукцию и в каком количестве должно выпускать предприятие в планируемом периоде, с тем, чтобы в конце периода получить максимальную прибыль/ Установлены нормы расхода ресурсов (аij) и прибыли (cj) на каждую единицу продукции. При этом за планируемый период предприятие не должно допустить перерасхода ограниченных ресурсов (Ьj).

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

Ниже приводится  решение прямой и двойственной задач графическим и алгебраическим методами с теоретическими пояснениями.

Графический метод является наиболее наглядной и доступной для понимания интерпретацией симплексного метода. Он рнскрьтваег не только его математическую, но и логино-экономическую  сущность.

1. ГРАФИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ СИМПЛЕКСНОГО МЕТОДА

1.1. - Математическая модель прямой задачи  формулируется на основании приведенных выше условий (Таблица1):

установить такие значения переменных (вектор Xj), которые в условиях ограниченных ресурсов:

5*X1 + 20*X2 ≤ 400        

10*X1 + 15*X2 ≤ 450        

и неотрицательных  неременных:

        XI, Х2 ≥0

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

45*X1 + 80*X2 = Р → max 

На Рис.1 приводится методика  решения задачи на плоскости (в пространстве двух измерений в декартовой системе координат (Х1, X2)). По горизонтальной оси откладываются объемы выпуска продукции первого типа (Х1),  но вертикальной - второго типа (X2).

Рис.1

Графическое решение задачи разделяется на две фазы:

1 - определение области допустимых планов (решений),

2 - определение в этой области оптимального плана.

Определение допустимого пространства решений лимитируется условиями неотрицательности переменных. Поэтому оно должно находиться в первом неотрицательном квадранте (Рис.1) в границах, очерченных системой линейных неравенств.

Предельные границы этой области находят построением прямых по уравнениям 5*X1+20*X2=400 и 10*X1|+15*X2=450, соответствующих линейным неравенствам ограничений. Так, прямую 5*X1+20*X2=400 находят по двум точкам (А и В), расположенным на осях координат  Х1 и X2:

при X1=0,  X2=400/20=20, А (0;20)

при X2=0, X1 =400/5 =80, В (80;0)

Полученная прямая А-В (Рис.1) разделяет общее пространство неотрицательного квадранта на две полуплоскости, лежащие по разные от нее стороны.

Все точки, расположенные выше этой прямой, отвечают условиям уравнения  (5*X1+20*Х2>400)  и противоречат условиям задачи.

Поле квадранта, распложенное ниже этой прямой и на ее границе, удовлетворяет первому неравенству-ограничению 5*Х|+20*Х2<400. Оно содержит множество планов, лимитируемых первым ресурсом.

Второму неравенству 10*X1 + 15*X2 ≤ 450 будет удовлетворять область, расположенная ниже прямой 10*X1 + 15*X2=450 и на этой прямой. Ее построение осуществляют (по аналогии с вышеприведенной прямой А-В) по двум точкам (С и D):

при X1=0, X2=450/15=30, C (0;30)

при X2=0, X1 =450/10 =45, D (45;0)

Интервал  допустимых решений,  расположенный  в заштрихованной области многоугольника (0-А - К-D-O) и на его сторонах,  удовлетворяет обоим условиям и фиксируется при  наложении двух указанных областей друг на друга.

В общем случае, область допустимых решений системы линейных неравенств может быть пустой, одной точкой, неограниченной выпуклой областью шит выпуклым многоугольником. В рассматриваемом примере помученная область является выпуклым четырехугодьником О-А-К-D-O).

На второй фазе решения производят определение оптимального плана.

Определение оптимального плана задачи в найденной области бесконечного множества допустимых решений производят постепенно посредством максимизации целевой функции. Для этого будем придавать целевой функции  различные значения. Начнем с нулевого,  Р=0.

Имеем:        

Р = 45*Х1 + 80*X2 = 0

Это  уравнение прямой, проходящей через начало координат (линия уровня) - Рис.1. С экономических позиций это означает такое состояние предприятия, при котором оно не выпускает никакой продукции (Х1= 0 и Х2=0) и не получает прибыли (Р=0).

Если предадим целевой фуекции P определенное числовое значение, то получим уравнение прямой (см. на графике ”целевая й-ия”), соответствующее этому значению.. Так как мы хогим получить максимальную прибыль, будем перемещать целевую функцию вверх (параллельно самой себе). Максимального значения целевая функция  достигнет на верхней границе (заштрихованной) области в точке К с координатами (Х1опт  и. Х2опт) - Рис.1. Эти координаты соответствуют оптимальному выпуску обеих видов продукции. Дальнейшее перемещение (рост) целевой функции недопустимо, так как приведет к ее выходу из допустимых границ.

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

5*X1 + 20*X2 = 400

10*Х1 + 15*Х2 = 450