Особенности т.З.

1. Все ограничения равенства ( в закрытой)

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

3. Каждая переменная входит в С.О. только два раза.

4. Теорема о существовании решения.

Т.З. всегда имеет оптимальное решение если сумма ai= сумме bj.

Док-во: Z=CijXij->min=ai (i=1,m)

=bj (j=1,n) Xij>=0

Очевидно что решением будет Хij = aibj/=aibj/

Просуммируем по i: =aibj/ai = bjai/ai = bj

Про суммируем по j : = ai Xij=min(ai;bj)

Теорема о ранге матрицы.

Ранг матрицы системы ограничений = m+n-1

х11+х12+…+х1n =a1

x21+x22+…+x2n =a2 m

2) xm1+xm2+…+xmn = am

x11+ x21 +xm1 = b1

x12+ x22+ xm2 = b2 n

x1n+ x2n+ +xmn=bn

Докажем что ранг матрицы (А)<m+n

А1=(1,1,1,0…0000…000) (коэффициенты первого уравнения размерность m*n)

А2=(0000,1111,0000000)

А1+А2+…+Аm=(111111111111)

Am+1

Am+2 A1+A2+…+Am=Am+1+Am+2+…+Am+n => Векторы линейно зависимые => уравнения

Am+n системы линейно зависимые между собой , а раз они линейно зависимые , то r(A)<m+n

Докажем что ранг = m+n-1

Ранг – наивысший порядок минора отличный от 0.

1. Построим матрицу А из (1 и 0) размерность m*n , найдем минор нужного порядка n-1 вычеркиваем одну из строк. Минор будет равен 1, отличен от 0.

Из этого следует что число базисных неизвестных в Т.З. = m+n-1 , а остальные переменные будут свободными. Ч.Т.Д.

Матрица Х=¦Хij¦ , называется допустимым решением Т.З. или допустимым планом , если она удовлетворяет системе ограничений и условиям не отрицательности. Допустимый план называется оптимальным , если Z при этом плане принимает свое минимальное значение.

Этапы решения т.З.

1. Находят первоначальный опорный план , либо методом северо-западного угла , либо методом минимального элемента.

2. Согласно т. о потенциальности плана (оптимальности плана) проверяют полученный план на оптимальность если он оптимален , то записывают ответ X* и Zmin=

3. Если полученный план не оптимален переходят к новому опорному плану.

Метод нахождения первоначального опорного плана.

1. северо-западного угла.

Х11=min(ai;bj) Клетка становится занятой – базисной. Если удовлетворен покупатель то столбец закрывается, если все со склада вывезли то закрывается строка. И.т.д.

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

Если в середине таблицы одновременно закрывается строка и столбец , а число занятых клеток не равно рангу, то в следующую клетку ставят 0 базисный и клетка считается занятой -> выражденной решение.