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

Теорема. Для того, чтобы некоторый план ТЗ был оптимальным, необходимо, чтобы он был потенциальным

Читайте также:
  1. Вихревой характер магнитного поля. Теорема Ампера о циркуляции индукции магнитного поля в дифференциаль-ной и интегральной форме для магнитных полей в вакууме.
  2. Гільбертовий простір. Теорема про ізоморфізм.
  3. ЗАДАНИЕ № 2. Теорема полной вероятности события.
  4. ІІ. СУМІЖНІ КЛАСИ. ТЕОРЕМА ЛАНГРАНЖА.
  5. Корректные и некорректные декомпозиции отношений. Теорема Хита (с доказательством). Минимально зависимые атрибуты.
  6. Момент инерции. Теорема Штейнера.
  7. Основная теорема безопасности Белла — Лападулы
  8. Основная теорема зубчатого зацепления
  9. Принцип вкладених куль. Теорема Бера.
  10. Спектральная теорема
  11. Теорема

Для того, чтобы некоторый план ТЗ был оптимальным, необходимо, чтобы он был потенциальным.

Доказательство. Пусть есть некоторый оптимальный план. Тогда в соответствии с первой теоремой теории двойственности имеют . В то же время, в соответствии со второй теоремой теории двойственности, система ограничений и прямой, и двойственной задач будут удовлетворяться условиями дополнительной нежесткости Слейтера. Укажем условия ДНС для двойственной задачи

.

Вполне очевидно, что для базисного набора клеток , т. к. в клетках указаны положительные значения перевозок. Тогда, чтобы выполнялось УДНС, необходимо и достаточно, чтобы для базисного набора клеток выражение в скобках превращалось в 0, т. е. .

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


 

АЛГОРИТМ МЕТОДА ПОТЕНЦИАЛОВ состоит из двух шагов: предварительного и общего повторяющегося.

Предварительный шаг:

1. Составляют первоначальный опорный план.

2. Составляют первоначальную систему потенциалов.

3. Проверяют план на потенциальность.

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

Если план не потенциальный, то он не оптимальный, и тогда переходят на общий повторяющийся шаг.

Общий повторяющийся шаг:

1. Перестраивают опорный план с целью его совершенствования (улучшения).

2. Перестраивают систему потенциалов.

3. Проверяют план на потенциальность.

Заметим, что метод потенциалов сходится и притом всегда за конечное число итераций.

 

МЕТОДЫ СОСТАВЛЕНИЯ ПЕРВОНАЧАЛЬНОГО ОПОРНОГО ПЛАНА

К опорным планам ТЗ предъявляются следующие требования:

1. Должна удовлетворяться система ограничений.

2. Количество базисных клеток должно быть равно . Если такое условие не выполняется, то в состав базисного набора клеток вводят дополнительные клетки небазисного набора, но с нулевыми значениями перевозок. Таким образом устраняется процедура вырожденности ТЗ.

3. Базисный набор клеток ТЗ должен быть ациклическим.


 


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

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

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