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

Метод Гомори

Читайте также:
  1. F. Метод, основанный на использовании свойства монотонности показательной функции .
  2. FAST (Методика быстрого анализа решения)
  3. I этап Подготовка к развитию грудобрюшного типа дыхания по традиционной методике
  4. I. 2.1. Графический метод решения задачи ЛП
  5. I. 3.2. Двойственный симплекс-метод.
  6. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  7. I. Метод рассмотрения остатков от деления.
  8. I. Методические основы
  9. I. Методические основы оценки эффективности инвестиционных проектов
  10. I. Организационно-методический раздел
  11. I. Предмет и метод теоретической экономики
  12. I. Что изучает экономика. Предмет и метод экономики.

К основной задаче ЛП добавим дополнительное условие – условие целочисленности неизвестных, в результате получим задачу ЛЦП. Можно, конечно, получить дробное оптимальное решение задачи ЛП и его округлить до ближайших целых значений. Но тогда может случиться, что мы будем либо близки к оптимальному плану задачи ЛЦП, либо далеки, либо вообще уйдем за пределы множества планов ЛЦП. Один из возможных методов решения задачи ЛЦП – метод Гомори. Идея метода базируется на представлении вещественного числа в виде суммы его целой и дробной частей. Как известно, целой частью вещественного числа «а» называется наибольшее целое число, не превосходящее Обозначение целой части [a]. Разность есть дробная часть числа Очевидно, например, что и Например:


Рассмотрим метод Гомори на примере (общая задача ЛП):

План задачи линейного программирования называют целочисленным, если все его составляющие целые числа.

Для определения целочисленного решения задачи:

или в краткой форме:

можно использовать алгоритм Гомори, состоящий из следующих этапов.

Первый этап. Задача (7.1) - (7.3) решается симплекс-методом до получения оптимального плана.

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

составленное для i - ой строки следующим образом:

где

(Символом [ a ] обозначают целую часть числа a, то есть наибольшее целое число, не превосходящее a).

Третий этап. В последней симплекс-таблице выбирают введенную строку разрешающей. Разрешающий столбец выбирают по правилу двойственного симплекс-метода. С выбранным таким образом разрешающим элементом осуществляют переход по известному алгоритму к следующей симплекс-таблице. Если при этом полученное решение окажется еще не целочисленным, то общий шаг повторяют.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 |

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



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