Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


—имплекс- метод при заданном начальном Ѕƒ–




ѕусть Ѕƒ– задачи (2.4.1) соответствует переменным . “огда ограничени€ задачи (2.4.1) могут быть преобразованы к виду

(2.5.1)

...................................

“огда векторы u и v предыдущего параграфа можно выразить через x следующим образом:

,

—огласно (2.4.7), вектор критери€ оптимальности может быть получен посредством преобразовани€ первоначальной целевой функции, записанной в виде уравнени€

.

»з этого уравнени€ вычитаютс€ уравнени€ ограничений, умноженные соответственно на . ¬ результате будет получено новое уравнение

(2.5.2)

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

ѕример. –ешить задачу (1а).

Ќабор , , €вл€етс€ Ѕƒ–. ‘ункци€ , имеюща€ нулевое значение, выражена через небазисные переменные.  оэффициенты при и отрицательные. “ак как коэффициент при больше по модулю, выберем переменную дл€ изменени€. —уществует предел изменени€ переменной поскольку ограничени€ (2.4.1) должны выполн€тьс€, и переменные , оставатьс€ неотрицательными.

ѕоскольку ,

то при .

ѕоскольку ,

то при .

ѕоэтому .

Ётот итерационный процесс удобно представить в симплекс- таблицах

 

итераци€   базис значение операции над строками
  - z   -2 -4    
           
      5 *    

 

  - z   -2/5     4/5
    7/5 *     -4/5
    2/5     -1/5

 

  - z       2/7 4/7  
        5/7 -4/7  
        -2/7 3/7  

 

—права от таблиц приведены операции со строками. Ўтрихом обозначаетс€ вновь полученна€ строка, котора€ помещаетс€ в следующую таблицу. —трока, соответствующа€ -функции, нумеруетс€ как нулева€ строка. «вездочкой обозначаетс€ элемент, соответствующий столбцу, вводимому в базис с наибольшим по модулю отрицательным значением нулевой строки, и строке, соответствующей той базисной переменной, котора€ убывает до нул€ и выводитс€ из базиса.

–ассмотрим симплекс-метод в таблицах. ѕредположим, что на некоторой произвольной итерации задача Ћѕ представлена в форме (2.5.2), (2.5.1), а коэффициенты внесены в таблицу:

 

базис значение ... ... ... ...
- z                
               
               
               
                         
               

 

»тераци€ процесса состоит из трех шагов.

1) Ќайти переменную дл€ включени€ в базис. ѕеременные небазисные. Ќаходим наименьший из коэффициентов . ѕусть это коэффициент . ≈сли , то увеличение приведет к убыванию функции . Ѕудем выбирать столбец с наименьшими значени€ми . ≈сли все , то значение функции не может быть уменьшено, решение найдено.

2) Ќайти переменную дл€ исключени€ из базиса. —ледует найти дл€ каждой базисной переменной величину, на которую можно увеличить не наруша€ услови€ неотрицательности „тобы не нарушалось условие неотрицательности ни дл€ одной базисной переменной следует выбрать

≈сли этот минимум достигаетс€ в строке , то обращаетс€ в 0. ƒругие базисные переменные останутс€ неотрицательными. Ёлемент называетс€ ведущим элементом, строка - ведущей строкой, столбец - ведущим столбцом.

3) ѕостроить новую форму задачи типа (2.5.2), (2.5.1) дл€ базисных переменных. —ледует коэффициент при в ведущей строке сделать равным 1, поделив строку на «атем исключить коэффициенты при из других строк, прибавл€€ или вычита€ ведущую строку.





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-02-12; ћы поможем в написании ваших работ!; просмотров: 488 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

—туденческа€ общага - это место, где мен€ научили готовить 20 блюд из макарон и 40 из доширака. ј майонез - это вообще десерт. © Ќеизвестно
==> читать все изречени€...

2014 - | 1939 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.012 с.