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

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

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

Кафедра АСУ 
 
 
 
 
 
 
 
 

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

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

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

Выполнил:

            

     Принял:

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

Москва 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) строке.

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

 
 
 
 
 

Решение: 

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

 
 

 
 

Ответ: X₁ = 3, X₂ = 0, X₃ = 0, X₄ = 0, X₅ =9, X₆ = 0, X₇ = 0.

        Оптимальный план (Z^*) = -75. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Решение задачи в алгебраическом формате с использованием Lindo. 

MAX -x1-7x2+4x3-9x4-8x5+3x6

SUBJECT TO

3X1+2X2+3X3-2x4+x5+x6=18

2X1+X2-X3-3x4+2x5>=24

END

LP OPTIMUM FOUND AT STEP      2 

    OBJECTIVE FUNCTION VALUE 

     1)     -75.00000 

VARIABLE        VALUE          REDUCED COST

     X1         3.000000          0.000000

     X2         0.000000          8.250000

     X3         0.000000         12.250000

     X4         0.000000         19.250000

     X5         9.000000          0.000000

     X6         0.000000          0.500000 
 

     ROW   SLACK OR SURPLUS     DUAL PRICES

       2)         0.000000          3.500000

       3)         0.000000         -5.750000 

NO. ITERATIONS=       2 

RANGES IN WHICH THE BASIS IS UNCHANGED: 

                           OBJ COEFFICIENT RANGES

VARIABLE         CURRENT        ALLOWABLE        ALLOWABLE

                   COEF          INCREASE         DECREASE

      X1       -1.000000        77.000000         1.000000

      X2       -7.000000         8.250000         INFINITY

      X3        4.000000        12.250000         INFINITY

      X4       -9.000000        19.250000         INFINITY

      X5       -8.000000         1.000000         INFINITY

      X6        3.000000         0.500000         INFINITY 

                           RIGHTHAND SIDE RANGES

      ROW         CURRENT        ALLOWABLE        ALLOWABLE

                    RHS          INCREASE         DECREASE

        2       18.000000        18.000000         6.000000

        3       24.000000        12.000000        12.000000 
 
 
 
 
 

ЗАДАЧА  № 2 

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

 

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

Модель  пессимизма – оптимизма. 

   Знание  вероятности не обязательно.

   Модель  выбора оптимального решения имеет  вид: 

 (1) 

где fij – значение функции предпочтения при оценки i – ого решения в j – ой ситуации.

       Чем больше предпочтение, тем больше значение числа.

   h – коэффициент веса пессимизма.

   Если  h = 0, модель (1) превращается в модель оптимизма. 

   Модель  оптимизма – соответствует стратегии выбора, согласно которой коэффициент решения определяется как наилучшие оценки предпочтений по всем ситуациям. Если критерии приводятся в количественной шкале по принципу “чем выше предпочтение, тем больше соответствует ему число”, то коэффициент решений находим по формуле: 

                                  (2) 

   Тогда модель принятия решения имеет вид: 

                               (3) 

   Если  измерение предпочтения проводим в  порядковой шкале и  - есть ранг i-ого решения в j-ой ситуации, т коэффициент решений находим из выражения: 

                                  (4) 

   Модель  выбора решения (оптимального) имеет вид: 

                               (5) 

   Если  h = 1, модель (1) превращается в модель пессимизма. 

   Модель  пессимизма – учитывается осторожная стратегия поведения.

   Для начала нужно определить коэффициент  важности. Для каждой к-ой цели имеется оценка предпочтения в каждой j-ой ситуации.

   Т.к. модель пессимизма рассчитывается на “худший случай”, то в качестве коэффициента важности i-ого коэффициента выбирается наихудшее значение функции предпочтения по всем ситуациям.

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

                                                                        (6)

   (6) - для i-ого решения выбирается по всем j-м ситуациям min значение. 
 
 
 
 

   Модель  нахождения оптимального решения по критерию пессимизма имеет вид: 

                                  (7)

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

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

                                    (8) 

   Модель  принятия оптимального решения в  порядковой шкале имеет вид: 

                                  (9) 

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

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

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

   В количественной шкале коэффициент  решений в случае моделей пессимизма – оптимизма определяется из следующей  формулы: 

 (10) 

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

 
 
 

Решение: 

Исходные данные: 

 

1. Находим минимальное  значение f_ij:

      min f_ij = (1, 3, 2). 

2. Находим максимальное значение f_ij:

      max f_ij = (9, 8, 6). 

3. Находим коэффициенты решение по критерию пессимизма – оптимизма при

   h = 0,3: 

   

      

      

        

4. Находим оптимальное решение по критерию пессимизма – оптимизма:

     

5. Находим коэффициенты решений по критерию пессимизма – оптимизма при

   h = 0,2: 

      

      

      

        

6. Находим максимальное значение βi:

        
 

Ответ: оптимальное решение по критерию пессимизма – оптимизма

• при h = 0,3 составляет 6,6
• при h = 0,2 составляет 7,4

 
 
 
 

ЗАДАЧА  № 3 

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

 

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

       
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Теорема Куна-Таккера. 

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

где - множитель Лагранжа (i=1,2,…,m) 

   Можно доказать, что вектор Х является решением задач нелинейного программирования тогда, когда существует такой вектор с неотрицательными компонентами, что справедливы неравенства: