.RU

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



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+2x2−x3+x4  min,
2x1−x2−x3+x4≤6,
x1+2x2+x3−x4≥8,
x1+3x2+5x3−3x4=15,

в канонической форме.
1.2. Записать задачу ЛП
f(x) =−2x1+x2+5x3 max,
2x1+x2+3x3≤6,
x1+x2−x3≥5,
2x1−x2+x3=4,

в сопряженной канонической форме.
1.3. Записать задачу ЛП
f(x) = x1−3x2−x3−x4+x5 min,
2x1+x2−x3−x4=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,
x1−x2≤2,
2x1+x2≤6,
x1, x2≥0.
1.6. Решить графическим методом задачу ЛП
f(x) = −3x1+4x2  min,
x1+2x2≤3,
3x1+3x2≥4,
3x1−x2≤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. 2010-07-19 18:44 Читать похожую статью
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • © Помощь студентам
    Образовательные документы для студентов.