Мегаобучалка Главная | О нас | Обратная связь  


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




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

Имеется два пункта однородного продукта. Мощность 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- му потребителю. Найти план перевозок. (матрицу Х) Х= х11 х12 х13 Предложение = спросу.

Х21 х22 х23 900 900

 

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

bj ai b1 b2 b3
  x11 x12 x13
  x21 x22 x23

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

 

х11+x12+x13=400

x21+x22+x23=500

2 x11+x21=300

x12+x22=400

x13+x23=200

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

Функция цели 1 Z=2x11+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




Читайте также:



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (825)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.004 сек.)