Page 48 - 6197
P. 48

За використання змінних  w ,  i   1,r   у структуру цільової
                                                             i
                            функції  ведемо  штраф  з  досить  великим  додатним
                            коефіцієнтом при цих змінних
                                                     n        r
                                                          j 
                                            R    x    c x   Mw .                  (1.39)
                                                        j
                                                                   i
                                                    j  1    i 1
                                Оскільки  розв’язується  задача  знаходження  мінімуму
                            функції    (1.12),  а  у  структурі  цільової  функції  (1.39)  при
                            змінних  w ,  i  1,r  знаходиться великий додатний коефіцієнт,
                                       i
                            то  у  кінцевому  підсумку  всі  змінні  w   повинні  набути
                                                                         i
                            нульових значень, що забезпечить рівність цільових функцій
                            (1.12)  і  (1.39)  при  оптимальному  розв’язку  задачі.  Слід
                            відмітити,  що  на  всіх  проміжних  ітераціях,  які  передують
                            отриманню      оптимального      розв’язку    задачі   лінійного
                            програмування,  штучні  змінні  можуть  приймати  довільні
                            (додатні або від’ємні) значення.
                                Після  того  як  задача  лінійного  програмування  подана  у
                            формі  (1.36)  –  (1.39)  значення  базисних  змінних  w ,
                                                                                           i
                             i  1,r необхідно виразити через відповідні  небазисні змінні  і
                            їх  значення  підставити  у  цільову  функцію  (1.39).  Тепер  до
                            нової структури задачі можна застосувати симплекс-алгоритм
                            для знаходження її оптимального розв’язку.
                                Приклад 1.5. Максимізувати функцію
                                                 Z    5x   x  12x   4x
                                                                       3
                                                           1
                                                                 2
                            за умов
                                                                   8
                                                    2x   x   3x  ,
                                                      1    2    3
                                                    x   2x   x  10 ,
                                                     1     2   3
                                                              0
                                                  x   0 ,  x  ,  x  .
                                                                     0
                                                   1      2       3
                                Оскільки  перше  обмеження  є  подано  у  вигляді  рівняння,
                            то у його структуру вводимо штучну змінну
                                                    2x   x   3x   w   8 .
                                                      1   2    3    1
                                                           48
   43   44   45   46   47   48   49   50   51   52   53