Формы задач линейного программирования. Связь между ними. Запись злп в матричной форме

Формы задач линейного программирования. Связь между ними. Запись злп в матричной форме

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

-математические модели очень большого числа экономических задач линейны относительно искомых переменных;

- эти типы задач в настоящее время наиболее изучены;

-для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;

-многие задачи линейного программирования, будучи решенными, нашли уже сейчас широкое практическое применение в народном хозяйстве;

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

 

Итак, Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.

Формы:

Общая форма.

Найти вектор х=(х1,х2,…,хn)-?

доставляющий max или min функции z=CₓX1= CₓX2+…..+CₓXn+ Cₒ ≤

При ограничениях:

а11х1+….+а1nXn≤b1

As1 X1+……+Asn Xn≤Bs

As+1,1 X1+……+As+1,n Xn=Bs+1

Am1X1+……+AmnXn=Bm

Xj≥0, j=1,n

 

Основная форма

Найти вектор х=(х1,х2,…,хn)-?

доставляющий max или min функции z=CₓX1= CₓX2+…..+CₓXn+ Cₒ

при ограничениях:

А11Х1+…..+A1n≤B1

……………………..

Am1X1+…..+AmnXn ≤ Bm

Xj≥0, j=1,n

Каноническая модель

Найти вектор х=(х1,х2,…,хn)-?

доставляющий max или min функции z=CₓX1= CₓX2+…..+CₓXn+ Cₒ

при ограничениях:

А11Х1+…..+A1n=B1

………………………

 

Am1X1+….+АmnXn=Bn

 

Xj≥0, j=1,n

 

Связь между ними и запись злп в матричной форме в тетради

Вырождение, зацикливание,неразрешимость задач линейного программирования

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

Если нулевой свободный член окажется в разрешающей строке, то Z не изменится после выполнения итерации. Тоже самое может быть и на 2,3 шаге. Теоретически не исключается возможность после нескольких шагов прийти к первоначальному опорному решению. Такая ситуация называется Зацикливание

Если после очередной итерации окажется Bs<0 а все остальные элементы этой строки >0 то задача неразрешима и з-за несовместимости системы ограничений.

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

Экономическтй смысл двойственных переменных (показатель дефицитности ресурсов и влияния ограничений на значение целевой функции; показатель эффективности производства отдельных видов продукции с позиций критерия оптимальности и инструмент балансировки суммарных затрат и прибыли)

Задача о назначении

Основные понятия теории игр

Основные понятия и постановка задачи динамического программирования. Геометрическая интерпретация

Формы задач линейного программирования. Связь между ними. Запись злп в матричной форме

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

-математические модели очень большого числа экономических задач линейны относительно искомых переменных;

- эти типы задач в настоящее время наиболее изучены;

-для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;

-многие задачи линейного программирования, будучи решенными, нашли уже сейчас широкое практическое применение в народном хозяйстве;

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

 

Итак, Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.

Формы:

Общая форма.

Найти вектор х=(х1,х2,…,хn)-?

доставляющий max или min функции z=CₓX1= CₓX2+…..+CₓXn+ Cₒ ≤

При ограничениях:

а11х1+….+а1nXn≤b1

As1 X1+……+Asn Xn≤Bs

As+1,1 X1+……+As+1,n Xn=Bs+1

Am1X1+……+AmnXn=Bm

Xj≥0, j=1,n

 

Основная форма

Найти вектор х=(х1,х2,…,хn)-?

доставляющий max или min функции z=CₓX1= CₓX2+…..+CₓXn+ Cₒ

при ограничениях:

А11Х1+…..+A1n≤B1

……………………..

Am1X1+…..+AmnXn ≤ Bm

Xj≥0, j=1,n

Каноническая модель

Найти вектор х=(х1,х2,…,хn)-?

доставляющий max или min функции z=CₓX1= CₓX2+…..+CₓXn+ Cₒ

при ограничениях:

А11Х1+…..+A1n=B1

………………………

 

Am1X1+….+АmnXn=Bn

 

Xj≥0, j=1,n

 

Связь между ними и запись злп в матричной форме в тетради