Методы оптимальных решений

Методы оптимальных решений

1. ВВЕДЕНИЕ. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ

2. ГЕОМЕТРИЧЕСКОЕ ИСТОЛКОВАНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

3. СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

3.1. Геометрическая интерпретация симплексного метода

3.2. Табличная интерпретация симплексного метода

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

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

Таблица 1.График самостоятельной работы по дисциплине «Методы оптимальных решений»

Содержание	Сроки сдачи	Критерии оценки
1.Изучение теоретического материала
2. Решение заданий кон-трольной работы	За 1,5 месяца до сессии	Каждое задание оцени-вается по десятибалль-ной системе
3. Подготовка к итоговой атт естации	Во время сессии

1. ВВЕДЕНИЕ. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ

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

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

Методы оптимальных решений является одним из разделов исследования операций – прикладного направления кибернетики, используемого для решения практических организационных задач. Задачи математического программирования находят применение в различных областях человеческой деятельности, где необходим выбор одного из возможных образов действий (программ действий).

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

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

Под принятием решений в курсе «Методы оптимальных решений» понимают сложный процесс, в котором можно выделить следующие основные этапы:

1-й этап. Построение качественной модели рассматриваемой проблемы, т. е. выделение факторов, которые представляются наиболее важными, и установление закономерностей, которым они подчиняются. Обычно этот этап выходит за пределы математики.

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

Итак, в результате этих двух этапов формируется соответствующая математическая задача. Причем, второй этап уже требует привлечения математических знаний.

3-й этап. Исследование влияния переменных на значение целевой функции. Этот этап предусматривает владение математическим аппаратом для решения математических, задач, возникающих на втором этапе процесса принятия решения.

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

4-й этап. Сопоставление результатов вычислений, полученных на 3-м этапе, с моделируемым объектом, т. е. экспертная проверка результатов (критерий практики). Таким образом, на этом этапе устанавливается степень адекватности модели и моделируемого объекта в пределах точности исходной информации. Здесь возможны два случая:

1-й случай. Если результаты сопоставления неудовлетворительны (обычная ситуация на начальной стадии процесса моделирования), то переходят ко второму циклу процесса. При этом уточняется входная информация о моделируемом объекте и, в случае необходимости, уточняется постановка задачи (1-й этап); уточняется или строится заново математическая модель (2-й этап); решается соответствующая математическая задача (3-й этап) и, наконец, снова проводится сопоставление (4-й этап).

2-й случай. Если результаты сопоставления удовлетворительны, то модель принимается. Когда речь идет о неоднократном использовании на практике результатов вычислений, возникает задача подготовки модели к эксплуатации. Предположим, например, что целью моделирования является создание календарных планов производственной деятельности предприятия. Тогда эксплуатация модели включает в себя сбор и обработку информации, ввод обработанной информации в ЭВМ, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.

В математическом программировании можно выделить два направления.

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

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

Традиционно в математическом программировании выделяют следующие основные разделы:

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

Нелинейное программирование – целевая функция и ограничения нелинейны. Нелинейное программирование принято подразделять следующим образом:

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

Квадратичное программирование – целевая функция квадратична, а ограничениями являются линейные равенства и неравенства.

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

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

Целью математического программирования является создание, где это возможно, аналитических методов определения решения, а при отсутствии таких методов – создание эффективных вычислительных способов получения приближенного решения.

Наконец, заметим, что наименование предмета – «методы оптимальных решений» – связано с тем, что целью решения задач является выбор программы действий. Рассмотрим более подробно задачу линейного программирования

2. ГЕОМЕТРИЧЕСКОЕ ИСТОЛКОВАНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задача линейного программирования (ЗЛП):

найти вектор X = (x₁,x₂. x_n) максимизирующий линейную форму

и удовлетворяющий условиям:

Линейная функция F называется целевой функцией задачи.

Источник

Методы оптимальных решений

Пример про стирку

В нашей жизни часто возникают задачи, в которых нужно не просто найти «любое решение» (которое, как раз, достаточно легко найти), а «наилучшее» из возможных решений. Приведем пример. Допустим, у нас есть стиральная машина, в которую можно загрузить 6 килограмм белья. И есть наборы белья, весом 1,2,4,5,6 килограмм. Каждый набор необходимо стирать только целиком. Требуется составить программу стирки наилучшим образом.

Тут мы явно видим, что «какое-то» решение найти очень просто. Например, будем брать наборы белья по-порядку:

Номер стирки	Какие наборы берем в стирку	Сколько кг белья стираем в этот раз
1	1+2	3
2	4	4
3	5	5
4	6	6

Итого, мы запустим стиральную машину 4 раза. Решение? Вполне себе решение. И вполне себе можно так и сделать — постирать 4 раза, и задача будет решена.

Но нам-то нужно именно «лучшее» решение. Будет ли наше решение, в котором мы стираем 4 раза лучшим? А вдруг можно так перетасовать белье, чтобы стирать 3 раза? Или даже 2 раза? На самом деле, в 3 раза вполне можно уложиться:

Номер стирки	Какие наборы берем в стирку	Сколько кг белья стираем в этот раз
1	6	6
2	2+4	6
2	1+5	6

Это решение будет оптимальным — ведь за два раза можно постирать максимум $2\cdot6=12$ килограмм, а у нас $1+2+4+5+6=18$.

Задачи оптимизации

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

1. Ограничения — это то, что ограничивает наши решения. Например, в нашей задаче мы не могли постирать все белье сразу, оно не влезло бы в стиральную машину. Поэтому максимальный объем белья в стиральной машине в нашем случае является ограничением. Как правило ограничения записываются в виде равенств или неравенств. В нашем случае это неравенство «количество белья, которое мы можем постирать за раз должно быть МЕНЬШЕ ИЛИ РАВНО 6 килограммам».
2. Целевая функция — это некоторое числовое значение, которое показывает, насколько хорошо мы решили задачу. В нашем случае это количество стирок. Чем оно меньше, тем лучше. То есть, говоря по математически, число стирок, то есть целевую функцию, нужно «минимизировать». Иногда наоборот, целевую функцию необходимо максимизировать, сделать как можно больше — например, если целевая функция это прибыль предприятия от продажи товаров. Предприятие всегда стремится заработать как можно больше.

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

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

Основные типы оптимизационных задач

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

Если задача математического программирования пришла из жизни, то ее решением занимается дисциплина «Исследование операций». Именно она решает задачи из вышеприведенного списка.

Линейное и нелинейное программирование

Кроме этого, задачи математического программирования делятся на два больших класса:

1. Если в задаче как ограничения, так и целевая функция представляют собой линейные функции, то есть, многочлены первой степени, то такая задача называется задачей линейного программирования. Например, если в нашей задаче про стирку мы обозначим количество взятых наборов №1, 2, 3, 4, 5 за $x_1$, $x_2$, $x_3$, $x_4$, $x_5$, то количество итоговых килограмм должно получиться меньше или равно шести. То есть, $x_1+2x_2+4x_3+5x_4+6x_5\leq6$. Это ограничение линейно. Тем не менее, полностью нашу задачу за задачу линейного программирования принять нельзя, так как линейной должна быть еще и целевая функция, кроме того у нас есть неявное условие, что переменные $x_1-x_5$ должны принимать только значения $0$ (мы не берем набор) или $1$ (мы берем набор), а это ограничение нельзя записать в линейной форме.
2. Если в задаче либо оганичения, либо целевая функция (либо и то, и другое) выражены в каком-либо другом виде, то данная задача называется задачей нелинейного программирования. Например, так было бы, если бы наше ограничение имело вид $x_1+3x_2^2+5x_3^3+10x_4^4+\sin(x_5)\geq100$

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

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

Источник