Теория принятия решений

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

Московский  Горный Государственный  Университет 

Кафедра АСУ 
 
 
 
 
 
 
 
 

Курсовая  работа

по дисциплине

“Теория принятия решений” 
 
 
 
 
 
 
 
 
 

Выполнил:

            

     Принял:

      проф. Куприянов В.В 
 
 
 
 
 
 
 
 
 

Москва 2010 
 

ЗАДАЧА № 1 

Используя двойственный симплексный метод, найти  решение задачи  

 

при ограничениях: 

       

ЗАДАЧА  № 2 

Определить  оптимальное решение по критерию пессимизма – оптимизма по результатам  оценки предпочтения (см. табл.): 

 

при h = 0,3 и h = 0,2 

ЗАДАЧА  № 3 

Найти максимальное и минимальное значение сепарабельной целевой функции: 

 

при ограничениях:

       
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ЗАДАЧА  № 1 

Используя двойственный симплексный метод, найти решение задач:  

 

при ограничениях: 

       
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Симплексный метод решения  ЗЛП. 

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

   Пусть дана ЗЛП в стандартной форме: определить оптимальное значение переменных x₁,…,x_s,…,x_j,…,x_n, максимизирующие целевую ф-цию:  

 

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

      

где a_ij, b_i, c_j – заданные постоянные коэффициенты.

   Для перехода в системе  ограничений  равенства в каждое неравенство  вводят новые дополнительные неотрицательные элементы y_i. Тогда ЗЛП имеет вид:  

 

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

      

   Коэффициенты при дополнительных переменных образуют единичную матрицу – базис. Тогда первоначальное решение имеет вид: 

   X₀=(X₁=0,…,Xs=0,…,Xj=0,…,Xn=0,…,y₁=b1,…,y_j=b_i,…,y_r=b_r,…,y_m=b_m)

или

   X₀=(0,…,0,…,0,...,0, b₁,…,b_i,…,b_r,…b_m). 

   Подставляя  это значение X₀ в целевую функцию, получаем:  

Z(X₀)=0.

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

   В первой верхней строке записывается коэффициенты целевой функции и коэффициенты при базисных переменных, входящих в нее. Во второй строке – обозначение всех векторов. В строках от 1 до m записываются коэффициенты при неизвестных переменных системы линейных ограничений. На пересечении (m+1) строки и столбца Р₀ вычисляется значение целевой функции при допустимом базисном плане как скалярное произведение вектора Р₀ на С_б:  

 

   В этой же строке (m+1) вычисляются оценки (Δj): 

 

   Признак оптимальности ЗЛП на максимум:

 для  того, чтобы решение (план) ЗЛП  был оптимальным необходимо и  достаточно, чтобы его оценки Δj были неотрицательными: 

 

   Признак оптимальности ЗЛП  на минимум:

для того, чтобы решение (план) ЗЛП был оптимальным  на минимум целевой функции Z, необходимо и достаточно, чтобы его оценки Δj были неположительными:  

 

Нахождение  оптимального решения  с использованием двойственного симплексного метода. 

   X*=(X1*,…,Xj*,..,Xn*) называется оптимальным, если целевая функция Z принимает максимальное (минимальное) значение на множестве допустимых решений.

   Данный  метод применяется:

1. для сохранения знаков уже неотрицательных элементов индексной строки (при решении ЦЗЛП);
2. когда свободные члены системы ограничений ЗЛП могут быть любыми числами (по знаку).

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

   Для определения вектора, вводимого в базис, применяются 4 правила:

1. Вычисляются все неотрицательные отношения элементов индексной строки (-Δj) к соответствующим отрицательным элементам разрешающей строки (-a_ij).
2. Находится минимальное отношение из всех .
3. В столбец, в котором расположено это минимальное отношение, является разрешающим и опред. вектор Pj, вводимый в базис.
4. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

   Переход к новой симплексной таблице осуществляется в соответствии с прямым симплексным методом:

1. В столбце Базис вместо имени выводимо из базиса вектора записывается имя нового вектора, вводимого в базис (имена остальных базисных векторов не меняется).
2. На пересечение Сб и строки с новым базисным вектором записывается значение коэффициента целевой функции соответствующего вводимого в базис вектору Pj.
3. В строку с новым введенным вектором переписывается строка из предыдущей симплексной таблицы. Все ее элементы, кроме разрешающего, делятся на РЭ.
4. На пересечении одноименных по векторам строки и столбца проставляется 1, все элементы вектора, вводимого в базис (вектора столбца) заменяется на 0, остальные базисные вектора не меняются.
5. Остальные элементы симплексной. таблицы вычисляются по формуле

 

 

6. Аналогично  вычисляются элементы вектора Р₀.
7. Вычисляются значения целевой функции и оценок, которые записываются по формулам, которые записаны выше, и записываются в (n+1) строке.

   Итерационный конечный процесс продолжается до тех пор, пока в столбце свободных членов Р₀ не  будет больше отрицательных элементов и следовательно найден оптимальный план ЗЛП. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 
 
 
 
 

Решение: 

Сведем все  исходные данные в симплексную таблицу: