Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Целочисленное программирование

Читайте также:
  1. C. ПРОГРАММИРОВАНИЕ БРЕЛКА С ДИСПЛЕЕМ
  2. Глава 1. ПРОГРАММИРОВАНИЕ, ЦЕЛЕПОЛАГАНИЕ И САМОКОНТРОЛЬ. РИТУАЛЫ, ПРАВИЛА ИГРЫ И РОЛИ
  3. ГЛАВА 5. Программирование подсознания
  4. Мужское программирование
  5. Оптимизация и математическое программирование
  6. Программирование
  7. ПРОГРАММИРОВАНИЕ

 

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

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

Многие ситуации требуют задания логических данных, принимающих вид «да/нет», «использовать/не использовать», «назначить/не назначить». Очевидно, что эти решения являются дискретными, имеющими только два количественных значения. Они могут быть смоделированы бинарными переменными, которые приобретают значение 0 или 1. Примеры дискретных решений возникают, когда разработчики сталкиваются с выбором из конечного множества альтернатив, плановики ищут оптимальную последовательность действий, при транспортном планировании отыскиваются маршрутизации транспортных средств, обеспечивающие минимальные затраты - все это Когда оптимизационные модели содержат как целые, так и непрерывные переменные их называют смешанными. Такие модели представляют реальные ситуации, но наряду с адекватностью моделирования приходится сталкиваться с большими вычислительными трудностями. Лишь сравнительно небольшие задачи с целочисленными переменными могут быть решены оптимально. На первый взгляд это может показаться непонятным, учитывая возможность решать задачи линейного программирования с большим количеством переменных. Однако дискретный характер переменных порождает комбинаторный рост альтернатив. В худшем случае, для подтверждения оптимальности должно быть перебрано большинство из этих решений. При возрастании количества целых переменных в задаче, найти оптимальное решение становится очень сложно, или даже невозможно. В таких случаях приходится использовать эвристические методы, которые не гарантируют оптимальности найденного решения, но обеспечивают некоторое приемлемое приближение к оптимуму.

Рассмотрим процесс моделирования задач оптимизации с целыми переменными. Введем некоторые новые термины.


Дата добавления: 2015-07-15; просмотров: 113 | Нарушение авторских прав


Читайте в этой же книге: Процесс исследования операций | Моделирование на основе системного подхода | Терминология | Этапы системного анализа-синтеза | Классификация систем и инструментов аналитической деятельности | Терминология | Решение и анализ задач ЛП графическим методом | Укрупненный алгоритм решения графическим методом | Пример решения | Анализ чувствительности к изменениям правых частей ограничений |
<== предыдущая страница | следующая страница ==>
Анализ чувствительности к изменению коэффициентов ЦФ| Терминология

mybiblioteka.su - 2015-2024 год. (0.006 сек.)