Постановка задачи целочисленного программирования - раздел Информатика, РАЗДЕЛ 1.МЕСТО И РОЛЬ ПРОЦЕССОВ ПОДГОТОВКИ И ПРИНЯТИЯ РЕШЕНИЙ В ОБЩЕЙ ТЕХНОЛОГИИ УПРАВЛЕНИЯ СЛОЖНЫМИ ОРГАНИЗАЦИОННО-ТЕХНИЧЕСКИМИ СИСТЕМАМИ (СОТС
Первые Упоминания О Линейных Уравнениях Возникли Ещё За Неско...
Первые упоминания о линейных уравнениях возникли ещё за несколько веков до нашей эры.
В Древней Греции Диофант (II-III в.) формулирует уравнения, в которых искомые переменные – целые. Например, для уравнения первой степени, а0+а1х1=0, где а0, а1 – целые, решение х1 = а0/а1 – целое, если а0 делится на а1 без остатка, т.е. такое уравнение не всегда разрешимо в целых числах. Из двух уравнений 3х1–27=0 и 5х2+21=0 только первое имеет целое решение: х1=27/3=9, а второе – нет, так как х2=–21/5.
Для уравнения с двумя неизвестными: а1х1+а2х2=0, где а1, а2 – целые, решение будет х1=–(а2/а1)х2. Например,
10х1–5х2 = 0 или х1=0,5х2. (1)
Из этого примера можно сделать следующие выводы: уравнение имеет бесчисленное множество решений, так как п > т; решение – целое, если х2 – чётное.
Для того, чтобы из множества допустимых решений выбрать одно – оптимальное, необходимо, как нам уже известно, добавить к условию (1) целевую функцию. Задачи оптимизации, в которых решение должно быть в целых числах, называют задачами целочисленного программирования. Если в этой задаче целевая функция и ограничения – линейные зависимости, то её называют целочисленной задачей линейного программирования; если же хотя бы одна зависимость будет нелинейной, то такая задача формулируется как целочисленная задача нелинейного программирования.
Большинство практических задач принятия решения сводятся, как правило, к целочисленным задачам линейного программирования.
Если к условию (1) добавить такие, например, граничные условия:
2 £ х1 £8; 1£ х2 £ 3,
то можно видеть, что такая система решения не имеет. Отсюда следует, что задача целочисленного программирования не всегда имеет решения, т.е. она не совместна.
Под целочисленным или дискретным программированием понимают такие задачи (обычно линейные), в которых искомые переменные по смыслу могут принимать только целые значения: число рабочих, разделяемых по рабочим местам, количество единиц оборудования, устанавливаемых на заданной площади и т.п.
Аналитическая задача целочисленного программирования формулируется:
(2)
Система (2) с точки зрения зависимостей ничем не отличается от задачи линейного программирования. Единственное отличие заключается в том, что в ней есть строка , которая оказывает существенное влияние на решение задачи и значительно его усложняет. Число целочисленных переменных может удовлетворять одному из двух вариантов. Если , где — общее число всех переменных, то в ответе все переменные должны быть только целыми. В таком случае задачу называют полностью целочисленной. Если , в ответе только переменных должны быть целыми, а остальные в заданных граничных условиях могут принимать любые значения. Иными словами, в ответе должны быть целые (но не все). В этом случае задачу называют частично целочисленной.
Следует отметить, что для решения задачи все целочисленные переменные обязательно должны иметь верхнюю границу.
Решение целочисленных и непрерывных задач оптимизации имеет принципиальные различия. Суть их заключается в следующем. Непрерывные задачи решают симплекс-методом с применением так называемых симплекс-таблиц. Каждой итерации соответствует своя симплекс-таблица. Есть признаки, с помощью которых по симплекс-таблицу можно получить ответы на вопросы: имеет ли вообще задача допустимое решение; является ли решение на данной итерации допустимым; является ли решение на данной итерации оптимальным.
Если задача имеет решения, то она решается до тех пор, пока не будут удовлетворены признаки этих решений. При этом решение является допустимым, если удовлетворяется один признак, и оптимальным, если удовлетворяются оба признака. К сожалению, для целочисленных задач таких признаков нет. Поэтому по задаче нельзя судить, во-первых, имеет ли она вообще допустимое решение и, во-вторых, является ли полученное допустимое решение оптимальным.
Некоторые вопросы, связанные с решением целочисленных задач, рассмотрим на таком примере:
Решим эту задачу графически. Графическое решение целочисленной задачи включает следующие этапы: графическое решение непрерывной задачи; наложение требований целочисленности; анализ полученных результатов. Графическое решение непрерывной задачи показано на рис. 3.4.1.
Рис. 3.4.1.
Требование целочисленности переменных состоит в том, что решением задачи могут быть только точки, находящиеся на пересечении целочисленных значений и .
Из рис. 3.4.1 видно, что оптимальным решением задачи без учета требований целочисленности являются координаты точки , приведенные в табл. 3.4.1. Как следует из этой таблицы, значения и в точке требованиям целочисленности не удовлетворяют. Естественная попытка получить целочисленное решение сводится к округлению непрерывных значений. Округленные координаты, принадлежащие точке , оказываются за пределами ОДР, т. е. являются недопустимым решением. Предположение, что решение недопустимое, потому что округление было произведено в большую сторону, неверно. В точке координаты также округлены в большую сторону, а решение допустимое. И, наконец, из рис. 3.4.1 видно, что оптимальным решением будут координаты точки , которые не являются ближайшими к непрерывному оптимальному решению.
Концептуальная модель принятия решений
Анализ многочисленных публикаций по различным аспектам проблемы выбора показывает, что в настоящее время наметилась прогрессивная тенденция к интеграции различных научных направлени
Постановка задачи линейного программирования
Значительная часть задач принятия решения – это задачи распределения ресурсовмежду объектами.
Пусть имеется т видов ресурсов, каждый i
Двойственные задачи линейного программирования
Каждой задаче ЛП можно некоторым образом сопоставить другую задачу ЛП, называемую двойственной по отношению к исходной (прямой):
Прямая задача (ПЗ)
Обобщенный алгоритм решения задач НЛП
Эффективное решение различных задач нелинейного программирования может быть осуществлено на основе учета конкретных особенностей этих задач. При этом под эффективностью того или иного алгоритма, ка
Аналитические методы решения задач НЛП
В некоторых случаях задачи НЛП удается решить аналитически. Это, в частности, удается в том случае, если ЦФ и ОДА являются выпуклыми. Обобщенный алгоритм решения задачи НЛП включает в себя следующи
Численные методы решения задач НЛП
В качестве r(xk) используется направление, в котором наиболее сильно возрастает целевая функция. Это направление задается градиентом функции ÑF(xk). Суть метода состоит
Постоянный шаг.
Задается hk = h = const, при этом должно выполняться условие
F(xk+1) = F(xk + hkÑF(xk)) > F(xk).
Пусть
Наискорейший подъем.
Если подставить в выражение для F(x) значение x=xk+1 в соответствии с (1), то получим выражение F(xk+hkÑF(xk)), как функцию от величины шага. След
Функции Лагранжа
Исторически первым способом сведения задачи с ограничениями к задаче безусловной оптимизации явилось использование функции Лагранжа L(x,m)
L(x, m) = f(x) + mт(b - j(x)) = f(x) +
Штрафные функции
Исходная задача условной оптимизации сводится к последовательности задач безусловной оптимизации функций
Fk(x, m) = f(x) - Sk(x, mk), k = 1,2,3,....
Методы прямой условной оптимизации
Методы прямой условной оптимизации предназначены для непосредственного решения задачи выпуклого программирования в условиях ограничений, описывающих множество допустимых решений D.
Итак, п
Метод условного градиента
Существо метода условного градиента состоит в том, что, если известна некоторая точка xkÎD, то направление возрастания целевой функции может задаваться некоторой внутренней или кра
Характерные особенности задач многокритериального выбора
Реальные задачи выбора, возникающие на практике, чрезвычайно разнообразны, но всех их объединяет общая схема поиска решения, суть которой состоит в формировании совокупности операци
Принцип В.Парето в задачах многокритериального выбора
В п. 4.1 было установлено, что для корректного решения задач многокритериального выбора необходимо в исходную постановку задачи (4.1)‑(4.2) привнести дополнительную информацию
Методы построения множества Парето
Приведенные в п.4.2.2 свойства множества Парето могут быть использованы для построения (исследования) данного множества (либо его подмножеств) или определения его характеристик в ко
Принятие решений в условиях стохастической среды
Постановка задач принятия решений в условиях стохастической среды имеет вид
(D(w), f(w)), wÎW,
где D(w) - множество допустимых альтернатив, f(w) - целевая функция.
Методы детерминизации.
При решении конкретных задач выбора на вероятностных структурах часто вводится предположение о том, что задание целевой функции f(w) и ограничивающих отношений ri(w), i=1,...,m, определя
Методы имитационной оптимизации.
В методах имитационной оптимизации (прямых методах стохастического выбора) не производится преобразование задачи к ее детерминированному эквиваленту. Суть данных методов заключается в том, что гене
Принятие решений в условиях целенаправленной среды
Принятие решений в условиях целенаправленной среды связано с тем, что известна цель среды, в соответствии с которой она выбирает свои состояния и которую преследует в своих действиях. Эти действия
Постановка задач игрового выбора.
Рассмотрим формализованное представление задачи принятия решений в условиях целенаправленной среды. Обобщенную задачу принятия решения в условиях неопределенности можно записать в виде
(D
Матричные игры. Чистые и смешанные стратегии.
Простейшим вариантом игры является антагонистическая игра, в которой противодействуют две оперирующих стороны (2 игрока), при этом множества различных альтернатив из которых они выбирают решения ко
Методы нахождения оптимальных смешанных стратегий.
Процедура нахождения оптимальных чистых или смешанных стратегий соответствует выявлению рациональной линии поведения противников в конфликтной ситуации, описываемой игровой моделью. Поэтому такую п
Принятие решений в условиях неизвестной среды
В случае неизвестной среды нет достаточных оснований для предположений о том, какие значения будут принимать параметры, характеризующие состояние среды на рассматриваемом временном интервале. При э
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
(2)
, которая оказывает существенное влияние на решение задачи и значительно его усложняет. Число целочисленных переменных 
может удовлетворять одному из двух вариантов. Если 
, где 
— общее число всех переменных, то в ответе все переменные должны быть только целыми. В таком случае задачу называют полностью целочисленной. Если 
, в ответе только 
переменных должны быть целыми, а остальные в заданных граничных условиях могут принимать любые значения. Иными словами, в ответе должны быть целые (но не все). В этом случае задачу называют частично целочисленной.
и 
.
, приведенные в табл. 3.4.1. Как следует из этой таблицы, значения 
, оказываются за пределами ОДР, т. е. являются недопустимым решением. Предположение, что решение недопустимое, потому что округление было произведено в большую сторону, неверно. В точке 
, которые не являются ближайшими к непрерывному оптимальному решению.
Новости и инфо для студентов