Киберфак – бесплатно скачать презентации PowerPoint, лекции, рефераты, шпоры, курсовые cyberfac logo
cyberfac.ru
На главную | Регистрация | Вход
  Статьи  
Главная » Статьи » Математика » Математические методы в экономике

Каноническая постановка задачи линейного программирования

Полезная статья? Пожалуйста, поставьте "+"
Математические методы в экономике - Содержание

Наиболее важными формами задачи линейного программирования являются каноническая и стандартная.

В канонической форме задача является задачей на максимум (минимум) некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х1, х2, ..., хn являются неотрицательными:

a11x1+a12x2+...+a1nxn=b1

a21x1+a22x2+...+a2nxn=b2

............................

a11x1+a12x2+...+amnxn=bm


x1>=0, x2>=0,...,xn>=0

F=c1x1+c2x2+...+cnxn ->max(min)

К канонической форме можно преобразовать любую задачу линейного программирования.

Правило приведения ЗЛП к каноническому виду:

1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением в левую часть некоторой неотрицательной переменной, при чем в неравенства «≤» вводится дополнительная неотрицательная переменная со знаком «+»; в случаи неравенства «≥» - со знаком «-»

a11x1+a12x2+...+a1nxn<=b1

Вводим переменную

xn+1=b1-a11x1-a12x2+...+a1nxn.

Тогда неравенство запишется в виде:

a11x1+a12x2+...+a1nxn +xn+1=b1

В каждое из неравенств вводится своя "уравнивающая” переменная, после чего система ограничений становится системой уравнений.

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

Xk=Xk-Xl

Xk>=0, Xl>=0

l - свободный индекс

3. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на (-1)

4. Наконец, если исходная задача была задачей на минимум, то введением новой целевой функции F1 = -F мы преобразуем нашу задачу на минимум функции F в задачу на максимум функции F1.

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

В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система ограничений ее состоит из одних линейных неравенств типа « = ». Все переменные задачи неотрицательны.

a11x1+a12x2+...+a1nxn=b1

a21x1+a22x2+...+a2nxn=b2

............................

a11x1+a12x2+...+amnxn=bm

F=c1x1+c2x2+...+cnxn ->max(min)

x1>=0, x2>=0,...,xn>=0

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

ai1x1+ai2x2+...+ainxn=bi ai1x1+ai2x2+...+ainxn<=bi

-ai1x1-ai2x2-...-ainxn<=bi

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


Категория: Математические методы в экономике | Добавил: Ni-Cd (12 Декабря 2011)
Просмотров: 4448 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
  Полезные материалы  

В нашем каталоге файлов можно найти много полезной информации. Также советуем заглянуть в каталог статей: в нем есть полезные статьи по темам: Экономика предприятия, Общая экономика, Финансы и Кредит, также Словарь терминов по экономике, Маркетинг, Бухучет и Мировая экономика
Также есть полезная страница Факультеты МИФИ, которая расскажет о том, какие есть в МИФИ факультеты.
Меню
 

Навигация
Теория вероятностей и математическая статистика (ТерВер и МатСтат) [17]
Математический анализ (МатАн) [67]
Математические методы в экономике [24]
 

Поиск
 

Онлайн
Онлайн всего: 1
Гостей: 1
Пользователей: 0
 

Статистика


Рейтинг@Mail.ru

 


2007 - 2024 © Ni-Cd. All Rights Reserved