Преобразование неравенств в равенства

Вопросы по дисциплине «Математические модели информационных процессов управления» 2009-2010 учебный год

1. Моделирование, виды моделирования.

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

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

Моделирование - создание, применение, использование модели.

Главные функции модели - упрощение получения информации о свойствах объекта; передача информации и знаний; управление и оптимизация объектами и процессами; прогнозирование; диагностика.

1.1 Виды моделирования

В силу многозначности понятия «модель» в науке и технике не существует единой классификации видов моделирования: классификацию можно проводить по характеру моделей, по характеру моделируемых объектов, по сферам приложения моделирования (в технике, физических науках, кибернетике и т. д.). Например, можно выделить следующие виды моделирования:

· Информационное моделирование

· Компьютерное моделирование

· Математическое моделирование

· Математико-картографическое моделирование

· Молекулярное моделирование

· Цифровое моделирование

· Логическое моделирование

· Педагогическое моделирование

· Психологическое моделирование

· Статистическое моделирование

· Структурное моделирование

· Физическое моделирование

· Экономико-математическое моделирование

· Имитационное моделирование

· Эволюционное моделирование

· Историческое моделирование

· Нечеткое моделирование

· Модельное моделирование

· и т. д.

2. Графическое решение задачи линейного программирования.

I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.

II. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи (1.2). Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.

Если неравенство истинное,

то надо заштриховать полуплоскость, содержащую данную точку;

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

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

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

III. Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.

IV. Если ОДР – не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L – произвольное число, например, кратное и, т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

V. Построить вектор, который начинается в точке (0;0) и заканчивается в точке. Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

VI. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора, при поиске минимума ЦФ – против направления вектора. Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).

VII. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ. Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится.

3. Графический анализ чувствительности.

Правило №1
Чтобы графически определить максимальное увеличение запаса дефицитного ресурса, вызывающее улучшение оптимального решения,
необходимо передвигать соответствующую прямую в направлении улучшения ЦФ до тех пор, пока это ограничение не станетизбыточным.

Правило №2
Чтобы численно определить максимальную величину запаса дефицитного ресурса, вызывающую улучшение оптимального решения,
необходимо:
1) определить координаты точки , в которой соответствующее ограничение становится избыточным;
2) подставить координаты в левую часть соответствующего ограничения.

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

Правило №3.5
Чтобы определить границы допустимого диапазона изменения коэффициента ЦФ, например и ,
необходимо приравнять тангенс угла наклона целевой прямой поочередно к тангенсам углов наклона прямых связывающих ограничений, например и

4. Стандартная форма задачи линейного программирования.

Стандартная форма записи задачи ЛП предполагает выполнение следующих

требований.

1. Все ограничения (включая ограничения неотрицательности переменных)

преобразуются в равенства с неотрицательной правой частью.

2. Все переменные неотрицательные.

Преобразование неравенств в равенства

Неравенства любого типа (со знаками неравенств < или >) можно преобразовать

в равенства путем добавления в левую часть неравенств дополнительных переменных — остаточных или избыточных1, которые связаны с неравенствами типа "<"

и ">" соответственно.

Для неравенств типа "<" в левую часть неравенства вводится неотрицательная

остаточная переменная. Например, в модели компании Reddy Mikks (пример 2.1.1)

ограничение на количество сырья Ml задается в виде неравенства 6х, + 4х2 < 24. Вводя новую неотрицательную переменную s,, которая показывает остаток

(неспользованное количество) сырья Ml, это ограничение преобразуется в равенство

6х, + 4^2 + s, = 24, s,>0.

Неравенства типа ">" в задачах ЛП обычно устанавливают нижнюю границу чего-либо. Избыточная переменная определяет превышение значения левой части

неравенства над этой границей. Так, в модели "диеты" (пример 2.2.2) неравенство

xi + х2 > 800 показывает, что суточное производство пищевой добавки не должно

быть меньше 800 фунтов. Математически это неравенство эквивалентно равенству

х, + х2 - Sj = 800, S,>0.

Положительное значение избыточной переменной S, показывает превышение

суточного производства добавки над минимальным значением в 800 фунтов.

Важно еще раз подчеркнуть, что дополнительные переменные — остаточная st

и избыточная S, — всегда неотрицательные.

Правую часть равенства всегда можно сделать неотрицательной, умножив все

равенство на -1. Кроме того, заметим, что неравенство типа "<" также преобразуется в неравенство типа ">" посредством умножения обеих частей неравенства на -1.

Например, неравенство -jc, + х2 < -3 эквивалентно равенству

-хх + хг + в1 = -3,з,>0.

Теперь, умножая обе части этого равенства на -1, получим равенство с неотрица-

тельной правой частью: х, - х2 - s, = 3.

5. Алгоритм симплекс метода

Алгоритм симплекс-метода находит оптимальное решение, рассматривая ограниченное количество допустимых базисных решений. Алгоритм симплекс-метода всегда начинается с некоторого допустимого базисного решения и затем пытается найти другое допустимое базисное решение, "улучшающее" значение целевой функции. Это возможно только в том случае, если возрастание какой-либо нулевой (небазисной) переменной ведет к улучшению значения целевой функции. Но для того, чтобы небазисная переменная стала положительной, надо одну из текущих базисных переменных сделать нулевой, т.е. перевести в небазисные. Это необходимо, чтобы новое решение содержало в точности m базисных переменных. В соответствии с терминологией симплекс-метода выбранная нулевая переменная называется вводимой (в базис), а удаляемая базисная переменная — исключаемой (из базиса).

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

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

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

Последовательность действий, выполняемых в симплекс-методе.

Шаг 1. Находится начальное допустимое базисное решение.

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

Шаг 3. На основе условия допустимости выбирается исключаемая переменная.

Шаг 4. Методом Гаусса-Жордана вычисляется новое базисное решение. Переход к шагу 2.

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

6. М-метод.

ИСКУССТВЕННОЕ НАЧАЛЬНОЕ РЕШЕНИЕ

В примере 3.3.1 при начальном допустимом базисном решении гарантирова-

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

где все ограничения являются неравенствами типа "<" (с неотрицательной правой

частью), дополнительные (остаточные) переменные позволяют сформировать начальное допустимое базисное решение. Естественно, возникает вопрос: как найти

начальное допустимое базисное решение в задачах ЛП, где есть ограничения в виде

равенств или неравенств типа ">"?

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

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

искусственные переменные: М-метод5 и двухэтапный метод.

3.4.1. М-метод

Пусть задача ЛП записана в стандартной форме (см. раздел 3.1). Для любого равенства i, в котором не содержится дополнительная остаточная переменная, введем

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

какого "физического смысла" в данной задаче), необходимо сделать так, чтобы на

последующих итерациях она обратилась в нуль. Для этого в выражение целевой

функции вводят штраф.

Переменная R, с помощью достаточно большого положительного числа М штрафуется путем ввода в целевую функцию выражения -MRj в случае максимизации

целевой функции и выражения +MR, — в случае минимизации. Вследствие этого

штрафа естественно предположить, что процесс оптимизации симплекс-метода

приведет к нулевому значению переменной Д. Следующий пример проясняет дета-

ли этого метода.

7. Двухэтапный метод.

Двухэтапный метод лишен недостатков, которые присущи М-методу вследствие

ошибок округления. Как следует из названия этого метода, процесс решения задачи ЛП разбивается на два этапа. На первом этапе ведется поиск начального допустимого базисного решения. Если такое решение найдено, то на втором этапе решается исходная задача.

Этап 1. Задача ЛП записывается в стандартной форме, а в ограничения добавляются необходимые искусственные переменные (как и в М-методе)

для получения начального базисного решения. Решается задача ЛП

минимизации суммы искусственных переменных с исходными ограничениями. Если минимальное значение этой новой целевой функции

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

что исходная система ограничений несовместна.) Если новая целевая функция равна нулю, переходим ко второму этапу.

Этап 2. Оптимальное базисное решение, полученное на первом этапе, используется как начальное допустимое базисное решение исходной задачи.

8. Особые случаи применения симплекс-метода.

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

1. Вырожденность.

2. Альтернативные оптимальные решения.

3. Неограниченные решения.

4. Отсутствие допустимых решений.

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

их практическим интерпретациям применительно к реальным задачам.