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

Задача, содержащая в свободных членах системы ограничений параметр

Читайте также:
  1. Assigning Pin Location Constraints (назначение ограничений на размещение выводов).
  2. Entering Timing Constraints (ввод временных ограничений).
  3. ERP (Enterprise Resource Planning)- системы управления ресурсами предприятия.
  4. III. СИСТЕМЫ УБЕЖДЕНИЙ И ГЛУБИННЫЕ УБЕЖДЕНИЯ
  5. III. Требования к организации системы обращения с медицинскими отходами
  6. IV. Расчет электрических параметров электрофильтра.
  7. L.1.1. Однокомпонентные системы.
  8. L.1.2.Многокомпонентные системы (растворы).
  9. SCADA как часть системы автоматического управления
  10. SCADA системы как инструмент проектирования АСУ ТП
  11. SCADA системы. Обзор SCADA систем
  12. T.5 Определение нормальной скорости распространения пламени и термодинамических параметров

Дана линейная функция и система линейных ограничений

(3.2.1)

(3.2.2)

Алгоритм решения задачи (3.2.1)-(3.2.2) подобен рассмотренному выше алгоритму решения задачи (3.1.1)-(3.1.2). Полагая значение параметра равным некоторому числу находим решение полученной задачи линейного программирования. При данном значении параметра , либо определяем оптимальный план задачи, либо установим ее неразрешимость. В первом случае найденный план является оптимальным для любого , где

 

и числа и определены компонентами оптимального плана и зависят от :

.

Если при задача (3.2.1) - (3.2.2) неразрешима, то либо целевая функция задачи (3.2.1) не ограничена на множестве планов, либо система уравнений (3.2.2) не имеет неотрицательных решений. В первом случае задача неразрешима для всех , а во втором случае определяем все значения параметра , для которых система уравнений (3.2.2) несовместна, и исключаем их из рассмотрения. После определения промежутка, в котором задача (3.2.1) - 3.2.2) имеет один и тот же оптимальный план или неразрешима, выбираем новое значение параметра , не принадлежащее найденному промежутку, и находим решение полученной задачи линейного программирования. При этом решение новой задачи ищем с помощью двойственного симплекс-метода. Продолжая итерационный процесс, после конечного числа шагов получаем решение задачи (3.2.1) - (3.2.2). Итак, процесс нахождения решения задачи (3.2.1) - (3.2.2) включает следующие основные этапы:

1. Считая значение параметра равным некоторому числу , находят оптимальный план или устанавливают неразрешимость полученной задачи линейного программирования.

2. Находят значения параметра , для которых задача (3.2.1) - (3.2.2) имеет один и тот же оптимальный план или неразрешима. Эти значения параметра исключают из рассмотрения.

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

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

Пример 3.2.1. Для каждого значения параметра найти максимальное значение функции

Решение. Считая , находим решение:

 

 

Таблица 3.2.1.

БП СЧ
         
  -1      
-2        
С   -1      

 

Таблица 3.2.2.

БП СЧ
        -1/2
        1/2
-1       1/2
С         1/2

Оптимальный план при : . Этот план будет оставаться оптимальным, пока среди его компонент не окажется отрицательного числа:

 

.

 

Следовательно, при : Исследуем, имеет ли задача оптимальные планы при . Если , то и, следовательно, не является планом задачи. Поэтому надо перейти к новому плану. Это можно сделать, когда в строке имеются отрицательные числа. В данном случае это условие выполняется. Переходим к оптимальному плану, применяя двойственный симплекс-метод.

 

Таблица 3.2.3.

БП СЧ
        1/2
         
  -1     -1/2
С          

 

, Этот план остается оптимальным при

.

Если , то это решение не является планом, так как
. Так как в строке нет отрицательных чисел, то исходная задача неразрешима.

При , не является планом, так как . С помощью таблицы 3.2.2 переходим к следующему решению:

 

Таблица 3.2.4.

БП СЧ
-4   -2    
         
         
С          

, Этот план оптимален при условии . При задача неразрешима, так как в строке нет отрицательных чисел.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

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



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