<<
>>

ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

Некоторые задачи линейного программирования требуют целочисленного решения. К ним относятся задачи по производству и распределению неделимой продукции (выпуск станков, телевизоров, автомобилей и т.д.).

В общем виде математическая модель задачи целочисленного программирования имеет вид

при ограничениях:

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

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

Пусть получено оптимальное решение опт = (f1, f2, ... , fr, 0, ..., 0), которое не является целочисленным, тогда последний шаг симплексной таблицы имеет следующий вид:

где r — ранг системы ограничений; hi,r+1 — коэффициент симплексной таблицы i–й строки, (r + 1)–го столбца; fi — свободный член i–й строки.

Пусть fi и хотя бы одно hij (j = , r = ) — дробные числа.

Обозначим через [fi] и [hij] целые части чисел fi и hij.

Определение. Целой частью числа fi называют наибольшее целое число, не превосходящее числа fi.

Дробную часть чисел fi и hij обозначим {fi} и {hij}, она определяется следующим образом:

Пример.

Если fi и хотя бы одно значение hij дробны, то с учетом введенных обозначений целых и дробных чисел дополнительное ограничение по целочисленности примет вид

{hi,r+l} xr+1 + {hi,r+2} xr+2 + • • • + {hi,п} xп ≥ {fi}.

Примечания. 1) Если fi — дробное число, а все hij — целые числа, то задача линейного программирования не имеет целочисленного решения.

2) Ограничение целочисленности может быть наложено не на все переменные, а лишь на их часть. В этом случае задача является частично целочисленной.

<< | >>
Источник: Архаров Евгений Валерьевич. Учебно–методический комплекс по дисциплине Математика Нижний Новгород, 2011. 2011

Еще по теме ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ:

  1. 4.3 Метод диагностического определения потребительной стоимости.
  2. Задача о кратчайшем пути.
  3. 2.1. Сети с упорядоченными событиями
  4. 3.3. Концептуальные положения разработки модели инвестиционной деятельности естественной монополии
  5. Оптимизационная задача
  6. Целочисленное программирование
  7. Постановка задачи и алгоритм решения
  8. Содержание дисциплины
  9. ПЕРЕЧНЬ ТЕМ ДЛЯ САМОСТОЯТЕЛЬНОГО ИЗУЧЕНИЯ
  10. Математическое программирование
  11. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ
  12. Графический метод решения задач
  13. Прогнозирование эффективного использования производственных площадей
  14. Некоторые экономические задачи, решаемые методами динамического программирования
  15. Метод отсечений. Формулирование верного отсечения. Алгоритм метода
  16. Лекция 4. Использование оптимизационных моделей при принятии решений
  17. Линейные модели оптимизации в управлении
  18. Основные понятия и структура исследования операций
  19. 8.2 Вопросы к модульным тестированиям