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

Несовместность задачи

Читайте также:
  1. Задачи.
  2. Неограниченность задачи.
  3. Распределение товаров. Политика распределения товаров. Стратегические и тактические задачи.
  4. Ситуационные задачи.
  5. Ситуационные задачи.
  6. Ситуационные задачи.
  7. Сформулируйте диагноз основного заболевания и ведущий синдром, требующий оказания неотложной помощи, обосновав их сведениями из условия задачи.
  8. Тема: Сущность архитектуры и её задачи.

 

Рассматривается задача в стандартной форме

 

Здесь столбцы aj матрицы A описывают технологические способы, элементы вектора b – запас ресурсов или обязательство (цели) по их производству.

 

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

 

Так как реальная система как то работает, то несовместность задачи показывает, что проект (модель) нуждается в доработке.

 

 

Направления совершенствования модели:


 

Изменяем правые части ограничений задачи:

Насколько нужно увеличить каждое bi, чтобы задача стала разрешимой.

Вводим вектор переменных «надбавок» .


где ri ≥ 0 – «стоимость» изменения правой части.

 

Важно: «стоимость» должна быть соизмеримой с исходной целевой функцией.

Пусть есть ki способов увеличения bi. При этом способ k может увеличить bi не более чем на с удельными затратами . Также пусть более дешевые способы имеют меньшие номера:

 

Задача запишется следующим образом:



 

Утверждение: Если в оптимальном решении последней задачи zik > 0, то
zik` = dik` для всех k` < k (способ применяется только после того, как исчерпаны возможности более дешевых способов).

Доказательство: Пусть в оптимальном решении задачи для некоторых
k` < k имеем zik > 0, и zik` < dik`.
Тогда существует такое δ >0, что zik – δ > 0 и zik` + δ < dik`.
Заменяя в условиях задачи zik на zik – δ, а zik` на zik` + δ, видим, что все они выполняются.
Но при этом значение целевой функции выросло на величину δ(rik – rik`). А это противоречит оптимальности решения.

 

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

 

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

 

Рассматривается задача P в канонической форме:

c · x → max при Ax = b, x0.

Будем считать, что вектор b0.

 

Решение данной задачи происходит с симплекс-метода, с поиска исходного БДР методом искусственного базиса: рассматривается вспомогательная задача P 1, которая всегда разрешима:

– Σ i ti → max при Ax + t = b, x0, t0.

 

Пусть f 1 – оптимальное решение задачи P 1. | f 1| указывает на минимальную достижимую величину «суммарного невыполнения» ограничений задачи P. Если задача P совместна, то f 1 = 0, иначе f 1 < 0.

 

Устранение несовместности задачи – введение такого технологического способа, который повысит значение f 1 (в идеале до нуля).

 

Рассмотрим задачу P 1*, двойственную к вспомогательной:

h (y) = b · y → min при yA0, yi ≥ –1 для всех i.

Так как задача P 1 разрешима, то и двойственная к ней будет иметь решение y * и h (y *) = f 1.

 

Предположим, что в исходную задачу вводится новый технологический способ: переменная x ≥ 0 с коэффициентами ai в ограничениях и c – в целевой функции. Аналогично строится вспомогательная задача P 2.

 

Она будет отличаться от P 1 введенной дополнительной переменной с теми же коэффициентами в ограничениях и нулевым коэффициентом в ЦФ.

 

Пусть x допустимое решение задачи P 1, тогда решение (x, x) при x = 0 – допустимо в P 2. Задача P 2 совместна. Двойственная к ней P 2* – также разрешима.

 

Отличие задачи P 2* от задачи P 1* в ограничении:

Σ i aiyi ≥ 0 (*).

Задачи P 2 и P 2* разрешимы одновременно по первой теореме двойственности. Их целевые функции имеют одинаковые значения f 2.

 

Пусть Y 1 и Y 2 – множества допустимых решений задач P 1* и P 2* соответственно. Поскольку любое дополнительное ограничение сужает область поиска решения, то Y 1 Y 2.Поэтому f 1f 2 – чем шире области минимизации (Y 1), тем меньше минимум.

 

Если решение задачи P 1* удовлетворяет условию (*), то оно также является допустимым решением задачи P 2*: y * Y 2 и f 2 = min Y 2 h (y) ≤ h (y *) = f 1

 

Так как нам нужно, чтобы при добавлении способа значение целевой функции задачи P 1 повышалось (f 1 < f 2), то, c учетом вышеупомянутого замечания, необходимо, чтобы условие (*) не выполнялось.

Утверждение: Для того, чтобы в несовместной задаче P с неотрицательным вектором b после введения нового технологического способа (a1,…,am, c) задача стала совместной, коэффициенты ai должны удовлетворять условию

Σ i aiyi * < 0,

где yi* – двойственные оценки вспомогательной задачи P 1.

 

Замечание: Указанное в утверждении условие необходимо, но, вообще говоря, недостаточно, чтобы при введении нового технологического способа задача стала совместной (потребуется введение нескольких дополнительных технологических способов).

 


 


1 | 2 | 3 | 4 |

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



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