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

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

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

     Для поддержки математического моделирования разработаны системы компьютерной математики, например, Maple, Mathematica, Mathcad, MATLAB, VisSim и др.Они позволяют создавать формальные и блочные модели как простых, так и сложных процессов и устройств и легко менять параметры моделей в ходе моделирования. Блочные модели представлены блоками (чаще всего графическими), набор и соединение которых задаются диаграммой модели. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1.2 Особенности симплекс метода 

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

Реализация  алгоритма симплекс-метода. 

1. Записать  задачу в канонической форме: заменить все ограничения-неравенства с положительной правой;
2. Разделить переменные на базисные и свободные: перенести свободные переменные в правую часть ограничений-неравенств.
3. Выразить базисные переменные через свободные: решить систему линейных уравнений (ограничений-неравенств) – относительно базисных переменных;
4. Проверить неотрицательность базисных переменных: убедиться в неотрицательности свободных членов в выражениях для базисных переменных. Если это не так, вернуться к пункту 2, выбирая другой вариант разделения переменных на базисные и свободные.
5. Выразить функцию цели через свободные переменные: базисные переменные, входящие в функцию, выразить через свободные переменные;
6. Вычислить полученное базисное решение и функцию цели на нем: приравнять к 0 свободные переменные;
7. проанализировать формулу функции цели: если все коэффициенты свободных переменных положительны (отрицательны), то найденное базисное решение будет минимально (максимально) и задача считается решенной;
8. Определить включаемую в базис и исключаемую из базиса переменные: если не все коэффициенты при свободных переменных в функции цели положительны (отрицательны), то следует выбрать свободную переменную, входящую в функцию цели с максимальным по модулю отрицательным (положительным) коэффициентом, и увеличивать ее до тех пор, пока какая-нибудь из базисных переменных не станет равной 0. Свободную переменную рассматриваем как новую базисную переменную (включаемую в базис), а базисную переменную рассматриваем как новую базисную переменную (исключаемую из базиса);
9. Используя новое разделение переменных на базисное и свободное, вернуться к пункту 3 и повторять все этапы до тех пор, пока не будет найдено оптимальное решение.

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

1. Ограничения вида  «£»- ресурсные ограничения. Справа находится то что мы используем на производстве, слева - то что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0».
2. Ограничения вида «=». Часто бывает, что несмотря на то что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса - Yi. В систему ограничений они входят с коэффициентом «1» , а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin - «+M», при Fmax - «-M»).
3. Ограничения вида «³» - Плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл - перерасход ресурсов или перевыполнение плана, перепроизводство, добавляются с коэффициентом «-1», в целевую функцию - с коэффициентом «0». А искусственные переменные (Y) как в предыдущем случае.

 

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

                                         (первая симплекс таблица)

      Пусть система приведена к каноническому  виду.  

     X1+     q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

     X2+   q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

     X3+  q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

     ……………………………………………………………….

     Xm+  qm,m+1 Xm+1 + …. + qm,m+n Xm+n =hm 

     В ней m базисных переменных, k свободных переменных. m+k=n - всего переменных.

Fmin= C1X1+ C2X2+ C3X3+....+ CnXn

     Все hi должны быть больше либо равны нулю, где i=1,2...m. На первом шаге в качестве допустимого решения принимаем все Xj=0 (j=m+1,m+2,...,m+k). При этом все базисные переменные Xi=Hi.

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

     Таблица 3.1. 
 
 
 
 
 
 
 
 
 

Симплекс  таблица.

 
 

     Первый  столбец- коэффициенты в целевой функции при базисных переменных.

     Второй  столбец - базисные переменные.

     Третий  столбец - свободные члены (hi³0).

     Самая верхняя строка - коэффициенты при целевой функции.

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

      Основное  поле симплекс метода - система коэффициентов из уравнения.

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

      Для первой итерации F0= å ci*hi.

     D1, D2, D3,..., Dm - оценки они рассчитываются по формуле:

     D j = å ciqij-cj. 

     Индексная строка позволяет нам судить об оптимальности плана:

1. При отыскании Fmin в индексной строке должны быть отрицательные и нулевые оценки.
2. При отыскании Fmax в индексной строке должны быть нулевые и положительные оценки.

 

Переход ко второй итерации:

      Для этого отыскиваем ключевой (главный) столбец и ключевую (главную) строку.

      Ключевым  столбцом является тот в котором находится наибольший положительный элемент индексной строки при отыскании Fmin или наименьший отрицательный элемент при отыскании Fmax.

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

     На  пересечении строки и столбца  находится разрешающий элемент.

     На  этом этапе осуществляется к переходу к последующим итерациям.

Переход к итерациям:

1. Выводится базис ключевой строки, уступая место переменной из ключевого столбца со своим коэффициентом.
2. Заполняется строка вновь введенного базиса путем деления соответствующих элементов выделенной строки предыдущей итерации на разрешающий элемент.
3. Если в главной строке содержится нулевой элемент, то столбец, в котором находиться этот элемент переноситься в последующую итерацию без изменения.
4. Если в главном столбце имеется нулевой элемент, то строка, в которой он находиться переноситься без изменения в последующую итерацию.
5. Остальные элементы переносятся по формуле:

Метод искусственного базиса.

                                         (Вторая симплекс таблица)

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

1. Построение  искусственного базиса и  оптимизация функции суммы искусственных переменных, т.е. F0=Y1+Y2+…+Yn = 0  (F®min). Если при этом F0=0, то искусственный базис мы вывели из состава переменных, переходим ко второй фазе – решаем задачу по первой симплекс таблице с действительными переменными. Если же F0¹0, т.е. искусственный базис не выведен из состава переменных – ОЗЛП решений не имеет.
2. Решение преобразованной системы ограничений с заданной целевой функцией и действительными переменными. При этом столбцами искусственных переменных в симплекс методе пренебрегаем.

 

Замечания:

1. При решении задач на max с искусственным базисом следует переходить к решению на min, меняя лишь только целевую функцию:

Fmax = - Fmin.