Лабораторная работа 1

Лабораторная работа №1. Решение задач линейного программирования графическим и симплекс-методом (6 час)

Цель работы:

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

Требования к содержанию, оформлению и порядку выполнения

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

Общая постановка задачи

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

графический метод решения:

Решить симплекс-методом следующие задачи ЛП.

Написать программы по каждому типу задач (язык программирования любой).

Теоретическая часть

Принятие решений представляет собой особый вид человеческой деятельности, который состоит в обоснованном выборе наилучшего в какомто смысле варианта или вариантов из имеющихся возможных. По-английски: decision making –«делание» или «создание» решения. Задачи принятия решений часто отождествляются с задачами выбора – одними из самых распространенных задач, с которыми человек сталкивается в своей деятельности.

Цели и Принятие решений представляет собой особый вид человеческой деятельности, который состоит в обоснованном выборе наилучшего в каком-то смысле варианта или вариантов из имеющихся возможных. По-английски: decision making –«делание» или «создание» решения. Задачи принятия решений часто отождествляются с задачами выбора – одними из самых распространенных задач, с которыми человек сталкивается в своей деятельности.

Формальные методы принятия решения могут оказаться полезными при следующих обстоятельствах.

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

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

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

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

•Имеется человек или группа лиц, которые заинтересованы в разрешении проблемы, имеют полномочия для выбора того или иного варианта решения и несут ответственность за выполнение принятого решения.

Участники процесса принятия решения выполняют различные функции.

Лицо, принимающее решение (ЛПР) или действующее лицо, по-

английски decision maker (DM) или actor – человек или группа лиц, которые фактически осуществляют выбор предпочтительного решения. Обычно это руководитель или группа компетентных специалистов, обладающих соответствующими знаниями и опытом деятельности, наделенных необходимыми полномочиями и несущих ответственность за реализацию принятого решения.

Владелец проблемы (ВП) – человек или группа лиц, имеющих основания

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

Активные группы (АГ) – формальные или неформальные объединения людей, которые имеют общие интересы по отношению к проблеме, требующей решения, и стремятся оказать влияние на процесс выбора с тем, чтобы добиться нужного им результата. Обычно владелец проблемы принадлежит к одной из основных активных групп. Интересы разных активных групп могут, как совпадать, так и отличаться друг от друга, а также от интересов и ЛПР.

Эксперты, от лат. expertus, т.е. опытный (Э) – компетентные специалисты, которые профессионально разбираются в решаемой проблеме, обладают необходимой информацией о проблеме и отдельных её аспектах, но не несут ответственности за принятое решение и его реализацию.

Консультанты по принятию решений (К) – компетентные специалисты,

которые оказывают помощь ЛПР и владельцу проблемы в организации процесса её решения, в правильной постановке задачи принятия решения,

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

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

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

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

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

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

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

Задача принятия решения

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

D = {F, A, X, G, P},

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

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

X – совокупность признаков (атрибутов, параметров), описывающих варианты и их отличительные особенности – объективные и, как правило, измеряемые показатели, которые характеризуют свойства вариантов; субъективные оценки по специально отобранным или сконструированным критериям, отражающим важные для участников выбора черты вариантов.

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

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

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

Факторы, характеризующие проблемную ситуацию и влияющие на формальную постановку задачи принятия решения и средства её решения:

•управляемые факторы, выбор которых зависит от ЛПР, – поставленные цели, варианты (альтернативы) их достижения, субъективные оценки вариантов и степени достижения целей;

•неуправляемые факторы, не зависящие от ЛПР, – объективные признаки вариантов, отчасти ограничения на выбор возможных вариантов;

•определенные или детерминированные факторы – неслучайные факторы с известными и/или заданными точными характеристиками;

•вероятностные или стохастические факторы – «хорошие» случайные факторы с известными и/или заданными неточными характеристиками;

•неопределенные или неизвестные факторы – «плохие» случайные факторы с нечётко известными и/или заданными характеристиками и иногда

сизвестной областью изменения их значений. В их числе:

–неопределенность природы, то есть факторы людям попросту неизвестные или от них не зависящие;

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

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

Пример. Покупка товара как задача принятия решения.

Формулировка проблемы – описание требуемого товара: продукты повседневного спроса, или костюм, или автомобиль; что требуется: выбрать самый лучший товар, либо рассортировать все товары по каким-то группам.

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

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

Определённые факторы – цена и дата изготовления товара; вероятностные факторы – потребительские характеристики товара; неизвестные факторы – вкусовые или эксплуатационные качества товара.

Ограничения – цена товара («не дороже, чем»), производитель («только отечественные», какая-то конкретная фирма).

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

Классификация задач принятия решений

По регулярности проблемной ситуации

•новые, уникальные задачи, никогда ранее не возникавшие;

•повторяющиеся задачи, регулярно встречающиеся на практике.

По виду окончательного результата (типовые задачи):

•выделить один или несколько лучших вариантов (альтернатив);

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

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

Варианты решения проблемы различаются:

•по количеству – немного (единицы, десятки), много (сотни и тысячи), бесконечно много;

•по наличию в процессе решения задачи – варианты, заданные заранее при формулировке задачи; варианты, конструируемые в процессе решения задачи; варианты, появляющиеся после окончания процесса решения;

•по степени взаимной зависимости – независимые варианты,

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

По числу лиц, обладающих полномочиями для принятия решения:

•индивидуальные решения (имеется единственное ЛПР);

•коллективные или групповые решения (существуют несколько ЛПР, которые имеют совпадающие или противоречивые интересы, преследуют свои цели и действуют независимо друг от друга);

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

По роли ЛПР в процессе принятия решения:

•выбор производится без участия ЛПР;

•ЛПР принимает участие только на заключительном этапе выбора;

•выбор осуществляется при непосредственном участии ЛПР в основных этапах процесса решения.

В зависимости от способа представления предпочтений ЛПР:

•задачи целостного выбора;

•задачи критериального выбора (однокритериальные и многокритериальные, с независимыми и зависимыми критериями).

По особенностям используемой информации:

•по виду информации – количественная (числовая), качественная (словесная или вербальная), смешанная;

•по наличию явной зависимости информации от времени – статическая

идинамическая;

•по характеру информации – объективная, полученная путем измерений и/или расчетов по общепринятым методикам, и субъективная, полученная от человека (ЛПР, эксперта);

•по степени определенности информации – детерминированная,

вероятностная (стохастическая), неопределенная. В первом случае говорят о принятии решения в условиях определенности, во втором – в условиях вероятностной неопределенности или риска, в третьем – в условиях полной неопределенности.

Структуризация проблемной ситуации

Степень структуризации или формализации проблемной ситуации

(Г.Саймон, А.Ньюэлл, 1958) – различное сочетание количественной и качественной, объективной и субъективной информации, описывающей проблему.

• Хорошо структурируемые или хорошо формализуемые проблемы

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

• Слабо структурируемые или плохо формализуемые проблемы

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

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

• Неструктурируемые или неформализуемые проблемы

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

Предпочтения ЛПР

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

Реляционная модель предпочтений, основанная на бинарных отношениях.

•Нейтральная или неопределенная предпочтительность вариантов

Ai≈Aj характеризуется симметричным отношением (сходство, эквивалентность; несходство, противоположность; несравнимость) и свидетельствует о некоторой равноценности, либо неопределенной ценности

обоих вариантов для ЛПР, например: «Варианты Aiи Aj похожи», «Варианты Aiи Aj несопоставимы».

•Нестрогая или слабаяпредпочтительность вариантов Ai Aj задаётся антисимметричным, либо рефлексивным и полным отношением (нестрогое превосходство, нестрогий порядок, предпорядок) и отражает как

различимость, так и одинаковость вариантов для ЛПР: «Вариант Аi не хуже, чем вариант Aj», «Вариант Аi,по крайней мере, такой же, как и вариант Aj». Первая формулировка допускает, чтобы вариант Аi был как лучше, так и равноценен варианту Aj. Вторая формулировка разрешает, чтобы оба варианта Аi и Aj были одинаково приемлемыми («хорошими»), либо одинаково неприемлемыми («плохими»).

•Строгая или сильная предпочтительность вариантов Ai Aj

выражается асимметричным отношением (строгое превосходство, строгий порядок) и интерпретируется как явно выраженное различие вариантов:

«Вариант Ai определенно лучше варианта Aj».

При выборе из пары вариантов Aiи Aj при нейтральной предпочтительности (Ai≈Aj) выбираются оба варианта: и Ai, и Aj; при

нестрогой предпочтительности (Ai Aj) выбирается либо вариант Ai, либо оба варианта вместе; при строгой предпочтительности (Ai Aj) выбирается только первый вариант Ai и не выбирается второй вариант Aj.

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

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

Оценка и сравнение вариантов

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

•Номинальная шкала (шкала наименований) – устанавливает взаимно однозначное соответствие между объектами, обладающими одним и тем же свойством; основана на отношении эквивалентности; используется для обозначения принадлежности объекта к некоторому определённому классу.

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

•Шкала интервалов – устанавливает упорядочение объектов в зависимости от величины различия какого-либо свойства; имеет

определённый масштаб (a 0) и некоторую произвольную начальную точку отсчёта (b – любое число); используется для измерения, на сколько объект Aiпревосходит объект Aj по разности dij=xi xj числовых оценок xi и xj объектов по шкале.

•Шкала разностей – имеет единичный масштаб (a=1, b – любое

число).

•Шкала отношений – устанавливает упорядочение объектов в зависимости от величины различия какого-либо свойства; имеет

определённый масштаб (a 0) и нулевую точку отсчёта (b=0); используется для измерения, во сколько раз объект Ai превосходит объект Aj по отношению hij=xi/xj числовых оценок xi и xj объектов по шкале.

• Абсолютная (натуральная) шкала – устанавливает упорядочение объектов; имеет единичный масштаб (a=1) и нулевую точку отсчёта (b=0); применяется для измерения количества объектов.

Критерии Критерий (греч. κριτηριον, мерило, средство суждения) – выделенная

особенность, с помощью которой можно охарактеризовать предмет или явление. Для описания этой выделенной особенности вводится определённая смысловая шкала X критерия K, а каждому варианту Ai, i=1,…,m ставится в соответствие одно из значений xi X по шкале критерия: Ai xi. Значение