АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Пример составления двойственной задачи ЛП

Читайте также:
  1. I Психологические принципы, задачи и функции социальной работы
  2. I. 1.1. Пример разработки модели задачи технического контроля
  3. I. 1.2. Общая постановка задачи линейного программирования
  4. I. 2.1. Графический метод решения задачи ЛП
  5. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  6. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  7. I. Значение и задачи учета. Основные документы от реализации продукции, работ, услуг.
  8. I. Ситуационные задачи и тестовые задания.
  9. I. Цель и задачи дисциплины
  10. I.5.3. Подготовка данных для задачи линейного программирования
  11. I.5.4. Решение задачи линейного программирования
  12. I.5.5. Просмотр и анализ результатов решения задачи
Пример 2. ЗАДАЧА 1. Требуется мак­симизировать линейную функцию =2x1 — х2 + Зх3 + х4 — 5x5 на множестве пятимерных векторов х = (х1, х2, х3, х4, х5), удовлетворяющих условиям , , , Зх1 + 2х2 - 5х3 + х5 - 7 0, 3х2 - 4х3 - 2х4 + 1 = 0, 2х1 + 2х3 - 3х4 + х5 0.   Решение. ЗАДАЧА 1* Требует­ся минимизировать линейную функцию на множестве трехмерных векторов, удовлетворяющих условиям , , 3y1 + 2y3 + 2 0, 2y1 + 3y2 -1 = 0, - 5y1 + 4y2 + 3y3 + 3 0, - 2y2 - 3y3 +1 0, y1 + y3 - 5 = 0.  

Связь между задачами 1 и 1*

 

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

Для любых допустимых векторов х и у в задачах 1 и 1* выполняются неравенства

µ(x) £ (у), (9)

причем (9) выполняется как равенство в том и только в том случае, если справедливы следующие соотношения:

(10)

(11)

 

 

Связь между задачами 1 и 1*

Доказательство. Имеем:

хj ³0 для jÎJ2

(12)

 

Суммируя полученные соотношения, получим с учетом того, что (13)

 

 

Связь между задачами 1 и 1*

Доказательство (продолжение). Имеем:

yi ≥ 0 для iÎI2

(14)

(15)

Правые части в соотношени­ях (13) и (15) отличаются лишь порядком суммирова­ния и, следовательно, равны между собой, т.е. выполняется µ(x) £ (у) (9). Для достижения равенства в (9), очевидно, не­обходимо и достаточно, чтобы достигались равенства во всех неравенствах (13) и (15). Последнее эквива­лентно выполнению соотношений (10) и (11) ▄


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)