prosdo.ru
добавить свой файл
1

Критерии оптимальности

Правильный выбор критериев играет существенную роль в выборе оптимального решения. В теории принятия решений не найдено общего метода выбора критериев оптимальности. В основном руководствуются опытом или рекомендациями.[4] Наиболее изучен вопрос для финансово-экономических задач, в которых зачастую применяется единственный критерий — максимум показателя эффективности, прибыли, либо максимум рентабельности, либо минимум срока окупаемости и т. п. Применение для технических задач только одного критерия (например, максимум уровня безопасности, минимум потребления энергии, минимум экологического ущерба) часто приводит к абсурдным результатам, выходящим за область допустимых решений, поэтому обычно сочетается с экономическими критериями (например, минимум стоимости или максимум дохода).

Большие сложности вызывают «неисчисляемые» критерии оптимальности, которые касаются, например, гуманитарных вопросов, художественного впечатления, изменения ландшафта и т. п. (например, максимум удобства, красоты). Для учёта таких критериев могут применяться экспертные оценки.


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

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

Иногда общим методом для многокритериальных задач называют оптимальность по Парето[5], которое позволяет найти ряд «неулучшаемых» решений, однако этот метод не гарантирует глобальной оптимальности решений. Менее известна «оптимальность по Слейтеру».

[править] Нормирование критериев

Для удобства и однозначности восприятия критерии Ki (где i = 1,…, m; m — число критериев) нормируют, то есть обычно приводят к следующему виду:


  • Ki ≥ 0;

  • критерии Ki убывают с улучшением решения, с ростом качества проектируемого объекта (встречается и обратное требование).

Например, минимальная цена, потери энергии (равны 1- КПД);

  • предпочтительно критерии приводить к безразмерному виду.

например, относительная цена (по отношению к цене самого дорогого варианта);

  • как следствие, наилучшее значение критерия равно нулю. Решения, у которого все критерии нулевые (Ki = 0), соответствует идеальному конечному результату (ИКР), когда объекта нет, но его функция выполняется.

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.


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

Содержание


 [показать

  • 1 История

  • 2 Задачи

  • 3 Примеры задач

    • 3.1 Максимальное паросочетание

    • 3.2 Максимальный поток

    • 3.3 Транспортная задача

    • 3.4 Игра с нулевой суммой

  • 4 Алгоритмы решения

  • 5 См. также

  • 6 Примечания

  • 7 Литература

  • 8 Ссылки

[править] История


Математические исследования отдельных экономических проблем, математическая формализация числового материала проводилась ещё в XIX веке. При математическом анализе процесса расширенного производства использовались алгебраические соотношения, анализ их проводился с помощью дифференциального исчисления. Это давало возможность получить общее представление о проблеме.

Развитие экономики потребовало количественных показателей, и в 1920 годы был создан межотраслевой баланс (МОБ). Он то и послужил толчком в деле создания и исследования математических моделей. Разработка МОБ в 19241925 годах в СССР повлияла на работы экономиста и статистика Василия Васильевича Леонтьева. Он разработал межотраслевую модель производства и распределения продукции.


В 1938 году Леонид Витальевич Канторович в порядке научной консультации приступил к изучению чисто практической задачи по составлению наилучшего плана загрузки лущильных станков (фанерный трест). Эта задача не поддавалась обычным методам. Стало ясно, что задача не случайная.[1]

В 1939 году Леонид Витальевич Канторович опубликовал работу «Математические методы организации и планирования производства», в которой сформулировал новый класс экстремальных задач с ограничениями и разработал эффективный метод их решения, таким образом были заложены основы линейного программирования.

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

В 1949 году американский математик Джордж Бернард Данциг разработал эффективный метод решения задач линейного программирования (ЗЛП) — симплекс-метод.[1]

Термин «программирование» нужно понимать в смысле «планирования» (один из переводов англ. programming). Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.


Метод внутренних точек был впервые упомянут И. И. Дикиным в 1967 году.[2]

[править] Задачи


Общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида[3]:



задача в которой фигурируют ограничения в форме неравенств, называется — основной задачей линейного программирования (ОЗЛП)

,

.

Задача линейного программирования будет иметь канонический вид, если в общей задаче вместо первой системы неравенств имеет место система уравнений с ограничениями в форме равенства[4]:

,

Основную задачу можно свести к канонической путём введения дополнительных переменных.

Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств[5].

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

[править] Примеры задач

[править] Максимальное паросочетание

Рассмотрим задачу о максимальном паросочетании в двудольном графе: есть несколько юношей и девушек, причём для каждых юноши и девушки известно, симпатичны ли они друг другу. Нужно поженить максимальное число пар со взаимной симпатией.

Введём переменные , которые соответствуют паре из -того юноши и -той девушки и удовлетворяют ограничениям:







с целевой функцией . Можно показать, что среди оптимальных решений этой задачи найдётся целочисленное. Переменные, равные 1, будут соответствовать парам, которые следует поженить.

[править] Максимальный поток


Пусть имеется граф (с ориентированными рёбрами), в котором для каждого ребра указана его пропускная способность. И заданы две вершины: сток и исток. Нужно указать для каждого ребра, сколько через него будет протекать жидкости (не больше его пропускной способности) так, чтобы максимизировать суммарный поток из истока в сток (жидкость не может появляться или исчезать во всех вершинах, кроме стока и истока).

Возьмём в качестве переменных  — количество жидкости, протекающих через -тое ребро. Тогда


,

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

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

Эти задачи могут быть решены быстрее, чем общими алгоритмами решения задач линейного программирования, за счёт особой структуры уравнений и неравенств.

[править] Транспортная задача

Имеется некий однородный груз, который нужно перевести с складов на заводов. Для каждого склада известно, сколько в нём находится груза , а для каждого завода известна его потребность в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния от -го склада до -го завода известны). Требуется составить наиболее дешёвый план перевозки.


Решающими переменными в данном случае являются  — количества груза, перевезённого из -го склада на -й завод. Они удовлетворяют ограничениям:





Целевая функция имеет вид: , которую надо минимизировать.

[править] Игра с нулевой суммой


Есть матрица размера . Первый игрок выбирает число от 1 до , второй — от 1 до . Затем они сверяют числа и первый игрок получает очков, а второй очков ( — число, выбранное первым игроком,  — вторым). Нужно найти оптимальную стратегию первого игрока.

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

,

,

(),

в которой нужно максимизировать функцию . Значение в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае.

[править] Алгоритмы решения

Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования (ЛП) является симплекс-метод. Несмотря на то, что симплекс-метод является достаточно эффективным алгоритмом, показавшим хорошие результаты при решении прикладных задач ЛП, он является алгоритмом с экспоненциальной сложностью. Причина этого состоит в комбинаторном характере симплекс-метода, последовательно перебирающего вершины многогранника допустимых решений при поиске оптимального решения.


Первый полиномиальный алгоритм, метод эллипсоидов, был предложен в 1979 году советским математиком Л. Хачияном, разрешив таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, некомбинаторную, природу, нежели симплекс-метод. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее, сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП — методов внутренней точки, первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году. Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования, разработанные в 1960-х годах Фиако (Fiacco) и МакКормиком (McCormick).

Постановка задачи и оптимизация модели с помощью процедуры поиска решения

javascript:AlterAllDivs('block');ПоказатьвсеПоказатьвсеПоказать все

javascript:AlterAllDivs('none');СкрытьвсеСкрытьвсеСкрыть все


  1. В меню Сервис выберите команду Поиск решения.

  2. Если команда Поиск решения отсутствует в меню Сервис, установите надстройку (Надстройка. Вспомогательная программа, служащая для добавления в Microsoft Office специальных команд или возможностей.) «Поиск решения».

javascript:ToggleDiv('divExpCollAsst_767778636')Инструкции

  1. В меню Сервис выберите команду Надстройки.

  2. Нажмите кнопку Обзор, чтобы найти надстройку (Надстройка. Вспомогательная программа, служащая для добавления в Microsoft Office специальных команд или возможностей.), которой нет в окне Список надстроек.

  3. Установите в окне Список надстроек флажок той надстройки, которую необходимо загрузить, а затем нажмите кнопку OK.

  4. Следуйте инструкциям программы установки, если они имеются.

  1. В поле Установить целевую ячейку введите ссылку на ячейку (Ссылка на ячейку. Координаты, определяющие расположение ячейки на листе. Например, B3 представляет ссылку на ячейку, находящуюся на пересечении столбца B и строки 3.) или имя (Имя. Слово или строка знаков, представляющие ячейку, диапазон ячеек, формулу или константу. Понятные имена, такие как «Продукты», используют для ссылок на диапазоны, названия которых трудно запомнить, например, Продажи!C20:C30.) конечной ячейки. Конечная ячейка должна содержать формулу (Формула. Совокупность значений, ссылок на другие ячейки, именованных объектов, функций и операторов, позволяющая получить новое значение. Формула всегда начинается со знака равенства (=).).

  2. Выполните одно из следующих действий:

  • чтобы максимизировать значение конечной ячейки путем изменения значений влияющих ячеек, установите переключатель в положение максимальному значению;
  • чтобы минимизировать значение конечной ячейки путем изменения значений влияющих ячеек, установите переключатель в положение минимальному значению;


  • чтобы установить значение в конечной ячейке равным некоторому числу, установите переключатель в положение значению и введите в соответствующее поле требуемое число.

  1. В поле Изменяя ячейки введите имена или ссылки на изменяемые ячейки, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с конечной ячейкой. Допускается задание до 200 изменяемых ячеек.

  2. Чтобы автоматически найти все ячейки, влияющие на формулу модели, нажмите кнопку Предположить.

  3. В поле Ограничения введите все ограничения (Ограничения. Ограничения на значения изменяемых ячеек, конечных ячеек или других ячеек, прямо или косвенно связанных друг с другом, задаваемые при постановке задачи.), накладываемые на поиск решения.

javascript:ToggleDiv('divExpCollAsst_834280828')Инструкции

javascript:ToggleDiv('divExpCollAsst_402672653')Добавление ограничения

  1. В разделе Ограничения диалогового окна Поиск решения нажмите кнопку Параметры.

  2. В поле Ссылка на ячейку введите адрес (Ссылка на ячейку. Координаты, определяющие расположение ячейки на листе. Например, B3 представляет ссылку на ячейку, находящуюся на пересечении столбца B и строки 3.) или имя (Имя. Слово или строка знаков, представляющие ячейку, диапазон ячеек, формулу или константу. Понятные имена, такие как «Продукты», используют для ссылок на диапазоны, названия которых трудно запомнить, например, Продажи!C20:C30.) ячейки, на значение которой накладываются ограничения.
  3. Выберите из раскрывающегося списка условный оператор ( <=, =, >=, цел или двоич ), который должен располагаться между ссылкой и ограничение (Ограничения. Ограничения на значения изменяемых ячеек, конечных ячеек или других ячеек, прямо или косвенно связанных друг с другом, задаваемые при постановке задачи.). Если выбрано цел, в поле Ограничение появится «целое». Если выбрано двоич, в поле Ограничение появится «двоичное».


  4. В поле Ограничение введите число, ссылку на ячейку или ее имя либо формулу (Формула. Совокупность значений, ссылок на другие ячейки, именованных объектов, функций и операторов, позволяющая получить новое значение. Формула всегда начинается со знака равенства (=).).

  5. Выполните одно из следующих действий.

  • Чтобы принять ограничение и приступить к вводу нового, нажмите кнопку Добавить.

  • Чтобы принять ограничение и вернуться в диалоговое окно Поиск решения, нажмите кнопку OK.

Примечания

  • Условные операторы типа цел и двоич можно применять только при наложении ограничений на изменяемые ячейки.

  • Флажок Линейная модель в диалоговом окне Параметры поиска решения позволяет задать любое количество ограничений. При решении нелинейных задач на значения изменяемых ячеек можно наложить более 100 ограничений, в дополнение к целочисленным ограничениям на переменные.

javascript:ToggleDiv('divExpCollAsst_757164752') Изменение и удаление ограничений

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

  2. Выберите команду Изменить и внесите изменения либо нажмите кнопку Удалить.

  1. Нажмите кнопку Выполнить и выполните одно из следующих действий:

  • чтобы сохранить найденное решение на листе, выберите в диалоговом окне Результаты поиска решения вариант Сохранить найденное решение;

  • чтобы восстановить исходные данные, выберите вариант Восстановить исходные значения.

javascript:ToggleDiv('divExpCollAsst_736256710')Совет

Чтобы прервать поиск решения, нажмите клавишу ESC. Лист Microsoft Excel будет пересчитан с учетом найденных значений влияющих ячеек.