Переход от стандартной формы к канонической форме

Транспортная задача.

Имеется два пункта однородного продукта. Мощность 1^го 400т.; 2^го – 500т., имеется 3 пункта потребления этого продукта. Известны затраты на перевозку 1т. продукции . Из 1^го пункта к 1^му – 2млн. р. ; 2^му – 3 млн. р; 3^му – 4 млн. р. Из 2^го - 1^му – 5 млн. р.;2^му- 4 млн. р.; 3^му- 2 млн. р. Спланировать перевод таким образом, чтобы суммарные затраты были минимальными.

1) нужно 300 т. 2) нужно 400 3) нужно 200 т.

Математическая модель.

Х_ij – кол-во тонн продукции перевезенной из пункта i к пункту j- му потребителю. Найти план перевозок. (матрицу Х) Х= х₁₁ х₁₂ х₁₃ Предложение = спросу.

Х₂₁ х₂₂ х₂₃ 900 900

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

bj ai	b1	b2	b3
	x11	x12	x13
	x21	x22	x23

b –потребность . =

х₁₁+x₁₂+x₁₃=400

x₂₁+x₂₂+x₂₃=500

2 x₁₁+x₂₁=300

x₁₂+x₂₂=400

x₁₃+x₂₃=200

3x_ij>=0 (i= ) (j= )

Функция цели 1 Z=2x₁₁+3x12+4x13+5x21+4x22+2x23 -> min

Математическое моделирование задачи.

Различают другие типы задач :

1) задачи о диете или о рациональном питании.

2) задачи производственного планирования

3) на составление математического моделирования

4) задачи о раскрое

5) задачи о назначениях.

Метод Гауса.

М.Г. вычисляется с помощью таблиц Гауса.

2х1-х2+х3=3

х1+3х2-2х3=1 разрешающий элемнт.

х2+2х3=8 разрешающая строка разреш.столбец.

Х1	Х2	Х3	Св.чл		проверка
	-1
		-2
	-7			-1	-1
		-2
		-8	-23	-30	-30

1)разрешающую строку делим на разрешающий элемент. 2) в разрешающем столбце элементы заменяем на ноли. 3) Все остальные элементы таблицы считаются по правилу прямоугольника.

переход от одной формы модели к другой форме модели , различные формы моделей З.Л.П.

В зависимости от системы ограничения различают в Л.П. три формы модели 1) каноническая 2) стандартная форма 3) общая форма. Эти три формы эквиваленты между собой в том смысле , что от одной формы можно перейти к другой с помощью элементарных преобразований.

Стандартная форма модели З.Л.П. . Система задачи формируется : Найти вектор х, удовлетворяющий системе ограничений и условию не отрицательности.

а11х1+а12х2+…+а1nxn<=b1

a21x1+a22x2+…+a2nxn<=b2

….

am1x1+am2x2+…+amnxn<=bn

xj>=0 j=1,4; Z=c1x1+c2x2+..+cnxn->max

A-матрица (m*n) Z=cx->max Ax<=b x>=0 ; C=(C1 C2 …Cn) b(b1 b2..bm)

Каноническая тоже самое только в системе ограничений = и Ax=b.

Общая форма. Найти вектор Х, удовлетворяющий системе ограничений

a11x1+a12x2+...+a1nxn=b1

am1x1+amnxn=bm

Xj>=0 (j=1,l) l<n Для которого Z=с1х1+cnxn -> max

Для того что бы решать задачи Л.П. симплекс методом необходимо иметь каноническую форму модели, поэтому необходимо знать , как перейти от одной формы модели к другой .

Переход от стандартной формы к канонической форме.

1) ai1x1+ai2x2+…+ainxn<=bi (2)

ai1x1+ai2x2+..+ainxn+ainxi+n=b xn+i>=0 , i=1,m – балансовые переменные. (1)

Можно доказать, что все решения системы 1 равны решениям неравенства 2 и в этом сысле они эквивалентны. Функцию цели эти переменные(xn+i) могут быть введены с коэффициентами =0 => z=c1x1+..+cnxn+oXn+1+..+oxn+m->max