Математика (3 сем-р) (стр. 1 )

МАТЕМАТИКА (3 сем-р)

Литература

1.  Исследование операций в экономике/Под ред. . ЮНИТИ, 1997

2.  Эддоус, Стэнсфилд. Методы принятия решений.-М.: Аудит, ЮНИТИ, 1997

3.  и др. Курс высшей математики для экономических вузов. Ч II. Математическое программирование.-М.:Высш. шк.,1982

4.  Акулич программирование в примерах и задачах.-М.:Высш. шк.,1982, 1990

5.  , , Волощенко программирование.-М.:Высш. шк.,1980

6.  и др. Высшая математика. Математическое программирование. Мн.:Вышэйш. шк., 1994

7.  Вентцель операций. М.:Радио и связь, 1972

8.  Калихман задач по математическому программированию. М.:Высш. шк.,1975

9.  Фомин методы и модели в коммерческой деятельности. М.: Финансы и статистика, 2001.

Введение

Вопрос 1. Предмет математического программирования

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

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

Формулировка экономико-математической задачи заключается в построении экономико-математической модели (ЭММ), т. е. в математическом описании реального экономического процесса или объекта.

ЭММ включает в себя:

а) формирование целевой функции (показателя эффективности или критерия оптимальности), то есть функции, экстремальное значение которой нужно найти в пределах экономических возможностей;

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

В.2. Запись задачи математического программирования

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

(1)

и удовлетворяющий системе ограничений

	(2)
	(3)

(последние неравенства вытекают из экономических или физических соображений)

Здесь для любого i -известные заданные функции, - области допустимых решений (или экономических возможностей), bi =const

План, удовлетворяющий системе ограничений задачи, называется допустимым ()

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

Экстремальное значение функции цели обозначается

В.3. Классификация методов математического программирования

Даётся в зависимости от вида функций (1) и (2):

·  линейное программирование (ЛП): все функции (1) и (2) линейны относительно неизвестных xj , j=1,…,n;

·  нелинейное программирование: целевая функция (1) или хотя бы одна из функций (2) нелинейна;

·  дискретное программирование: на переменные xj наложено условие дискретности; частным случаем дискретного программирования является целочисленное программирование, в котором переменные принимают только целые значения;

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

·  стохастическое программирование: переменные xj, (j=1,2,…,n) сами являются функциями или случайными величинами, например, в задачах принятия решений в конфликтных ситуациях, в условиях неполной или недостоверной информации, в условиях риска.

Тема 1. Линейное программирование (ЛП)

В.1. Примеры задач линейного программирования (ЗЛП)

1.1. Задача об использовании ресурсов (о планировании производства)

Пример 1. Для производства двух видов продукции Р1 и Р2 предприятие использует 4 вида ресурсов S1, S2, S3, S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, заданы в таблице:

Вид ресурса	Запас ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
Р1	Р2
S1	18	1	3
S2	16	2	1
S3	5	-	1
S4	21	3	-
Прибыль от продажи единицы ресурса	2 у. е.	3 у. е.

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

Общая постановка:

-  предприятие выпускает n различных видов продукции Р1, Р2, …, Рn ;

-  оно располагает для этого m видами ресурсов S1, S2,…, Sm. (например, рабочая сила, площади, сырьё, энергия и пр.);

-  запасы ресурсов ограничены и составляют условных единиц;

-  цена реализации j-го продукта равна , то есть задан вектор цен ;

-  aij - технологические коэффициенты: сколько единиц i- го ресурса расходуется для производства единицы j- го вида продукции.

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

Составим ЭММ данной задачи:

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

(1)

Теперь составим баланс расхода по каждому ресурсу. Скажем, расход i- го ресурса складывается из затрат на производство 1-го изделия, то есть ai1x1, расхода на производство 2-го изделия ai2x2,…, расхода на производство n-го изделия ainxn. С другой стороны, этот суммарный расход не может превысить общего количества этого ресурса, то есть bi. Таким образом, запишем аналогичные ограничения для каждого из ресурсов, получим систему неравенств:

(2)

Чтобы план был реален, он должен состоять из неотрицательных компонент:

(3)

Математическая формулировка: Найти план , удовлетворяющий системе (2) и условию (3), при котором функция (1) принимает максимальное значение.

Запишем ЗЛП об использовании ресурсов в компактном виде: найти

(1’)

; (2’)

(3’).

1.2. Задача о диете (о составлении кормового рациона,

о приготовлении различных смесей)

Пример 2. Имеется 2 вида корма I и II, содержащие питательные вещества (витамины) S1, S2, S3.

Содержание числа единиц питательных веществ в 1 кг корма и необходимый минимум питательных веществ в день приведены в таблице:

Витамин	Необходимый минимум витамина	Число единиц витаминов в 1 кг корма
I	II
S1	9	3	1
S2	8	1	2
S3	12	1	6
Стоимость 1 кг корма	4 у. е.	6 у. е.

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

Общая постановка:

получить кормовой рацион с заданными свойствами (содержанием питательных веществ) при наименьших затратах на исходные сырьевые материалы.

Дано:

-  n видов исходных продуктов (сено, силос и пр. для животноводства);

-  они содержат m видов питательных веществ (белки, жиры, углеводы, соли и т. д);

-  xj количества кормов j-го вида ;

-  для жизнедеятельности надо потреблять не менее bi единиц i-го питательного вещества;

-  cj – стоимость единицы исходного продукта j – го вида;

-  aij – содержание i-го питательного вещества в единице j-го вида корма.

Составим ЭММ задачи. Суммарная стоимость всего набора кормосмесей равна . Эта стоимость должна быть минимальной, то есть целевая функция задачи выглядит так:

(4)

Теперь составим баланс по каждому питательному веществу в кормовом рационе. Содержание i-го питательного вещества в кормосмеси первого вида равно ai1x1, в кормосмеси второго вида равно ai2x2,…, в кормосмеси n-го вида равно ainxn. Общее количество i-го питательного вещества должно быть не меньше, чем bi. Это задаёт вид неравенства, и в результате запишем систему ограничений для всех питательных веществ:

(5)

Эти ограничения, как обычно, дополняются тривиальными ограничениями из физических соображений (поскольку нельзя произвести кормосмеси в отрицательных количествах!):

(6)

В компактном виде:

(4’)

; (5’)

(6’).

1.3. Задача о загрузке оборудования (об использовании мощностей)

Общая постановка:

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

Требуется за время Т выпустить n1, n2, … , nk единиц продукции Р1, Р2, …, Рk. Продукция производится на станках S1, S2,…, Sm.

Для каждого станка известны производительность aij – число единиц продукции Рj, которое можно произвести на станке Si в единицу времени, и затраты bij на изготовление продукции Рj на станке Si в единицу времени.

Необходимо составить такой план работы станков (т. е. распределить выпуск продукции между станками), при котором затраты на производство всей продукции были бы минимальными.

Составим ЭММ.

Пусть – время, в течение которого станок Si занят изготовлением продукции Рj .

Тогда суммарные затраты на производство всей продукции составят

(7)

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

(8)

Продукции Рj станок S1 может произвести в количестве , станок S2 –, …, станок Sm –. Т. о. для выполнения плана по номенклатуре необходимо, чтобы выполнялись равенства:

(9)

Кроме того

, ,. (10)

В.2. Основная задача линейного программирования (ЗЛП)

Формулировка ЗЛП:

найти вектор переменных (план Х), который удовлетворяет системе линейных ограничений (уравнений и неравенств) (12)-(13) и обеспечивает экстремальное (максимальное или минимальное) значение линейной целевой функции (11).

Общая форма записи ЗЛП в компактном виде:

(11) – требование оптимизации;

(12) –нетривиальная система ограничений;

(13) – тривиальные неравенства

(могут все отсутствовать).

Задача (11)-(13) называется основной задачей линейного программирования. Коэффициенты - заданные действительные числа. Кроме того, в модель могут быть введены и другие ограничения.

Замечания.

1.  Есть экономические задачи, в которых ограничения состоят только из строгих неравенств (например, закрытая модель транспортной задачи).

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

В. 3. Формы записи ЗЛП.

Взаимосвязь однородной и канонической форм записи

А) Симметричная или стандартная форма записи ЗЛП. Она состоит в определении максимального значения функции (11) при выполнении условий (12) и (13) общей ЗЛП, где k=m и t=n. (Т. е. система нетривиальных ограничений состоит только из неравенств и все переменные неотрицательны).

;

.

Б) Каноническая форма записи ЗЛП: это задача на максимум ,

все нетривиальные ограничения заданы в виде уравнений

а тривиальные ограничения распространяются на все переменные

В) Матричная форма. Введём обозначения:

матрица системы ограничений;

вектор-строка коэффициентов целевой функции;

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

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

Запишем каноническую форму в матричном виде:

Г) Векторная форма. Рассмотрим только одну из векторных форм. Обозначим

, .

Задача принимает вид:

(здесь скалярное произведение векторов)

Д) Однородная форма. Однородной называется такая модель ЗЛП, в которой все ограничения (нетривиальные и тривиальные) заданы в виде неравенств:

Эта форма удобна при графическом методе решения ЗЛП. Обратите внимание, что здесь переменные не обязательно неотрицательны.

Любая общая ЗЛП может быть с помощью эквивалентных преобразований приведена сначала к однородной, а затем к канонической форме. Рассмотрим этот процесс более подробно.

Перевод общей ЗЛП в однородную форму. Основным отличием общей формы от однородной является наличие в составе ограничений некоторого количества уравнений; каждое такое уравнение

эквивалентно системе из двух нестрогих неравенств

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

1.  Если задана задача на минимум (), то, умножив целевую функцию на (-1), получим задачу на (). Причём .

2.  В каждое исходное неравенство типа «меньше или равно» вводится новая неотрицательная балансовая (дополнительная) переменная со знаком «+», и неравенство записывается как уравнение. Т. е. неравенство эквивалентно системе из уравнения и тривиального неравенства:

(xn+1 – балансовая переменная)

3.  В каждое неравенство типа «больше или равно» вводится балансовая неотрицательная переменная со знаком «-»:

, (xn+2 – балансовая переменная)

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

4.  Если на какую-нибудь переменную не наложено условие неотрицательности, её можно представить как разность двух неотрицательных переменных:

5.  Дополнительные балансовые переменные вводятся в целевую функцию с коэффициентами, равными нулю:

Следующие примеры дают представление о реализации указанных преобразований.

Задача планирования производства в канонической форме

Задача о смесях в канонической форме

Пример 3. Привести ЗЛП к канонической форме:

Обратите внимание, что переменная x3 может принимать произвольные значения.

Решение. Поскольку на переменную x3 не наложено условие неотрицательности, заменим её разностью двух неотрицательных переменных . Для удобства, чтобы не было штрихов, переобозначим эти переменные соответственно . Введём балансовые переменные Подставим новые переменные в выражение для целевой функции и в нетривиальные ограничения задачи, дополнив при этом тривиальные ограничения новыми переменными, получим:

В.4. Методы решения ЗЛП

4.1. Геометрический (графический) метод решения ЗЛП

Графический метод используется, с одной стороны, для обобщения на алгебраический метод с произвольным количеством переменных, с другой стороны, для наглядного представления решения ЗЛП с двумя переменными. При наличии только двух переменных область допустимых решений (ОДР) может быть легко изображена на плоскости .

Рассмотрим ЗЛП с двумя переменными в однородной форме записи:

	(1)
	(2)
	(3)

Геометрический метод основывается на двух основных утверждениях:

1.  Область допустимых решений (ОДР) системы ограничений ЗЛП представляет собой выпуклый многоугольник (многогранник) (Множество точек называется выпуклым, если отрезок, соединяющий любые две точки этого множества, также принадлежит данному множеству).

2.  Оптимальное решение ЗЛП, если оно существует, обязательно находится, по крайней мере, в одной из угловых точек ОДР.

Решение ЗЛП геометрическим методом можно разбить на следующие основные этапы:

I этап. Построить ОДР.

Для этого необходимо найти решение каждого из неравенств системы ограничений.

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

Для того чтобы определить, какая из полуплоскостей является решением неравенства, рекомендуется взять контрольную точку, не принадлежащую данной прямой, и подставить её в неравенство. Если неравенство выполняется в выбранной точке, то решением служит та полуплоскость, которая содержит данную точку (если не выполняется – то другая полуплоскость).