Общая постановка задачи о принятии решения
Процессы принятия решений лежат в основе любой целенаправленной деятельности. В экономике они предшествуют созданию производственных и хозяйственных организаций, обеспечивают их оптимальное функционирование и взаимодействие» в научных исследованиях — позволяют выделить важнейшие научные проблемы, найти способы их изучения, предопределяют развитие экспериментальной базы и теоретического аппарата; при создании новой техники — составляют важный этап в проектировании машин, устройств, приборов, комплексов, зданий, в разработке технологии их построения и эксплуатации; в социальной сфере — используются для организации функционирования и развития социальных процессов, их координации с хозяйственными и экономическими. Оптимальные (эффективные) решения позволяют достигать цели при минимальных затратах трудовых, материальных и сырьевых ресурсов.
В классической математике методы поиска оптимальных решений рассматривают в разделах классической математики, связанных с изучением экстремумов функций, в математическом программировании.
Математическое программирование является одним из разделов исследовании операций – прикладного направления кибернетики, используемого для решения практических организационных задач.
Задачи математического программирования находят применение в различных областях человеческой деятельности, где необходим выбор одного из возможных образов действий (программ действий).
Значительное число задач, возникающих в обществе, связано с управляемыми явлениями, т. е. с явлениями, регулируемыми на основе сознательно принимаемых решений. При том ограниченном объеме информации, который был доступен на ранних этапах развития общества, принималось оптимальное в некотором смысле решение на основании интуиции и опыта, а затем, с возрастанием объема информации об изучаемом явлении, — с помощью ряда прямых расчетов. Так происходило, например, создание календарных планов работы промышленных предприятий.
Совершенно иная картина возникает на современном промышленном предприятии с многосерийным и многономеклатурным производством, когда объем входной информации столь велик, что его обработка с целью принятия определенного решения невозможна без применения современных электронных вычислительных машин. Еще большие трудности возникают в связи с задачей о принятии наилучшего решения.
Под принятием решений в исследовании операций понимают сложный процесс, в котором можно выделить следующие основные этапы:
1-й этап. Построение качественной модели рассматриваемой проблемы, т. е. выделение факторов, которые представляются наиболее важными, и установление закономерностей, которым они подчиняются. Обычно этот этап выходит за пределы математики.
2-й этап. Построение математической модели рассматриваемой проблемы, т. е. запись в математических терминах качественной модели. Таким образом, математическая модель — это записанная в математических символах абстракция реального явления, так конструируемая, чтобы анализ ее давал возможность проникнуть в сущность явления. Математическая модель устанавливает соотношения между совокупностью переменных — параметрами управления явлением.
Этот этап включает также построение целевой функции переменных, т. е. такой числовой характеристики, большему (или меньшему) значению которой соответствует лучшая ситуация с точки зрения принимающего решения.
Итак, в результате этих двух этапов формируется соответствующая математическая задача.
Второй этап уже требует привлечения математических знаний.
3-й этап. Исследование влияния переменных на значение целевой функции.
Этот этап предусматривает владение математическим аппаратом для решения математических, задач, возникающих на втором этапе процесса принятия, решения.
Широкий класс задач управления составляют такие экстремальные задачи, в математических моделях которых условия на переменные задаются равенствами и неравенствами. Теория и методы решения этих задач как раз и составляют содержание математического программирования.
На третьем этапе, пользуясь математическим аппаратом, находят решение соответствующих экстремальных задач. Обратим внимание на то, что задачи математического программирования, связанные с решением практических вопросов, как правило, имеют большое число переменных и ограничений. Объем вычислительных работ для нахождения соответствующих решений столь велик, что весь процесс не мыслится без применения современных электронных вычислительных машин (ЭВМ), а значит, требует либо создания программ для ЭВМ, реализующих те или иные алгоритмы, либо использования уже имеющихся стандартных программ.
4-й этап. Сопоставление результатов вычислений, полученных на 3-м этапе, с моделируемым объектом, т. е. экспертная проверка результатов (критерий практики).
Таким образом,, на этом этапе устанавливается степень адекватности модели и моделируемого объекта в пределах точности исходной информации. Здесь возможны два случая:
1-й случай. Если результаты сопоставления неудовлетворительны (обычная ситуация на начальной стадии процесса моделирования), то переходят ко второму циклу процесса: уточняется входная информация о моделируемом объекте и в случае необходимости уточняется постановка задачи (1-й этап), уточняется или строится заново математическая модель (2-й этап), решается соответствующая математическая задача (3-й этап) и, наконец, снова проводится сопоставление (4-й этап).
2-й случай. Если результаты сопоставления удовлетворительны, то модель принимается. Когда речь идет о неоднократном использовании на практике результатов вычислений, возникает задача подготовки модели к эксплуатации. Предположим, например, что целью моделирования является создание календарных планов производственной деятельности предприятия. Тогда эксплуатация модели включает в себя сбор и обработку информации, ввод обработанной информации в ЭВМ, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.
В математическом программировании можно выделить два направления. К первому, уже вполне сложившемуся направлению — собственно математическому программированию — относятся детерминированные задачи — когда вся исходная информация является полностью определенной.
Ко второму направлению — так называемому стохастическому программированию — относятся задачи, в которых исходная информация содержит элементы неопределенности, либо когда некоторые параметры задачи носят случайный характер с известными вероятностными характеристиками. Так, планирование производственной деятельности зачастую производится в условиях неполной информации о реальной ситуации, в которой будет выполняться план. Или, скажем, когда экстремальная задача моделирует работу автоматических устройств, которая сопровождается случайными помехами. Заметим, что одна из главных трудностей стохастического программирования состоит в самой постановке задач, главным образом из-за сложности анализа исходной информации.
Традиционно в математическом программировании выделяют следующие основные разделы:
Линейное программирование — целевая функция линейна, а множество, на котором ищется экстремум целевой функции, задается системой линейных равенств и неравенств. В свою очередь в линейном программировании существуют классы задач, структура которых позволяет создать специальные методы их решения, выгодно отличающиеся от методов решения задач общего характера. Так, в линейном программировании появился раздел транспортных задач.
Нелинейное программирование — нелинейны целевая функция и ограничения. Нелинейное программирование принято подразделять следующим образом:
Выпуклое программирование — когда выпукла целевая функция (если рассматривается задача ее минимизации) и выпукло множество, на котором решается экстремальная задача.
Квадратичное программирование — когда целевая функция квадратична, а ограничения — линейные равенства и неравенства.
Многоэкстремальные задачи. Здесь обычно выделяют специализированные классы задач, часто встречающихся в приложениях, например, задачи о минимизации на выпуклом множестве вогнутых функций.
Важным разделом математического программирования является целочисленное программирование — когда на переменные накладываются условия целочисленности.
Целью математического программирования является создание, где это возможно, аналитических методов определения решения, а при отсутствии таких методов — создание эффективных вычислительных способов получения приближенного решения.
Наконец, заметим, что наименование предмета — «математическое программирование» — связано с тем, что целью решения задач является выбор программы действий.
Рассмотрим более подробно задачу линейного программирования.
Примеры задач линейного программирования
1.1. Для изготовления трех видов изделий А, В и С используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия для каждого из типов оборудования указаны в таблице 1. В ней же указан общий фонд рабочего времени каждого из типов используемого оборудования, а также прибыль от реализации одного изделия каждого вида.
Таблица 1
| Тип оборудования | Затраты времени (станко-ч) на обработку одного изделия Вида | Общий фонд рабочего времени оборудования (ч) | ||
| А | В | С | ||
| Фрезерное | ||||
| Токарное | ||||
| Сварочное | ||||
| Шлифовальное | ||||
| Прибыль (руб.) |
Требуется определить, сколько изделий, и какого вида следует изготовить предприятию, чтобы прибыль от их реализации была максимальной. Составить математическую модель задачи.
Решение. Предположим, что будет изготовлено единиц изделий вида А, единиц — вида В и единиц — вида С. Тогда для производства такого количества изделий потребуется затратить станко-часов фрезерного оборудования.
Так как общий фонд рабочего времени станков данного типа не может превышать 120, то должно выполняться неравенство
Аналогичные рассуждения относительно возможного использования токарного, сварочного и шлифовального оборудования приведут к следующим неравенствам:
При этом так как количество изготовляемых изделий не может быть отрицательным, то
(1)
Далее, если будет изготовлено единиц изделий вида А, единиц изделий вида В и единиц изделий вида С, то прибыль от их реализации составит
Таким образом, приходим к следующей математической задаче: дана система
(2)
четырех линейных неравенств с тремя неизвестными 1) и линейная функция относительно этих же переменных
(3)
требуется среди всех неотрицательных решений системы неравенств (2) найти такое, при котором функция (3) принимает максимальное значение. Как это сделать, будет показано в дальнейшем.
Линейная функция (3), максимум которой требуется определить, вместе с системой неравенств (2) и условием неотрицательности переменных (1) образуют математическую модель исходной задачи.
Так как функция (3) линейная, а система (2) содержит только линейные неравенства, то задача (1) - (3) является задачей линейного программирования.
1.2. Продукцией городского молочного завода является молоко, кефир и сметана, расфасованное в бутылки. На производство 1 т молока, кефира и сметаны требуется соответственно 1010, 1010 и 9450 кг молока. При этом затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 машино-ч. На расфасовке 1 т. сметаны заняты специальные автоматы в течение 3,25 ч. Всего для производства цельномолочной продукции завод может использовать 136000 кг молока. Основное оборудование может быть занято в течение 21,4 машино-ч, а автоматы по расфасовке сметаны — в течение 16,25 ч. Прибыль от реализации 1 т молока, кефира и сметаны соответственно равна 30, 22 и 136 руб. Завод должен ежедневно производить не менее 100 т молока, расфасованного в бутылки. На производство другой продукции не имеется никаких ограничений.
Требуется определить, какую продукцию и в каком количестве следует ежедневно изготовлять заводу, чтобы прибыль от ее реализации была максимальной. Составить математическую модель задачи.
Решение. Предположим, что молочный завод будет ежедневно производить тонн молока, тонн кефира и тонн сметаны. Тогда ему для изготовления этой продукции необходимо кг молока.
Так как завод может использовать ежедневно не более 136000 кг молока, то должно выполняться неравенство
Аналогичные рассуждения, проведенные относительно возможного использования линий разлива цельномолочной продукции и автоматов по расфасовке сметаны, позволяют записать следующие неравенства:
Так как ежедневно должно вырабатываться не менее 100 т молока, то . Далее, по своему экономическому смыслу переменные и могут принимать только лишь неотрицательные значения: Общая прибыль от реализации тонн молока, тонн кефира и тонн сметаны равна руб. Таким образом, приходим к следующей математической задаче: дана система
(4)
четырех линейных неравенств с тремя неизвестными , , и линейная функция относительно этих же переменных
(5)
требуется среди всех неотрицательных решений системы неравенств (4) найти такое, при котором функция (5) принимает максимальное значение. Так как система (4) представляет собой совокупность линейных неравенств и функция (5) линейная, то исходная задача является задачей линейного программирования.
1.3. На швейной фабрике ткань может быть раскроена несколькими способами для изготовления нужных деталей швейных изделий. Пусть при j-м варианте раскроя 100 м2 ткани изготовляется деталей i-го вида , а величина отходов при данном варианте раскроя равна м2. Зная, что деталей i-го вида следует изготовлять штук, требуется раскроить ткань так, чтобы было получено необходимое количество деталей каждого вида при минимальных общих отходах. Составить математическую модель задачи.
Решение. Предположим, что по j-му варианту раскраивается сотен м2 ткани. Поскольку при раскрое 100 м2 ткани по j-му варианту получается деталей i-го вида, по всем вариантам раскроя из используемых тканей будет получено
деталей i-го вида. Так как должно быть изготовлено деталей данного вида, то
Общая величина отходов по всем вариантам раскроя ткани составит
Таким образом, приходим к следующей математической задаче: найти минимум функции
(6)
при условии, что ее переменные удовлетворяют системе уравнений
(7)
и условию неотрицательности
Сформулированная задача является задачей линейного программирования, так как функция (6) линейная, а система (7) содержит только лишь линейные уравнения.