Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Связь между различными типами задачи ЛП

Читайте также:
  1. B) система отношений между людьми
  2. Barbie: использование капитала маркина международных рынках 1 страница
  3. Barbie: использование капитала маркина международных рынках 10 страница
  4. Barbie: использование капитала маркина международных рынках 11 страница
  5. Barbie: использование капитала маркина международных рынках 12 страница
  6. Barbie: использование капитала маркина международных рынках 2 страница
  7. Barbie: использование капитала маркина международных рынках 3 страница
  8. Barbie: использование капитала маркина международных рынках 4 страница
  9. Barbie: использование капитала маркина международных рынках 5 страница
  10. Barbie: использование капитала маркина международных рынках 6 страница
  11. Barbie: использование капитала маркина международных рынках 7 страница
  12. Barbie: использование капитала маркина международных рынках 8 страница



Покажем, что общая задача ЛП может быть сведена как к однородной задаче ЛП, так и к канонической.

I. Вначале сведём общую задачу к однородной. В соответствии с определением 1 п.1.3 для этого достаточно каждое ограничение вида равенства:

,

заменить на равносильную систему неравенств:

Все ограничения задачи будут иметь вид неравенства и задача станет однородной. При этом число ограничений, конечно же, увеличится.

II. Теперь сведем общую задачу ЛП к канонической. Для этого следует, во-первых, представить каждое неравенство в виде равенства и, во-вторых, добиться того, чтобы все переменные задачи были неотрицательны. Для каждого неравенства системы ограничений вида «меньше»

,

добавим новую (балансовую) переменную , определяемую равенством:

.

Для каждого неравенства системы ограничений вида «больше»

введем переменную , определяемую равенством:

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

Для каждой переменной , на которую не наложено тривиальное ограничение, положим: где и

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

Пример 1. Пусть дана задача ЛП

(1)

Требуется преобразовать исходную общую задачу ЛП к другим формам задачи ЛП.

1. Сведем эту задачу к однородной форме.

Заменяя равенство из (1) на систему неравенств получим соответствующую однородную задачу:

(2)

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

Заменим переменную :

Тогда получим каноническую задачу:

(3)

фактически равносильную исходной.

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

Сведение произвольной канонической задачи ЛП к симплексной форме будет рассмотрено в следующих параграфах.

Укажем на один частный случай сведения однородной задачи ЛП к симплексной форме. Пусть дана задача о ресурсах, то есть однородная задача ЛП вида:

(4)

причем все

Сведем эту задачу к канонической с помощью введения балансовых переменных

 

 

(5)

Полученная каноническая задача ЛП на самом деле является симплексной, поскольку, во-первых, столбец свободных членов состоит только из неотрицательных элементов, во-вторых, система уравнений имеет разрешенный вид (столбцы переменных , …, и сами переменные являются базисными), в-третьих, целевая функция F зависит только от свободных переменных .



 





Дата добавления: 2014-12-26; Просмотров: 64; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


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



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.224.210.130
Генерация страницы за: 0.012 сек.