Линейное программирование icon

Линейное программирование




НазваниеЛинейное программирование
страница5/15
Дата конвертации29.07.2012
Размер0.99 Mb.
ТипЗадача
1   2   3   4   5   6   7   8   9   ...   15
1. /лекции динамическое программирование+ио гольдштейн/Глава 1.doc
2. /лекции динамическое программирование+ио гольдштейн/Глава 2.doc
3. /лекции динамическое программирование+ио гольдштейн/Глава 3.doc
4. /лекции динамическое программирование+ио гольдштейн/Глава 4.doc
5. /лекции динамическое программирование+ио гольдштейн/Глава 5.doc
6. /лекции динамическое программирование+ио гольдштейн/Глава 6.doc
7. /лекции динамическое программирование+ио гольдштейн/Глава 7.doc
8. /лекции динамическое программирование+ио гольдштейн/Глава 8.doc
9. /лекции динамическое программирование+ио гольдштейн/Глава 9.doc
10. /лекции динамическое программирование+ио гольдштейн/Глава10.doc
11. /лекции динамическое программирование+ио гольдштейн/НОВЫЙТИТУЛ.doc
12. /лекции динамическое программирование+ио гольдштейн/Оглавление_новое.doc
13. /лекции динамическое программирование+ио гольдштейн/ПРЕДИСЛОВИЕ.doc
14. /лекции динамическое программирование+ио гольдштейн/СПИСОК_ЛИТ.doc
Характеристика исследования операций
Постановка задачи оптимизации
Методы классического анализа
Линейное программирование
Транспортные задачи
Блочное программирование
Характерные источники целочисленности (дискретности)
Нелинейное программирование характеристика задач
Динамическое программирование
Многокритериальные задачи принятия решений
Теория принятия решений
Характеристика исследования операций
Которое определяют по-разному
Список литературы

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


4.3.1. Каноническая форма задач ЛП


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





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

L = max

или



где верхний индекс T означает транспонирование; – вектор коэффициентов целевой функции; – векторы условий, j= – вектор ограничений или вектор свободных членов, иногда используют сокращение ССЧ (столбец свободных членов);

– матрица условий; – вектор переменных; – число переменных в канонической форме, оно не меньше числа переменных в исходной модели

Любую задачу ЛП можно привести к каноническому виду. Возможны 3 случая несоответствия исходной модели каноническому представлению. В каждом из них простое преобразование позволяет получить требуемый вид.

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

2.В исходной модели есть неравенства. При этом способ преобразования зависит от знака неравенства. В случае неравенства очевидно, что разность правой и левой части будет неотрицательной и неизвестной величиной, которую можно принять за новую переменную:



Отсюда получаем следующее равенство:



Таким образом, чтобы привести рассмотренное неравенство к равенству, нужно к левой части неравенства прибавить новую переменную.

Аналогично поступаем с неравенством Но теперь новая переменная обозначает разность левой и правой части



и равенство записывается в виде



то есть чтобы неравенство типа “больше или равно” привести к равенству, следует из левой части вычесть новую переменную. В отличие от исходных переменных такие вновь вводимые переменные будем называть дополнительными. Нетрудно видеть, что они по определению являются неотрицательными, что соответствует каноническому представлению модели.

3.Некоторые переменные исходной модели не имеют ограничения на знак. Исключение таких переменных производится следующим способом.

Пусть – переменная, которая может иметь любой знак. Введем две неотрицательные переменные и во всей модели заменяем их разностью:



Таким образом, последние два случая преобразования к каноническому виду приводят к увеличению числа переменных, и поэтому всегда

Пример 4.1. Исходная модель:



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



4.3.2. Стандартная форма задачи ЛП

Точные методы решения задач ЛП ориентированы на каноническую форму записи модели. Однако в геометрических представлениях удобнее стандартная форма. Мы будем понимать под стандартной модель, в которой все функциональные ограничения имеют вид неравенств и все переменные неотрицательные. Как и выше, тип экстремума не имеет существенного значения.

Таким образом, стандатрная форма модели имеет вид







Та же модель в векторно-матричных обозначениях:

L = max

или




Здесь символ / означает “или”. Число переменных при отсутствии неограниченных по знаку переменных не больше Соответственно матрица и вектор имеют меньшие размеры, чем в канонической модели.

Поясним преобразование равенств в неравенства. Пусть в исходной модели имеется q равенств. Решив эту систему уравнений относительно первых q переменных, получим



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



Таким образом, все ограничения задачи будут записаны в виде неравенств.

1   2   3   4   5   6   7   8   9   ...   15




Похожие:

Линейное программирование iconЛинейное программирование. Методы решения одношаговых задач оптимального управления
Методы решения таких задач получили название математического программирования. Простейшим случаем математического программирования...

Линейное программирование iconДокументы
1. /33 Барсов А.С. - Что такое линейное программирование (1959).djvu
2. /Прочитай...

Линейное программирование iconДокументы
1. /33 Барсов А.С. - Что такое линейное программирование (1959).djvu
2. /Прочитай...

Линейное программирование iconДокументы
1. /Лаб раб 10 Программирование в MS Access часть 3.doc
2. /Лаб...

Линейное программирование iconДокументы
1. /Дж. Д. Маркел. Линейное предсказание речи. 1980.djvu

Линейное программирование iconДокументы
1. /Информатика/Информационный фонд/Источники по информатике.DOC
2. /Информатика/Информационный...

Линейное программирование iconДокументы
1. /ЛЕКЦИИ_МО/Двойственность задач ЛП.doc
2. /ЛЕКЦИИ_МО/Линейное...

Линейное программирование iconСценарный подход и субъектно-ориентированное программирование развития народов севера (к постановке проблемы)*
Сценарный подход и субъектно-ориентированное программирование развития народов севера

Линейное программирование iconТомский государственный университет систем управления и радиоэлектроники
Определение Отображение L из линейного пространства в линейное пространство называется линейным отображением, или линейным оператором,...

Линейное программирование iconДокументы
1. /Программирование.doc

Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2013
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы