1.3. Задания

Решить задачу линейного программирования в соответствии с вариантом:

1) 2) 3)

4) 5) 6)

7) 8) 9)

1.4. Ход работы

Решение задачи графическим способом (порядок решения приведен выше).

Решение задачи с помощью надстройки Поиск решения в Microsoft Excel.

Ввод условия задачи состоит из следующих основных шагов:

1. Создание формы для ввода условий задачи.

2. Ввод исходных данных.

3. Ввод зависимостей из математической модели.

4. Поиск решения.

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

1. Сделаем форму для ввода условий задачи (рис. 2.4).

2. Введем исходные данные в форму (рис. 2.5).

3. Введем зависимости из математической модели (рис. 2.6).

Рис. 2.4. Внешний вид формы для ввода условий задачи

Рис. 2.5. Внешний вид формы с данными задачи

а)

б)

Рис. 2.6. Внешний вид формы:

а – с зависимостями задачи, б – с целевой функцией

4. Поиск решения осуществим с помощью надстройки Поиск решения: Данные  Анализ  Поиск решения.

5. На экране: диалоговое окно Поиск решения (рис. 2.7).

Рис. 2.7. Внешний вид диалогового окна «Поиск решения»

6. В поле «Установить целевую ячейку» введем адрес ячейки, где находится формула целевой функции.

7. Установим флажок в поле «Равной максимальному значению».

8. В поле «Изменяя ячейки» введем адрес ячеек, которые мы зарезервировали под значения переменных.

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

а)

б)

Рис. 2.8. Внешний вид диалогового окна:

а – «Добавление ограничений», б – со всеми ограничениями

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

Рис. 2.9. Внешний вид диалогового окна «Параметры поиска решения»

11. Осуществим поиск решения, нажав кнопку «Выполнить».

12. На экране появиться диалоговое окно «Результаты поиска решения» (рис. 2.10).

Рис. 2.10. Внешний вид диалогового окна «Результаты поиска решения»

Ответ: F_max = 14; x₁ = 2; x₂ = 4.

Контрольные вопросы

1. Определение управленческих решений (УР). Сущность УР (организационная, экономическая, социальная, технологическая).

2. Области применения УР (технические, биологические, социальные системы). Направленность УР (стратегическое планирование, управление управленческой деятельностью, управление человеческими ресурсами, управление производственной и вспомогательной деятельностью, формирование организации: структура, процессы, механизмы, коммуникации с внешней средой и др.).

3. Типы УР (структурированные, слабоструктурированные, неструктурированные).

4. Понятие «лицо, принимающее решения» (ЛПР). Факторы, влияющие на принятие и реализацию УР (общественное мнение, эгоизм, собственность, религия, деньги, любовь, семья, политика и т.п.).

5. Альтернативы. Критерии. Процесс принятия решений. Типовые задачи принятия решений.

6. Решение задач линейного программирования графическим методом.

7. Порядок решения задач линейного программирования.

8. Работа с надстройкой Поиск решения.

9. Последовательность решения задач линейного программирования средствами Eсxel.

10. Активизация надстройки Поиск решения.

Оформление отчета

Отчет по лабораторной работе должен содержать:

1. цель и задачи работы;

2. постановку задачи и исходные данные;

3. порядок решения поставленной задачи;

4. полученные результаты;

5. выводы по лабораторной работе.

Литература: [1, с. 63 – 75]; [2, с. 3 – 24]; [3, с. 169 – 185]; [11]; [12].

Лабораторная работа № 2

Решение многокритериальной транспортной задачи методом STEM

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

2.1. Постановка задачи

Основными этапами решения любой задачи в исследовании операций являются:

1. построение модели;

2. выбор критерия оптимальности;

3. нахождение оптимального решения.

Наиболее часто встречаются следующие классические задачи исследования операций.

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

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

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

Классическая постановка транспортной задачи общего вида такова. Имеется m пунктов отправления («поставщиков») и n пунктов потребления («потребителей») некоторого одинакового товара. Для каждого пункта определены:

W_i – объемы запасов i-го поставщика, i = 1, …, m;

q_j – потребность j-го потребителя, j = 1,…,n;

с_ij – стоимость перевозки одной единицы продукции из пункта W_i –

i-го поставщика, в пункт Q_j – j-го потребителя.

Для наглядности данные удобно представлять в виде таблицы (табл. 2.1), которую называют таблицей стоимостей перевозок.

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

Таблица 2.1

Стоимость перевозок

Поставщики	Потребители				Запасы
	Q1	Q2	…	Qn
W1	с11	с12	…	с1n	w1
W2	с21	с22	…	с2n	w2
…	…	…	…	…	…
Wm	cm 1	cm 2	…	cmn	wm
Потребность	q1	q2	…	qn

Под планом перевозок понимают объем перевозок, т.е. количество товара, которое необходимо перевезти от i-го поставщика к j-му потребителю. Для построения математической модели задачи необходимо ввести m×n штук переменных х_ij, i= 1,…, n, j= 1, …, m, каждая переменная х_ij обозначает объем перевозок из пункта W_i в пункт Q_j. Набор переменных X = {x_ij} и будет планом, который необходимо найти, исходя из постановки задачи.

Ограничения задачи примут вид:

– условие минимизации суммарных транспортных расходов;

– ограничения по запасам;

– ограничения по потребностям;

– условие неотрицательности.

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

Очевидно, что для разрешимости задачи необходимо, чтобы суммарный спрос не превышал объема запасов у поставщиков:

.

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

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

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

• существуют альтернативы x, которые обладают m свойствами (характеристиками) z₁, …, z_m;

• каждому i-му (i = 1, …, m) свойству z_i альтернативы x соответствует критериальная оценка z_i = f_i (x) – локальный критерий;

• каждой альтернативе x соответствует в m-мерном критериальном пространстве Z решение (точка) z = (z₁, …, z_m) = (f₁ (x), …, f_m (x)) R^m;

• альтернативы x принадлежат исходному множеству альтернатив X, образованному ограничениями и условиями ( );

• отображение множества X в критериальное пространство Z порождает в этом пространстве множество решений Z_X, являющееся образом множества X:

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

• допустимое множество решений в критериальном пространстве Z образовано пересечением множеств Z_X и Z_Z ( ).

Особенностью задачи является то, что альтернативе x соответствует однозначное описание в пространстве критериев z = (z₁, …, z_m) = (f₁ (x), …, f_m (x)).

Требуется решить одну из следующих задач:

1. упорядочения альтернатив по совокупности m свойств;

2. классификации – распределить альтернативы по классам решений;

3. выбора – выделить лучшую альтернативу.

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

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

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

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

Требуется найти альтернативу (решение) (для непрерывной задачи вектор управления ), обеспечивающую такие значения локальных критериев, которые удовлетворяют ЛПР, и для которой

, ,

,

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

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

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

• ввести понятие лучших решений;

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

• использовать методы для поиска компромиссных решений.

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

При наличии различного характера локальных критериев необходимы предварительное преобразование и нормализация этих критериев. Если в качестве критериев выбраны затраты, потери и др., которые надо минимизировать, то задача минимизации преобразуется в задачу максимизации изменением знака локальных критериев: « ».

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

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

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

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

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

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

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

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

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

Дано: область В допустимых значений переменных, определяемая совокупностью линейных равенств и неравенств; критерии С_k, оценивающие качество решения.

Каждый из критериев линейно связан с переменными:

,

где n – число переменных j = 1, ..., n; c_ij – числовые коэффициенты.

Требуется: найти решение (x₁, x₂, ..., x_n) в области D, при котором достигаются наиболее приемлемые значения по всем критериям. Иначе говоря, нужно найти такие критериальные оценки, при которых достигается максимальное значение априори неизвестной функции полезности ЛПР.

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

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

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

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

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

Компьютерная фаза расчетов:

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

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

• компьютер вырабатывает вспомогательную информацию для ЛПР.

Фаза анализа, проводимая ЛПР:

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

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

Существует большое количество ЧМП [2], [3]. Различные ЧМП отличаются друг от друга содержанием и способом выполнения каждой из фаз. Первые из разработанных ЧМП основаны на использовании информации об относительной важности критериев.

Была предложена классификация ЧМП, основанная на характере информации, получаемой от ЛПР на фазе анализа.

Первая группа ЧМП – прямые ЧМП, в которых ЛПР непосредственно назначает веса критериев и корректирует их на основе полученных решений. В основе прямых ЧМП лежит предположение, что человек может искать наилучшее решение путем непосредственного назначения ряда параметров (например, весов критериев) и сравнения получающихся решений.

Для второй группы ЧМП задача ЛПР состоит в сравнении многокритериальных решений. Эта группа называется ЧМП оценки векторов.

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

Все эти ЧМП имеют общие предварительные этапы. Прежде всего рекомендуется произвести нормирование критериев, определив диапазон их изменения от 0 до 1:

,

где – минимально и максимально возможные значения k-го критерия; C_k (х) – промежуточное значение.

ЧМП STEM – одна из первых ЧМП, относится к процедурам поиска удовлетворительных значений критериев. Она предназначена для решения многокритериальных задач линейного программирования, одной из которых как раз и является многокритериальная транспортная задача.

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

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

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

2. Определение весов критериев. Оптимизация свертки критериев, получение вектора .

3. Диалог с ЛПР (по и определяются «хорошие» и «плохие» компоненты ).

4. Выбор с наименее удовлетворительным значением. Назначение ЛПР удовлетворительного значения для .

5. Максимизация критериев при ряде ограничений на критерий (критериальные ограничения).

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

7. Если ЛПР удовлетворен решением, то останов поиска, иначе переход к п. 1.