|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Несовместность задачи
Рассматривается задача в стандартной форме
Здесь столбцы aj матрицы A описывают технологические способы, элементы вектора b – запас ресурсов или обязательство (цели) по их производству.
В данной формулировке несовместность задачи означает, что применяемые в модели технологии при имеющихся ресурсах не обеспечивают выполнение обязательств и достижение целей.
Так как реальная система как то работает, то несовместность задачи показывает, что проект (модель) нуждается в доработке.
Направления совершенствования модели:
Изменяем правые части ограничений задачи: Насколько нужно увеличить каждое bi, чтобы задача стала разрешимой. Вводим вектор переменных «надбавок» . где ri ≥ 0 – «стоимость» изменения правой части.
Важно: «стоимость» должна быть соизмеримой с исходной целевой функцией. Пусть есть ki способов увеличения bi. При этом способ k может увеличить bi не более чем на с удельными затратами . Также пусть более дешевые способы имеют меньшие номера:
Задача запишется следующим образом:
Утверждение: Если в оптимальном решении последней задачи zik > 0, то Доказательство: Пусть в оптимальном решении задачи для некоторых
В некотором роде рассмотренные способы изменения правых частей сводятся к задаче добавления нового технологического способа производства.
Возникает вопрос: каким условиям должен соответствовать технологический способ, добавляемый в модель с целью устранения несовместности?
Рассматривается задача P в канонической форме: c · x → max при Ax = b, x ≥ 0. Будем считать, что вектор b ≥ 0.
Решение данной задачи происходит с симплекс-метода, с поиска исходного БДР методом искусственного базиса: рассматривается вспомогательная задача P 1, которая всегда разрешима: – Σ i ti → max при Ax + t = b, x ≥ 0, t ≥ 0.
Пусть f 1 – оптимальное решение задачи P 1. | f 1| указывает на минимальную достижимую величину «суммарного невыполнения» ограничений задачи P. Если задача P совместна, то f 1 = 0, иначе f 1 < 0.
Устранение несовместности задачи – введение такого технологического способа, который повысит значение f 1 (в идеале до нуля).
Рассмотрим задачу P 1*, двойственную к вспомогательной: h (y) = b · y → min при yA ≥ 0, 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 1≤ f 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.
Замечание: Указанное в утверждении условие необходимо, но, вообще говоря, недостаточно, чтобы при введении нового технологического способа задача стала совместной (потребуется введение нескольких дополнительных технологических способов).
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.) |