Оптимизация показателей качества при наличии ограничений. Линейное программирование

Страницы работы

Содержание работы

2.3. Оптимизация показателей качества при наличии ограничений

Линейное программирование

Определение 1. Общей задачей ЛП называется задача, которая состоит в определении максимального (минимального) значения функции:

                      (2.23)

при условиях

   (2.24)

  (2.25)

           xj ≥ 0                 (2.26)

где   аij , bi, cj – заданные постоянные величины и к ≤ m.

Определение 2. Функция F называется целевой функцией (или линейной формой) задачи (2.23)….(2.26), а условия (2.24)…(2.26) называются ограничениями данной задачи.

Определение 3. Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции F при  выполнении условий (2.24) и (2.26),где к = m, l = n.

Определение 4. Основной ( или канонической) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции F при выполнении условий (2.25) и (2.26), где к = 0 и l = n.

Определение 5. Совокупность чисел Х = (х1, х2, …., хn) удовлетворяющих ограничениям задачи (2.23)…(2.26) называется допустимым решением (или планом).

Определение 6. План Х* = (х1*, х2*, …., хn*), при котором целевая функция задачи (2.23) принимает свое максимальное значение (минимальное) значение, называется оптимальным.

Однофазный симплекс-метод  Рассмотрим каноническую задачу линейного программирования в специальной (диагональной)  форме:

y = с1 х1 + с2x2+….+ сnxn min

х1 +                         +  а1,к+1хк+1 +….+ a1n хn = b1

                       х2 +                   + а2,к+1хк+1 +….+ a2n хn = b2       (2.27)

………………………………………………………

              xk +           + аk,к+1хк+1 +….+ akn хn = bk

Обозначим у = х0 ; bi = ai0 и запишем:

                           х0 - с1 х1 - с2x2-….- сnxn = 0                       (*)

С уравнением (*) сложим все уравнения системы (2.27), умноженные последовательно на с1, с2,…,ск. Получим первое уравнение системы (2.28) в котором отсутствуют все переменные х1 , х2 , …., хк, но в котором может быть свободный член а00:

                     х0 +                                  +  а0,к+1хк+1 +….+ a0n хn = а00

х1 +                         +  а1,к+1хк+1 +….+ a1n хn = а10

                         х2 +                       + а2,к+1хк+1 +….+ a2n хn = а20              (2.28)

………………………………………………………

              xk +           + аk,к+1хк+1 +….+ akn хn = аk0

где

                                

Система (2.28) является диагональной формой относительно переменных   х0, х1 , х2 , …., хк  (или говорят, что система приведена к диагональному виду относительно этих переменных).

          Решение

                             хi = ai0 i = 1, 2, …, k; хк+1 = …= хn = 0                     (2.29)

этой системы без учета нулевого уравнения называется базисным решением, а переменные  х1 , х2 , …., хк  - базисными переменными.

          Если среди элементов  а10, а20,… аk0 имеются нулевые, то соответствующие компоненты базисного решения также равны нулю.

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

          Систему (2.28)записывают в виде симплекс – таблицы :

                                                                             Таблица 2.1

х1

х2

хk

хk+1

...

хn

х0

a00

0

0

0

a0,k+1

a0,n

х1

a10

1

0

0

a1,k+1

a1,n

х2

a20

0

1

0

a2,k+1

a2,n

хk

ak0

0

0

1

ak,k+1

ak,n

      Каждая строка таблицы задает соответствующее уравнение системы (2.28), свободный член которого записан в самом левом (ненулевом) столбце.

       Слева от таблицы записаны текущие базовые переменные. Столбцы, соответствующие базисным переменным, составляют единичную подматрицу симплекс - таблицы (Табл.2.1).

       Исходную задачу ЛП можно привести к диагональной форме относительно х0  и каких-то других к переменных из набора х1 , х2 , …., хn. В этом случае изменяются и базисные переменные, а столбцы, отвечающие этим базисным переменным будут располагаться в соответствующих графах симплекс-таблицы и составлять подматрицу, отличающую от единичной лишь перестановкой столбцов.

       В любом случае текущее базисное решение – это такое решение, в котором все небазисные переменные имеют нулевое значение, а базисные переменные равны соответствующим элементам нулевого столбца.

       Рассмотрим алгоритм симплекс – метода. Начинать следует с таблицы, которая соответствует диагональной форме относительно х0 и некоторых к (базисных) переменных из полного набора х1 , х2 , …,хn.

Все элементы нулевого столбца (кроме, возможно a00) должны быть неотрицательными, так как  bi  ≥ 0.

       Шаг 1. Если среди элементов нулевой строки (не считая a00) нет положительных, так как текущее базисное решение оптимально и минимальное значение целевой функции равно a00. Таблица, соответствующая этому случаю называется оптимальной таблицей.

Если таблица не является оптимальной, то среди положительных элементов нулевой строки (кроме a00) следует выбрать некоторый элемент. Обычно среди положительных элементов выбирают максимальный, но это не обязательно. Пусть выбран элемент a> 0. Тогда столбец с номером s называется ведущим столбцом.

      Если все элементы нулевой строки таблицы не положительны, то значение целевой функции  х0 найденное из нулевого уравнения, является разностью между a00 и суммой произведений небазисных переменных на соответствующие коэффициенты: х0 = a00  - ∑ a0j хj (так как коэффициенты при базисных переменных равны нулю). Таким образом величина х0 зависит только от небазисных переменных. Коэффициенты a0j не положительны, а небазисные переменные не отрицательны. Поэтому минимальное значение х0 достигается только в том случае, когда значения всех небазисных переменных равны нулю. Следовательно, число х0 = a00 действительно минимум, а текущее базисное решение является оптимальным. Следует отметить, что выбор максимального элемента нулевой строки на шаге 1 обеспечивает максимальное убывание целевой функции и, таким образом, ведет к сокращению общего числа вычислений.

       Шаг 2. Выделить среди положительных элементов  ведущего столбца элемент ais, для которого отношение  ai0 / ais  является наименьшим.

Пусть этот элемент ars Его называют ведущим элементом, строку с номером r – ведущей строкой. При выполнении вычислений шага 2 предполагается, что в ведущем столбце найдется по крайней мере один положительный элемент. Если это предположение не выполняется, т.е. все элементы ведущего столбца  (кроме a0s) не положительны, то исходная задача не имеет конечного решения (целевая функция не ограничена снизу на допустимом множестве).

        Чтобы убедиться в этом, предположим, что симплекс – таблица имеет вид таблицы 1 и s = n. Тогда решение

              хi (ג) = ai0 - ain ג ,  i=1,2,…k;  хi (ג) = 0, i = k+1, … n-1; хi (ג) = ג

так, как ai0 ≥ 0;  ain  ≤ 0, I = 1,2,…, k при любых ג ≥ 0 является допустимым, т. е. удовлетворяет соответствующей системе уравнений и имеет неотрицательные компоненты.

Похожие материалы

Информация о работе