Состав типичных задач, решаемых методами линейного программирования

Типичные задачи линейного программирования выглядят так:

«Найти значения неизвестных, обеспечивающие максимум (или минимум) некоторой критериальной функции, представляющей собой линейную комбинацию значений неизвестных».

При этом:

- в задачу линейного программирования входит еще система ограничений для самих неизвестных и/или линейных комбинаций этих неизвестных;

- линейная комбинация неизвестных в критериальной функции обычно включает в себя «свободный член», который не зависит от значений неизвестных.

Таким образом, и критериальная функция и ограничения носят линейный характер, что и определяет название этого класса задач.

Чаще всего задача линейного программирования ставится в отношении поиска либо максимума, либо минимума критериальной функции и лишь значительно реже – и того и другого.

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

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

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

(а) решение существует и является единственным;

(б) имеется бесконечно много решений, обеспечивающих экстремальное (максимум или минимум) значение критериальной функции;

(в) не существует ни одного решения

Вариант «а» является наиболее типичным (распространенным) для задач линейного программирования.

Вариант «б» встречается как исключение. В этом случае лицо принимающее решение (ЛПР) выбирает его из числа вариантов с оптимальным значением критериальной функции по некоторому дополнительному критерию.

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

Если же речь идет о реальной задаче, постановка которой исходит от ЛПР, то обычно бывает нужно пересмотреть систему ограничений - с тем, чтобы она стала совместной.

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

Мы поможем в написании ваших работ!