Применение ЭВМ в электроэнергетике: Текст лекций. Медведева С.Н. - 24 стр.

найти переменные x1 , x2 ,..., x n , удовлетворяющие заданной системе                                                   y1 = b1 − (a11 x1 + ... + a1n x n )
ограничений                                                                                                             ...
     n                      n                      n                                                                    y m = bm − (a m1 x1 + ... + a mn x n )
    ∑      a ji xi ≤ c j   ∑      b ji xi ≥ d j   ∑      f ji xi = g j                                                  xi ≥ 0, i = 1,2,...n
    i =1                   i =1                   i =1
                                                                                                                        y j ≥ 0, b j ≥ 0, j = 1,2,...m m < n
                                                                         n
Такие, чтобы целевая функция                               F(X ) =   ∑ ri xi → min(max)   достигла        Переменные, входящие в ЦФ и в правую часть равенств,
                                                                                                     называются независимыми или свободными переменными, а остальные
                                                                     i =1
своего экстремального значения. (Если коэффициенты при неизвестных                                   (yi) – зависимыми или базисными.
принимают значения 0 или 1, то такая задача называется транспортной и                                     Суть метода: значения свободных переменных можно варьировать в
решается с помощью распределительного метода с использованием                                        области положительных чисел так, чтобы базисные переменные не
приема "северо-западного угла"). Симплекс-метод для действительных                                   стали отрицательными. Каждое такое решения называется допустимым
значений коэффициентов.                                                                              базисным решением, ему соответствует определенное значение ЦФ.
    Симплекс-метод требует представления модели в каноническом                                       Переходя от одного базисного решения к другому, определяется
виде. Для этого над заданными уравнениями выполняются следующие                                      минимальное значение ЦФ. Процесс перебора носит упорядоченный
преобразования:                                                                                      характер и определяется симплекс-алгоритмом:
    1) если требуется найти максимум ЦФ, то выполняют переход к ее                                        1. приведение задачи к каноническому виду. В каждом уравнении
минимизации max F ( X ) = − min[− F1 ( X )] ;                                                        д.б. базисная переменная с коэффициентом, равным 1.
    2) система ограничений должна содержать неравенства одного                                            2. составление симплекс-таблицы.
знака, что достигается изменением знака правой и левой части                                                  а) левый крайний столбец=номера i базисных переменных (m)
неравенств;                                                                                                   б) верхняя строка=номера j свободных переменных (n)
    3) преобразуют ограничения-неравенства в ограничения-равен-ства                                           в) на пересечениях в столбце j коэффициенты из уравнений
с помощью введения дополнительной неотрицательной переменной, т.е.                                            г) в правом столбце=постоянные члены уравнений
неравенство заменяют двумя равенствами;                                                                       д) в нижней строке=коэффициенты ЦФ
    4) если на знак переменной не наложено ограничение                                                        е) в последней ячейке=свободный член ЦФ с противоположным
неотрицательности, заменить ее разностью двух неотрицательных                                        знаком.
переменных xi = z i − wi ; z i ≥ 0; wi ≥ 0 ;                                                              Пример: 2х1             -х3+ 3х4+                 х8    =1
    5) если в правой части полученных равенств есть отрицательные                                                           х2           +3х4                     =2
свободные члены, умножить обе части уравнений на (-1).                                                               2х1                             +х7          =6
    В результате преобразований математическая модель записывается                                                                х3            +х6               =6
следующим образом:                                                                                                   -2х1         +х3 -3х4+х5                     =2
                                            n
   определить Z ( X ) = c0 +              ∑ ci xi → min                                                 ЦФ: 4х1-6х3+9х4+66
                                           i =1
при выполнении ограничений