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

Основные понятия задачи принятия решений

Необходимость принятия решений так же стара, как и само человечество. Несомненно, уже в доисторические времена первобытные люди, отправляясь, скажем, охотится на мамонта, должны были принимать те или иные решения: в каком месте устроить засаду? Как расставить охотников? Чем их вооружить?

Процессы принятия решений лежат в основе любой целенаправленной деятельности человека:

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

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

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

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

На протяжении многих лет что важные решения принимались опытными людьми (экспертами) , довольно далёкими от математики.

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

Под целью понимается идеальное представление желаемого состояния или результата деятельности. Если фактическое состояние не соответствует желаемому, то имеет место проблема.

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

- функционирование системы в данный момент не обеспечивает достижение поставленных целей;

- функционирование системы в будущем не обеспечит достижение поставленных целей;

- необходимо изменение целей деятельности.

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

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

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

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

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

Принятие решений происходит во времени, поэтому вводится понятие процесса принятия решений. Этот процесс состоит из последовательности этапов и процедур и направлен на устранение проблемной ситуации.

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

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

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

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

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

· ресурсным,

· правовым,

· морально-этическим.

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

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

Итак :

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

Существуют следующие классы задач принятия решений:

1. Задачи принятия решений в условиях определенности (детерминированные задачи)

– когда каждая альтернатива приводит к единственному исходу. Здесь имеется

функциональная зависимость исходов от альтернатив.

2. Задачи принятия решений в условиях стохастики, когда каждая альтернатива

может привести к одному из нескольких исходов, каждый из которых имеет

определенную вероятность появления. В этом случае имеет место стохастическая

зависимость исходов от альтернатив.

По регулярности задачи принятия решения могут быть условно разделены на три

класса:

1. Уникальные задачи. К таким задачам относятся задачи разработки крупных целевых программ. Например, программа высадки человека на Луне, программа экономического развития региона, программа ликвидации последствий аварии на Чернобыльской АЭС. По регулярности это однократно решаемые на данном объекте задачи.

2. Специфические задачи. К данному классу будем относить более часто встречающиеся,

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

Данный класс задач очень широк, к нему относятся такие задачи, как разработка

производственной программы предприятия, определения основных проектных

решений по автоматизации предприятия, распределение ресурсов и т.п. Частота

решения таких задач на одном объекте – несколько раз в году

3. Типовые задачи. К этому классу относятся такие задачи, как принятие решения оператором, диспетчеризация, диагностирование и т.п. Частота решения – несколько раз в день-месяц на одном объекте. Для типовых задач разработаны автоматизированные и

экспертные системы в рамках которых эффективно решаются задачи выбора

оптимального маршрута, раскроя материала, диагностирования и т.п.

Для многих разработаны пакеты прикладных

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

1.1. Методы принятия решений

Совершенствование процесса принятия обоснованных объективных решений в ситуациях исключительной сложности достигается путем использования научного подхода к данному процессу, моделей и количественных методов принятия решений. Следует различать методы принятия управленческих решений на основе математического моделирования и методы, основанные на психологических приемах работы в группах. Экспертные методы принятия управленческих решений, включающие вербально-числовые шкалы и Метод Дельфи, метод ранжирования,методы определения весовых коэффициенов Методы принятия управленческих решений на основе творческого мышления (психологические методы). Вероятностно-статистические методы , включающие системы массового обслуживания. Линейное программирование — метод, при котором решаются оптимизационные задачи, в которых целевая функция и функциональные ограничения являются линейными функциями относительно переменных, принимающих любые значения из некоторого множества значений. Имитационное моделирование — способ формирования решения, при котором лицо, принимающее решение, приходит к разумному компромиссу в значениях различных критериев. При этом ЭВМ по заданной программе имитирует и воспроизводит течение изучаемого процесса при нескольких возможных вариантах управления, ему заданных, полученные результаты анализируются и оцениваются. Метод теории игр — метод, при котором задачи решаются в условиях полной неопределенности. Это означает наличие таких условий, при котором процесс выполнения операции является неопределенным или противник противодействует сознательно, или отсутствуют ясные и четкие цели и задачи операции. Следствием такой неопределенности является то, что успех операции зависит не только от решений принимающих их люден, но и от решений или действий других людей. "Чаще всего с помощью этого метода приходится разрешать конфликтные ситуации. Метод аналогий — поиск возможных решений проблем на основе заимствования из других объектов управления. Мы основное внимание на практических занятиях будем уделять основное внимание методам, поддающимся компьютерной обработке и программирования . Сначала мы изучим более доступный и применяемый метод линейного программирования, затем имитационного моделирования .     Глава 2 Линейное программирование 2.1. Понятия модели, моделирования и оптимального (линейного) программирования Модель –это специально подобранный объект, который имеет с реальным объектом некоторые общие свойства, интересующие исследователя. Математическая модель – составляется на языке математики с использованием математических знаков и правил. Компьютерная модель на языке программирования и выполняется преобразованием знаков в электрические сигналы , с последующим обратимым преобразованием сигналов на язык понятный человеку. Серией компьютерных экспериментов мы исследуем модель и получаем подтверждение или опровержение наших пред экспериментальных гипотез о поведении модели. Выводы о поведении модели менеджер применяет к реальному объекту , т.е. принимает плановое или прогнозное решение, полученное с помощью исследования модели. Моделирование-это способ теоретического анализа и практического действия, направленное на разработку и исследование моделей. Задачами экономико-математического моделирования являются: Анализ экономических объектов и процессов. Экономическое прогнозирование и предвидение развития экономических процессов Выработка управленческих решений на всех уровнях хозяйственной иерархии. Наиболее часто в моделях используются следующие цели и критерии: максимизация прибыли, рентабельности, снижение затрат минимизация налогов обеспечение устойчивости в нестабильной среде расчет экономических параметров операций (например баланс ресурсов) и др. 2.2. Этапы моделирования 1.Постановка экономической проблемы и ее качественный анализ. Формируется сущность проблемы , принимаемые предпосылки и допущения. Выделяются важнейшие черты и свойства моделируемого объекта, изучается его структура и взаимосвязь элементов. 2. Построение математической модели, т.е. экономическую проблему выражают в виде формул, уравнений и т.д. 3. Математический анализ модели. Выделяются общие свойства модели и ее решение. 4. Подготовка исходной информации. В процессе подготовки информации используются методы теории вероятностей и математической статистики, оценки достоверности данных и т.д. 5. Численное решение. Этап включает разработку алгоритмов решения задаи, подготовку программ, т.е. начинается : Разработка компьютерной модели. При этом необходимо выбрать программное обеспечение для реализации модели на компьютере. Это могут быть прикладные программы, например, табличные процессоры Excel, Lotus. Пакет моделирования системы массового обслуживания GPSS пакеты для моделирования экономической динамики Ithink пакеты математических и технических систем Matlab Simulink. Компьютерное моделирование, прогон программ. Намечается план модельных экспериментов. Составляется перечень и числовые значения параметров входных переменных, для которых будут выполнены расчеты. Компьютерные расчеты Запускается модель, выводятся на экран и печать результаты расчетов в виде таблиц и графиков. 6. Оценка результатов моделирования и отладка модели Результаты моделирования сравниваются с поведением реального объекта. Степень совпадения результатов говорит об адекватности модели объекту. Модель почти всегда дорабатывается. Все этапы разработки модели многократно циклически повторяются . Готовая модель передается пользователям: плановикам менеджерам, аналитикам. Результаты моделирования применяются к реальному объекту для управления или заключении о его функционировании. 2.1. Понятия линейного и оптимального программирования Оптимальным (математическим ) программированием называется раздел прикладной математики, изучающий задачи условной оптимизации. Линейное программирование – это раздел оптимального программирования. В задачах условной оптимизации для некоторой системы требуется найти решение (1), компоненты которого наилучшим (оптимальным) образом соответствуют внутренним и внешним условиям рассматриваемой системы. В экономике задачи оптимизации возникают при практической реализации принципа оптимальности в планировании и управлении, при этом в качестве критерия оптимальности могут выступать максимум прибыли, минимум себестоимости, минимум трудовых затрат и др. Критерий оптимальности, записанный в виде математической функции называется целевой функцией (другие названия : функция цели, функционал). Требование соответствия принимаемого решения внутренним и внешним условиям системы и предполагает выбор решения из некоторой области возможных решений (ОДР), или областью решения задачи. Решение из области определения называется допустимым решением , или планом. Допустимое решение, для которого выполняется принятый критерий оптимальности (максимум или минимум целевой функции) называется оптимальнымпланом или оптимальным решением. Стандартная форма записи задачи линейного программирования   Реализация на практике принципа оптимальности в планировании и управлении означает решение экстремальной задачи вида: , (2.1) (2.2) Если целевая функция является линейной функцией переменных , а ограничения , описывающие область определения D имеют вид линейных уравнений и (или) неравенств относительно тех же переменных, то задача оптимального программирования (2.1)-(2.2) называется задачей линейного программирования. В общем виде задача линейного программирования может быть записана следующим образом: (2,3) (2,4) j=1,n (2,5) Эта форма записи (2,3 – 2,5) называется стандартной формой задачи линейного программирования. ограничение (2,4) называется функциональными ограничениями. Ограничение 23,5) называется прямыми ограничениями или условиями не отрицательности   2.3.. Примеры приведения экономической задачи к математической модели и ее решение с помощью линейного программирования   Задача экономики труда. Посмотрим как ее привести к задаче линейного программирования. Пусть на предприятии есть две категории рабочих: Основные Вспомогательные Нормы затрат труда на производство единицы двуъ видов продукции, наличие трудовых ресурсов на предприятии и цены единиц продукции приведены в таблице   Категория рабочих Нормы затрат труда на единицу продукции Наличие ресурсов труда Основные Вспомогательные Цены единицы продукции         Требуется составить план выпуска продукции при имеющихся ограничениях на трудовые ресурсы. План должен обеспечивать наибольшую общую стоимость выпущенной продукции. Решение. Пусть - объемы выпуска продукции каждого вида. Тогда целевая функция задачи имеет вид: Функциональные ограничения определяются объемами имеющихся трудовых ресурсов: Условия неотрицательности переменных будут 0 ; ; Таким образом, получаем задачу линейного программирования. Для ее решения был разработан Симплекс метод.

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

Рассмотрим алгоритм симплекс-метода на данной задаче.

Этап 1. Приведем задачу к каноническому виду, введя дополнительные переменные х₃ и х₄

_{Это нужно, чтобы иметь дело с уравнениями, а не неравенствами.}

или

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

1 3 1 0 300

1 1 0 1 150

- это начальное опорное базисное решение,

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

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

Задавая свободным переменными нулевые значения , получим базисное решение.

В нашей задаче переменные базисные свободные.

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

Получим начальный опорный план (0, 0, 300, 150).

Этап 3. Составим начальную (нулевую ) симплексную таблицу и применим алгоритмы симплекс-метода. Количество граф данной таблицы определяется прибавлением к числу переменных канонической формы ЗЛП числа 5. Таким образом в нашей задаче этих граф будет 9.

Симплексные таблицы имеют одну и ту же структуру и следуют непосредственно одна за другой. Для нашей задачи они представлены в табл. 2

Таблица 2.

Номер симплекс- таблицы	Базис	Сj   Ci	План (bi)
			150
			-2	-3
				1/3 2/3		1/3 -1/3
		-1
						1/2 -1/2	-1/2 3/2
				1/2	3/2

Нулевая симплекс-таблица, за исключением последней строки и последней графы, не является расчетной и отражает в табличной форме результаты этапов 1 и 2.

Первый вычислительный алгоритм симплекс-методазаключается в расчете для каждой переменной ее оценки (симплексной разности):

j=1,n (2.8)

В формуле (2,8)суммирование ведется по всем переменным, веденным в базис

Дадим экономическую интерпретацию этой величины. Если коэффициенты c_j понимать

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

В теории линейного программирования доказывается, что если для всех переменных выполняется условие

(2.9)

То план, представленный в симплекс-таблице, является оптимальным. Если для некоторой свободной переменной условие (2.9) не выполняется , то данный план не является оптимальным:

Ввод в базис этой свободной переменной приведет к увеличению значения целевой функции.

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

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

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

(2.10)

Где -индекс направляющего столбца, а величина берется из графы «План»

Так в нулевой симплекс-таблице решаемой задачи оценочное отношение для базисной переменной равно300/3=100, а для базисной переменной - 150/1=150 в последней графе табл.2

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

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

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

Необходимо отметить следующее. В формуле (2.!0) для оценочного отношения

Выделено условие . Если для некоторой базисной переменной элемент направляющего столбца , то величина не рассчитывается ( в последней графе ставится прочерк или знак бесконечности).Если в направляющем столбце все элементы

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

Если в симплексной таблице определен решающий элемент, то в соответствии с методом Жордана-Гаусса можно переходить к улучшенному опорному плану ( к следующей симплекс-таблице).

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

Третий вычислительный алгоритмсимплекс-метода состоит из двух вычислительных процедур.

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

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

Рис. 2. Правило прямоугольного треугольника

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

Указанная последовательность трех вычислительных алгоритмов симплекс-метода повторяется столько раз, пока в строке оценок симплексной таблицы для всех оценок не будет выполняться условие не отрицательности (2.9) Выполнение этого условия, будет свидетельствовать о достижении оптимального решения, в котором значения базисных переменных даются в графе «План» последней симплекс-таблицы, а все свободные переменные равны нулю. Таким образом:

· оптимальный опорный план решаемой задачи имеет вид: (75; 75; 0; 0)

· максимум целевой функции при этом равен 375.

Результат можно записать следующим образом:

при , оптимальный план является единственным.

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