Формы записи задачи линейного программирования



1. развернутая форма

2.матричная форма

a. СХ-> min(max) C=(c11…………cn)

b. AX(=< = >= B)

x.>=0

x=(x11……..xn)

b=(b11……..bn)

c. A=(aij)m*n

3.векторная форма

4.кананическая форма

a. Z-> min целевая функция на min

b.AX=b

c. x.>=0

d.B>=0

5.базисная форма

Линейное векторное пространство. Линейная зависимость векторов. Ранг.

О п р . Совокупность всевозможных упорядоченных систем из n действительных чисел после введения в нее операций сложения и умножения на действительное число называется n-мерным векторным пространством.

О п . Вектор В называется линейной комбинацией векторов A1, A2, ... , An , если существуют такие числа k1, k2, ... , kn, при которых выполняется соотношение B =k1 A1+ k2A2 + ... + knAn .

О п р . Система векторов A1, A2, ... , Ar (r > 1) называется линейно зависимой, если хотя бы один из векторов системы является линейной комбинацией остальных, и линейно независимой — в противном случае.

Рассматривая линейно зависимую систему векторов A1, A2, ... , An , возьмем такую линейно независимую подсистему векторов A1, A2, ... , Ar (r  n), к которой невозможно присоединить ни одного вектора системы, не нарушив линейной независимости. Такая подсистема называется максимальной линейно независимой подсистемой данной системы векторов. Число векторов, входящих в любую максимальную линейно независимую подсистему векторов, называется рангом системы, а сами вектора составляют базис системы.

Понятие базиса системы. Базисное и опорное решение системы.

О п р . Базисом n-мерного векторного пространства называется любая совокупность n линейно независимых векторов этого же пространства.

В двумерном пространстве в качестве базиса могут быть взяты два любых неколлинеарных вектора, в трехмерном пространстве — три некомпланарных вектора, в пространстве измерений n > 3 — система из n линейно независимых векторов.

В качестве базиса удобно выбрать систему единичных векторов n-мерного векторного пространства:

                                                                                   (2.1)

Тогда компоненты любого n-мерного вектора можно считать координатами этого вектора в единичном базисе.

О п р . Базисными решениями называются решения системы, получаемые при приравнивании свободных неизвестных нулю.

О п р . Базисное решение называется невырожденным, если все базисные переменные полученного решения ненулевые, в противном случае базисное решение называется вырожденным.

  О пр . Опорными решениями системы называются те базисные решения, которые имеют все неотрицательные значения неизвестных

 

Отыскание исходного опорного базиса

по еденичке в строчке, и так в каждой клеточке

 

 

Переход от одного опорного решения к другому

необходимо выполнить следующую последовательность действий:

1) начинаем с преобразования системы методом последовательных исключений, причем выбор разрешающего элемента на начальном этапе может быть совершенно произвольным;

2) если после приведения системы к единичному базису появились отрицательные свободные элементы, выберем среди них наибольший по абсолютной величине и вычтем почленно выделенное таким образом уравнение из всех остальных уравнений с отрицательными свободными членами. Само же выделенное уравнение перепишем, умножив все коэффициенты на -1;

3) дальнейшие преобразования системы будем проводить согласно правилам однократного замещения, выбирая разрешающий столбец из условия, чтобы он имел в выделенной строке положительный элемент. Для выбора разрешающей строки вычисляем отношения Aio к Aip и берем в качестве разрешающей строку с минимальным полученным значением;

4) предположим, что после выполнения некоторого количества итераций (3) мы все же не смогли выделить базис полностью и пришли к таблице, в которой выделенная строка не имеет ни одного положительного элемента, кроме свободного члена. Очевидно, что процесс последовательных преобразований на этом обрывается, ибо становится невозможным выбор разрешающего столбца по указанному выше принципу. Нетрудно прийти к выводу, что в этом случае исходная система уравнений не имеет ни одного решения с неотрицательными значениями неизвестных, в том числе и опорного решения, или, как говорят, несовместна в области неотрицательных (допустимых) решений.

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


Дата добавления: 2018-05-12; просмотров: 635; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!