Баланс: 0.00
Авторизация
placeholder
Openstudy.uz saytidan fayllarni yuklab olishingiz uchun hisobingizdagi ballardan foydalanishingiz mumkin.

Ballarni quyidagi havolalar orqali stib olishingiz mumkin.

Метод симплекс-таблиц. Исполнитель


Метод симплекс-таблиц..doc
  • Скачано: 31
  • Размер: 159.5 Kb
Matn

Метод симплекс-таблиц.

Как известно общая задача линейного программирования имеет следующей вид:

{spoiler=Подробнее}

                                                        (1)

при условиях

                                     (2)

                               (3)

                                      (4)

где   А i  j ,    Вi  ,  С j  -- заданные    постоянные     величины    и   к

F=CX                                                                 (5)

при условияx

х 1 P1   + X2 P2 + ...+  Хп   Рп    =  Р­о                                          (6)

x    С                                                                 (7)

где    С  =  (С1  , С  2  , .....  ,  С  n)   Х= ( Х :  ,  Х 2 ,  ....  ,   Х n  ): CX­ скалярное произведения: Р1 ,  Р2 ,  ....   Рn   -n -мерный вектор столбце, составление из коэффициентов при неизвестных и свободных членах системы уравнений задачи:

P0 =

Пусть требуется найти максимальное значение функции

при условиях

Здесь ai ,bi    и ci (i=1,m; j=1,n) - заданные постоянные числи (m=n и bi>0).

     (8)

при условиях

X1P1 + X2P2 + . . . + XmPm + . . . + XnPn = P0   (9)

Xj>0         (j=1,n)    (10)

где

Так, как

b1p1 + b2p1 + . . . + bmpm = p0

то на определению опорного плана Х=( b1, b2,...bm ;0,0,....0) является опорном планом данной задачи. Этот план определяется системой единичных векторов Р1, Р2, ... Рn которые образуют базис m-мерного пространства

Пусть 

Положим         так как векторы р1,р2,......,рm- единичные, то xij=aij  и  zi=a   Aj=.

ТЕОРЕМА: (признак оптимальности опорного плана)

Опорный план   х*=(х1*,x2*,….xn*,0,0,0…..0) задачи (8)-(10)-является оптимальный если  Аj=0  для любого  j(j=1,n)     Исследование  опорного плана на оптимальность ,а также дальнейший вычислительный процесс удобного вести, записать так как показано в следующее таблице:


I
Базис Сб Р0 С1 С2 …. С2 Сm Cm+1 Ck Cn
P1 P2 P2 Pm Pm+1 Pk Pn

12

.

.

 .r

.

.

m      

P1

P2

.

.

PR

.

.

Pm

C1

C2

.

.

Cr

.

.

Cm

B1

B2

.

.

br

.

.

bm

1

0

.

.

0

.

.

0

0

1

.

.

0

.

.

0

..

0

0

.

.

1

.

.

0

0

0

.

.

0

.

.

.1

A1m+1

A2m+1

…..

…..

arm+1

….

….

Amm+1

……………………

A1k

A2k

ark

amk

……………………
M+1 F0 0 0 0 0 :m+1 :k :k
                                   

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

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

Столбце векторов рi представляет собой  коэффициенты разложенный этик векторов данного базиса. В строке определяются исходными данными задачи, а показатели (m+1)-й строке вычисляют. В этой строке в столбце вектора р0 записывают значение целевой функции ,которое она принимает при данном опорном плане, а в столбце вектора рi -значение  Di=zi-ci ;,m) на вектор Сб=(С1;C2;….,Cm)

Zi=

Значение F0 равно скалярному произведению вектора р0 на вектор Сi:

Fn значение zi находится как скалярное произведение вектора

Fi(i=1 =

После заполнения таблицы опорного плана проверяют на оптимальность. Для этого просматривают элементы (m+1)-й строки таблицы. В результате может иметь место один из следующих трех случаев:

  1. для  j=m+1 , m+r,....... ,n(при  j=1,mZj=Cj)

По этому, в данном случая числа   :j0  всех j от 1до n:

2) для  некоторых  индексов j  и  для каждого такого j  по крайней мере одно из чисел аji положительно.

3) для некоторого j  и  все соответствующие  этому индексу величины аij   (i=1,m)

В первом случае  на основании признака оптимальности исходный опорный план является оптимальным. Во втором случай целевая функция не ограничена сверху на множестве планов. А в третьем случае можно перейти от исходного плана  к новому  опорному плану ,при котором значение целевой функции увеличиться .

Этот переход от одного опорного плана к другому осуществляются исключением из исходного базис какого-нибудь из векторов и введением в него нового вектора.

Пусть, например, Dk0 и решено вести в базис вектор рк.

Для определения вектора, подлежащего исключению из базиса ,находят min(в аik)  для всех аik. Пусть этот минимум достигает при i=2. Тогда из базиса исключают вектор рr  а число аrk называют разрешающим элементом.

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

После выделения направляющей строки направляющего столбца находят новый опорный план  и  коэффициенты разложении векторов Рj через векторы нового базиса ,соответствующего новому опорному плану , это легко реализовать если воспользоваться методом Жордана-Гаусс. При этом можно показать ,что положительных компоненты  нового опорного плана вычисляются по формулам:

bi1=                 при

a-коэффициенты разложения векторов Рj через векторы нового базиса, соответствующего новому опорному плану -по формулам:

ai1j= при

После вычисления br1j  и  ai1j  согласно но формулой 11 и  12  их значения заносят в след. табл.

Элементы (m+1) й  строки  этой  таблицы могут быть вычислены либо по формулам:

p01=p0-(br/ark) Dk                              (13)

Dj1=Dj-(arj/ark) Dk                              (14)

либо основании их определения .

После заполнения новой симплекс таблицы просматривают элементы(m+1)-й строки. Если все zj-cj, то новый опорный план является оптимальным.

Таким образом, решение симплексным методом осуществляется в определенной последовательности .

1)Находится базисное допустимое решение .

2)Вычисляется симплекс - разность для каждой переменной не входящей в базис;

3)Вводится  в базис переменная, удовлетворяющая условию max(xr)=min(xi1/xir)

4)Исключается из решения переменная, соответствующая  max(xr),ни вектор Рi;

5)n 1-4 повторяется до тех пор, пока симплекс разность для всех переменных не входящих в базис, не станет равной нулю или отрицательной . это свидетельствует  о том , что оптимальное решение получено.


{/spoilers}

Комментарии (0)
Комментировать
Кликните на изображение чтобы обновить код, если он неразборчив
Copyright © 2024 г. openstudy.uz - Все права защищены.