По курсу математические методы и модели исследования операций для студентов специальности 080801


НазваниеПо курсу математические методы и модели исследования операций для студентов специальности 080801
страница1/7
Дата публикации19.06.2013
Размер0.92 Mb.
ТипМетодические указания
userdocs.ru > Математика > Методические указания
  1   2   3   4   5   6   7


4072



Министерство образования и науки

российской федерации

федеральное агентство по образованию

Технологический институт

Федерального государственного образовательного учреждения

высшего профессионального образования

«Южный федеральный университет»

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

К ПРАКТИЧЕСКИМ ЗАНЯТИЯМ

ПО КУРСУ



^ МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ

ИССЛЕДОВАНИЯ ОПЕРАЦИЙ


Для студентов специальности 080801





Таганрог 2007



удк 518.5.001.57(07.07)+519.8(07.07)

Составитель Б.Ф. Харчистов

Методические указания к практическим занятиям по курсу «Математические методы и модели исследования операций». – Таганрог: Изд-во Технологического института ЮФУ, 2007. 64 с.



Изложены основные понятия и теоретические положения курса «Математические методы и модели исследования операций», используемые при решении задач. Приведены алгоритмы реализации различных математических методов. Каждый подраздел содержит задачи, снабженные ответами. Предназначены для студентов специальности 080801 «Прикладная информатика в экономике», а также преподавателей, проводящих практические занятия по данному предмету.


Илл. 3. Библиогр.: 6 назв.


Рецензент О.Д. Глод, канд. техн. наук, доцент каф. СА и Т Технологического института ЮФУ.


^ 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (ЛП)




1.1. ФОРМЫ ПРЕДСТАВЛЕНИЯ ЗАДАЧ ЛП
В общем случае задача ЛП записывается следующим образом:

(1.1)

(1.2)

(1.3)

(1.4)

где сj, aij, bi – заданные постоянные величины и rm.

Считается, что все уравнения системы (1.3) являются линейно независимыми, при этом mrn. На практике рассматривается только случай mr<n (случай mr=n – тривиальный, поскольку дает единственное решение для совместной системы уравнений (1.3)).

В случае, когда исходная задача ЛП является задачей минимизации f(x), от нее можно перейти к задаче максимизации (–f(x)), поскольку min f(x) = −max (–f(x)).

В случае, когда исходная задача ЛП содержит ограничения-неравенства вида «≥», от них можно перейти к ограничениям-неравенствам вида «≤», меняя в исходных ограничениях знаки свободных членов и коэффициентов на противоположные. Например, от ограничения



можно перейти к ограничению

.

Общая задача ЛП, в которой все ограничения (кроме условий (1.4) неотрицательности переменных) заданы в виде равенств, т.е.

(1.5)

(1.6)

(1.7)

называется задачей ЛП в канонической форме. В данном случае r=0, s=n и m<n.

Алгоритм приведения общей задачи ЛП к задаче в канонической форме заключается в следующем.

Ограничения-неравенства (1.2) преобразуются в равенства посредством введения дополнительных неотрицательных переменных xn+i, по схеме



Таким образом, при переходе от общей задачи ЛП к задаче в канонической форме получаем m ограничений-равенств с n+r переменными.

Общая задача ЛП, в которой все ограничения заданы в виде нестрогих неравенств, т.е.

(1.8)

(1.9)

(1.10)

называется задачей ЛП в сопряженной канонической форме. В данном случае r=m и s=n.

Алгоритм приведения общей задачи ЛП к задаче в сопряженной канонической форме заключается в следующем:

1. Из переменных xj системы уравнений (1.3) выбирают mr переменных, для которых определитель матрицы коэффициентов отличен от нуля (базисные переменные). Пусть для определенности базисными переменными являются переменные xn-m+r+1xn, тогда переменные x1xn-m+r являются свободными переменными.

2. Из уравнений системы (1.3) базисные переменные выражаются через свободные. Для выбранных в п.1 базисных и свободных переменных получим

(1.11)

3. Из условий неотрицательности базисных переменных



находят ограничения задачи ЛП в виде нестрогих неравенств



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



5. Базисные переменные из соотношений вида (1.11) подставляют в выражение для целевой функции (1.1), в результате получают целевую функцию, зависящую только от свободных переменных. Для выбранных в п.1 базисных и свободных переменных получим



Таким образом, при переходе от общей задачи ЛП к задаче в канонической форме получаем m ограничений-неравенств с nm+r неизвестными.

По рассмотренным алгоритмам можно также переходить от задачи в канонической форме к задаче в сопряженной канонической форме и наоборот.
Задачи
1.1.Записать задачу ЛП

f(x) = −x1+2x2x3+x4  min,

2x1x2x3+x4≤6,

x1+2x2+x3x4≥8,

x1+3x2+5x3−3x4=15,



в канонической форме.

1.2. Записать задачу ЛП

f(x) =−2x1+x2+5x3 max,

2x1+x2+3x3≤6,

x1+x2x3≥5,

2x1x2+x3=4,



в сопряженной канонической форме.

1.3. Записать задачу ЛП

f(x) = x1−3x2x3x4+x5 min,

2x1+x2x3x4=1,

x1+x2+2x3+x4=2,

x1−2x2+x3+x4+x5=1,



в сопряженной канонической форме.
^ 1.2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛП
Графический метод применим для решения задач ЛП в сопряженной канонической форме, если число переменных n=2, т.е. задач вида

f(x) = c1x1+c2x2 max, (1.12)

pi(x) = ai1x1+ai2x2 bi, (1.13)

x1≥0, x2≥0. (1.14)
Каждое из неравенств (1.13) системы ограничений задачи геометрически определяет полуплоскость, лежащую по одну сторону от прямой ai1x1+ai2x2=bi (прямая тоже принадлежит этой плоскости). Если bi0, то ограничение выполняется для точки (x1=0, x2=0), т.е. допустимой является полуплоскость, включающая начало координат; если bi<0, то допустимой является полуплоскость, не включающая начало координат. Для условий (1.14) неотрицательности переменных допустимыми являются полуплоскости над осью абсцисс (x20) и слева от оси ординат (x1≥0). Часть плоскости [x10x2], принадлежащая одновременно всем допустимым полуплоскостям, образует область X допустимых решений (если система ограничений является несовместной, то область X является пустой).

Для нахождения решения задачи ЛП строятся градиент f(x) целевой функции и основная прямая f(x)=0 (вектор f(x) перпендикулярен основной прямой). Основная прямая перемещается в направлении градиента до тех пор, пока она не выйдет на границу области X.

При этом возможен один из следующих случаев:

– прямая f(x)=const и область X допустимых решений имеют одну общую точку (вершину X). Эта точка определяет единственное оптимальное решение;

– прямая f(x)=const и область X допустимых решений имеют множество общих точек (вектор f'(x) перпендикулярен к одной из сторон многоугольника X). Данное множество общих точек представляет собой множество оптимальных решений;

– прямая f(x)=const не выходит на границу области X допустимых решений, сколько бы ее не перемещали (это возможно, если область X неограниченная). При этом целевая функция f(x) оказывается также неограниченной.

Таким образом, алгоритм решения задачи ЛП графическим методом заключается в следующем:

1. Строятся прямые, задаваемые уравнениями ai1x1+ai2x2=bi, , и находят полуплоскости, определяемые каждым из ограничений задачи.

2. Находят область допустимых решений X.

3. Строят градиент f(x)=(c1, c2) и основную прямую f(x)=0.

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

5. Определяют координаты точки максимума x* функции и вычисляют значение целевой функции f* f(x*)в этой точке.
Задачи
1.4. Решить графическим методом задачу ЛП

f(x) = 2x1+3x2 max,

3x1+2x2≤15,

x1+x2≤6,

x2≤4,

x1, x2≥0.

1.5. Решить графическим методом задачу ЛП

f(x)=2x13x2  min,

x1x2≤2,

2x1+x2≤6,

x1, x2≥0.

1.6. Решить графическим методом задачу ЛП

f(x) = −3x1+4x2  min,

x1+2x2≤3,

3x1+3x2≥4,

3x1x2≤2,

x1, x2≥0.
^ 1.3. СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛП
Симплекс-метод требует приведения задачи ЛП к канонической форме, т.е. к виду (1.5)(1.7), причем все bi в (1.6) должны быть неотрицательными, т.е. (если некоторое bi<0, то соответствующее ограничение надо умножить на (−1)). Расчеты симплекс-методом наиболее удобно проводить с помощью симплекс-таблиц.

Для задачи ЛП вида (1.5)(1.7) симплекс-таблица состоит из n+2 столбцов и m+1 строк. В первых m строках симплекс-таблицы записываются коэффициенты уравнений, выражающих базисные переменные через свободные, в (m+1)-й строке (целевой строке) – коэффициенты уравнения , где – целевая функция, зависящая только от свободных переменных. Указанные уравнения преобразованы таким образом, что все переменные содержатся в одной части уравнений, а свободные члены – в другой части.

Так, если базисными являются переменные xn-m+1xn, то уравнения, выражающие базисные переменные через свободные, и целевая функция имеют вид:





При этом «преобразованные уравнения» записываются следующим образом:





где

Для рассматриваемого случая симплекс-таблица имеет вид


Базис

Св. член

x1

∙∙∙

xn-m

xn-m+1

xn-m+2

∙∙∙

xn

xn-m+1

b′1

a′11

∙∙∙

a′1,n-m

1

0

∙∙∙

0

xn-m+2

b′2

a′21

∙∙∙

a′2,n-m

0

1

∙∙∙

0



















∙∙∙

∙∙∙

∙∙∙



















∙∙∙

∙∙∙

∙∙∙







xn

b′m

a′m1



a′m,n-m

0

0

∙∙∙

1

φ

φ0

φ1



φn-m

0

0

∙∙∙

0


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

Для приведенной симплекс-таблицы базис (Б), базисное решение (БР) и значение целевой функции определяются из соотношений

Б = {xn-m+1, xn-m+2, …, xn},

БР = (x1=0, x2=0, …, xn-m=0, xn-m+1=b1, xn-m+2=b2, …, xn=bm),

φ (x1=0, x2=0, …, xn-m=0) = φ0.

Базисное решение, удовлетворяющее условию неотрицательности базисных переменных, называется допустимым базисным решением (ДБР).

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

– среди коэффициентов целевой строки нет отрицательных;

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

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

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

В качестве новой базисной переменной выбирают ту свободную переменную xk, которой соответствует наибольший по абсолютной величине отрицательный коэффициент целевой строки. Столбец, соответствующий вводимой переменной, называется ведущим столбцом (в симплекс-таблице помечается стрелкой: k).

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

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

Симплекс-таблица, соответствующая новому базису, заполняется по следующим правилам:

(1.15)

(1.16)

(1.17)

где l – номер итерации, l = 0,1,…

Таким образом, алгоритм решения задачи ЛП симплекс-методом заключается в следующем:

1. Приводят задачу ЛП к канонической форме, при этом все свободные члены ограничений должны быть неотрицательными (bi≥0, ).

2. Определяют начальный базис, составляют симплекс-таблицу и находят начальное ДБР.

3. Проверяют условие оптимальности полученного ДБР: в целевой строке все коэффициенты, кроме свободного члена, являются неотрицательными.

Если условие выполняется, то ДБР определяет решение x* задачи ЛП, при этом f*f(x*)0.

Если условие не выполняется, то переходят к п. 4.

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

Если условие не выполняется, то задача ЛП неразрешима.

Если условие выполняется, то переходят к п. 5.

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

6. Используя соотношения (1.15)(1.17), составляют симплекс-таблицу, соответствующую новому базису, и находят следующее ДБР. Затем переходят к п. 3.

Вычисления завершают, когда найдено оптимальное решение (п. 3), либо когда задача неразрешима (п. 4).

Определение начальных базиса Б0 и допустимого базисного решения ДБР0 не вызывает трудностей, когда задача ЛП задана в сопряженной канонической форме, т.е. в виде (1.8)(1.10), причем все bi в (1.9) неотрицательны, т.е. bi≥0, . Тогда для решения задачи ЛП симплекс-методом ее следует привести к канонической форме, вводя дополнительные переменные xn+i, . Поскольку определитель Δ матрицы коэффициентов при дополнительных переменных отличен от нуля (Δ=1), то совокупность этих переменных может использоваться в качестве начального базиса Б0, т.е.

Б0 = { xn+1, xn+2, …, xn+m},

при этом

ДБР0 = ( x1=0, x2=0, …, xn=0, xn+1=b1, xn+2=b2, …, xn+m=bm).

Если система ограничений в задаче ЛП при неотрицательных свободных членах представлена неравенствами вида «≥» или равенствами, то начальный базис не может быть найден так просто. В таких случаях для его нахождения может использоваться метод искусственных переменных.

Пусть задача ЛП задана в канонической форме, т.е. в виде (1.5)(1.7), причем все свободные члены в (1.6) неотрицательны. Алгоритм нахождения начального базиса методом искусственных переменных заключается в следующем:

1. В ограничения-равенства (1.6) вводят неотрицательные искусственные переменные zi≥0, , по схеме



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







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

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

Если min F(z)=0, то полученные оптимальные базис и ДБР вспомогательной задачи являются начальными базисом и ДБР исходной задачи.

Если min F(z)>0, то исходная задача не имеет решения.

Следует отметить, что число вводимых в уравнения (1.6) задачи ЛП искусственных переменных может быть и меньше m. Если есть возможность из уравнений (1.6) просто найти s<m базисных переменных из числа «основных» переменных xj, то можно ввести лишь (ms) искусственных переменных zi, При этом начальный базис вспомогательной задачи будет содержать s «основных» переменных xj и (ms) искусственных переменных zi.
  1   2   3   4   5   6   7

Похожие:

По курсу математические методы и модели исследования операций для студентов специальности 080801 iconМетодические указания по проведению практических занятий и выполнению...
Методические указания предназначены для проведения практических занятий и выполнения домашних заданий по дисциплине «Экономико-математические...
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconКлючевые понятия 54 Контрольные вопросы 55
К65 Математические методы исследования операций в экономикеЎєспб: Питер, 2000. ЎЄ 208 с.: ил. ЎЄ (Серия «Краткий курс»)
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconПрограммные вопросы по курсу «Психология» для студентов специальности...
История предмет, структура педагогической психологии ее задачи и методы исследования
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconПлан семинарских занятий
Для студентов 4 курса очного отделения, обучающихся по специальности «математические методы в экономике»
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconМетодические указания к лабораторным работам по курсу рспсит для...
Методические указания к лабораторным работам по курсу рспсит для специальности 080801. 65-Прикладная информатика в экономике
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconДисциплина «Методология и методы психологического исследования» для...
Классификация методов психологического исследования (Классификация Пирьова; Б. Г. Ананьева; М. С. Роговина и Г. В. Залевского; В....
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconСеминар №2 по дисциплине «Методология и методы психологического исследования»...
Проблемная ситуация и проблема исследования. Требования к формулированию проблемы научного исследования
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconРабочая программа дисциплины математические методы в исторических исследованиях
Целью освоения дисциплины Математические методы в исторических исследованиях является формирование целостного, системного представления...
По курсу математические методы и модели исследования операций для студентов специальности 080801 icon1. Понятие о науке а/х и методы исследования, которыми она располагает
Математические методы используют для проверки точности опытов и установлении достоверности полученных результатов. Выявления кариляционных...
По курсу математические методы и модели исследования операций для студентов специальности 080801 iconПрограмма междисциплинарного экзамена по специальности 080801. 65...
Охватывает вопросы ряда специальных дисциплин, предусмотренных учебным планом вэпи по данной специальности и позволяет оценить качество...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2015
контакты
userdocs.ru
Главная страница