Файл: Кафедра Математических методов принятия решений.pdf

Метод сценариев получил очень большое распространение в современном мире.
Используется во всех отраслях экономики, как для открытия новых компаний, так и для синтеза действующих компаний. Наиболее часто можно увидеть применение данного метода при составлении различных прогнозов для финансово-хозяйствующего субъекта ( к примеру, при прогнозировании продаж ).
Как правило, данный метод подразумевает составление трех сценариев:
1.
Пессимистического.
2.
Реального.
3.
Оптимистического.
Вопрос 2. Постановка задачи линейного программирования и свойства ее решений.
Линейное программирование
— раздел математического программирования,
применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополнительных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП).
Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.
Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений. Отсюда — необходимость разработки новых методов.
Формы записи задачи линейного программирования:
Общей задачей линейного программирования называют задачу
(1)
при ограничениях
(2)
(3)
(4)
(5)
– произвольные
(6)
где
– заданные действительные числа; (1) – целевая функция; (1) – (6) –
ограничения;
– план задачи.
Пусть ЗЛП представлена в следующей записи:
(7)
(8)
(9)

Чтобы задача (7) – (8) имела решение, системе её ограничений (8) должна быть совместной. Это возможно, если r этой системы не больше числа неизвестных n. Случай вообще невозможен. При система имеет единственное решение, которое будет при оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть
. В
этом случае система векторов содержит базис — максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, вообще говоря, может быть несколько, но не более
.
Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные переменных будут
свободными, их обозначают СП. Не ограничивая общности, будем считать, что базис составляют первые m векторов
. Этому базису соответствуют базисные переменные
, а свободными будут переменные
Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (8) называют опорным
решением (планом).
Теорема. Если система векторов содержит m линейно независимых векторов
, то допустимый план
(10)
является крайней точкой многогранника планов.
Теорема. Если ЗЛП имеет решение, то целевая функция достигает экстремального значения хотя бы в одной из крайних точек многогранника решений. Если же целевая функция достигает экстремального значения более чем в одной крайней точке, то она достигает того же значения в любой точке, являющейся их выпуклой линейной комбинацией.
Графический способ решения ЗЛП.
Геометрическая интерпретация экономических задач дает возможность наглядно представить, их структуру, выявить особенности и открывает пути исследования более сложных свойств. ЗЛП с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в пространствах, размерность которых больше трех, графическое решение, вообще говоря, невозможно. Случай двух переменных не имеет особого практического значения, однако его рассмотрение проясняет свойства ОЗЛП,
приводит к идее ее решения, делает геометрически наглядными способы решения и пути их практической реализации.
Пусть дана задача
(11)
(12)
(13)

Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений
(12), (13) задает на плоскости некоторую полуплоскость. Полуплоскость — выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множеством.
Отсюда следует, что область допустимых решений задачи (11) — (13) есть выпуклое множество.
Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП — непустое множество, например многоугольник
Рис. 1
Выберем произвольное значение целевой функции
. Получим
. Это уравнение прямой линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение
. Считая в равенстве (11) параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).
Найдём частные производные целевой функции по и :
, (14)
. (15)
Частная производная (14) (так же как и (15)) функции показывает скорость ее возрастания вдоль данной оси. Следовательно, и
— скорости возрастания соответственно вдоль осей и
. Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:
Вектор указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.
Вектор перпендикулярен к прямым семейства
Из геометрической интерпретации элементов ЗЛП вытекает следующий порядок ее графического решения.
1.
С учетом системы ограничений строим область допустимых решений .
2.
Строим вектор наискорейшего возрастания целевой функции — вектор градиентного направления.
3.
Проводим произвольную линию уровня
.

4.
При решении задачи на максимум перемещаем линию уровня в направлении вектора так, чтобы она касалась области допустимых решений в ее крайнем положении
(крайней точке). В случае решения задачи на минимум линию уровня перемещают в антиградиентном направлении.
5.
Определяем оптимальный план и экстремальное значение целевой функции
Симплексный метод решение ЗЛП.
Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит:
1)
умение находить начальный опорный план;
2)
наличие признака оптимальности опорного плана;
3)
умение переходить к нехудшему опорному плану.
Пусть ЗЛП представлена системой ограничений в каноническом виде:
Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства – с коэффициентом,
равным нулю.
Пусть система ограничений имеет вид
Сведем задачу к каноническому виду. Для этого прибавим к левым частям неравенств дополнительные переменные
. Получим систему, эквивалентную исходной:
,
которая имеет предпочтительный вид
В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю
Пусть далее система ограничений имеет вид

Сведём её к эквивалентной вычитанием дополнительных переменных из левых частей неравенств системы. Получим систему
Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные входят в левую часть (при
) с коэффициентами, равными
–1. Поэтому, вообще говоря, базисный план не является допустимым. В этом случае вводится так называемый искусственный базис. К левым частям ограничений-равенств, не имеющих предпочтительного вида, добавляют искусственные переменные . В целевую функцию переменные , вводят с коэффициентом М в случае решения задачи на минимум и с коэффициентом – М для задачи на максимум, где М – большое положительное число. Полученная задача называется М-задачей, соответствующей исходной.
Она всегда имеет предпочтительный вид.
Пусть исходная ЗЛП имеет вид
, (16)
, (17)
, (18)
причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:
(19)
(20)
(21)
Задача (19) – (21) имеет предпочтительный план. Её начальный опорный план имеет вид
Если некоторые из уравнений (17) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.
Теорема. Если в оптимальном плане
(22)

М-задачи (19) – (21) все искусственные переменные
, то план является оптимальным планом исходной задачи (16) – (18).
Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида,
вводят искусственный базис и решают расширенную М – задачу, которая имеет начальный опорный план
Решение исходной задачи симплексным методом путем введения искусственных переменных называется симплексным методом с искусственным базисом.
Если в результате применения симплексного метода к расширенной задаче получен оптимальный план, в котором все искусственные переменные
, то его первые n
компоненты дают оптимальный план исходной задачи.
Теорема. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.
Признаки оптимальности.
Теорема. Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки неотрицательны, то такой план оптимален.
Теорема. Если исходная задача решается на минимум и для некоторого опорного плана все оценки не положительны, то такой план оптимален.
Рассмотрим классические примеры ЗЛП.
Задача о смесях.
В различных отраслях народного хозяйства возникает проблема составления таких рабочих смесей на основе исходных материалов, которые обеспечивали бы получение конечного продукта, обладающего определенными свойствами. К этой группе задач относятся задачи о выборе диеты, составлении кормового рациона в животноводстве, шихт в металлургии, горючих и смазочных смесей в нефтеперерабатывающей промышленности, смесей для получения бетона в строительстве и т. д. Высокий уровень затрат на исходные сырьевые материалы и необходимость повышения эффективности производства выдвигает на первый план следующую задачу: получить продукцию с заданными свойствами при наименьших затратах на исходные сырьевые материалы.
Пример. Для откорма животных используется три вида комбикорма: А, В и С. Каждому животному в сутки требуется не менее 800 г. жиров, 700 г. белков и 900 г. углеводов.
Содержание в 1 кг. каждого вида комбикорма жиров, белков и углеводов (граммы) приведено в таблице 1:
Таблица 1.
Содержание жиров, белков и углеводов (граммы) в 1 кг. каждого вида комбикорма
Содержание в 1 кг.
Комбикорм
А
В
С
Жиры
320 240 300
Белки
170 130 110

Углеводы
380 440 450
Стоимость 1 кг
31 23 20
Сколько килограммов каждого вида комбикорма нужно каждому животному, чтобы полученная смесь имела минимальную стоимость?
Математическая модель задачи есть:
– количество комбикорма А, В и С. Стоимость смеси есть:
Ограничения на количество ингредиентов:
Задача о раскрое материалов.
Сущность задачи об оптимальном раскрое состоит в разработке таких технологически допустимых планов раскроя, при которых получается необходимый комплект заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму.
Рассматривается простейшая модель раскроя по одному измерению. Более сложные постановки ведут к задачам целочисленного программирования.
Задача о назначениях.
Речь идет о задаче распределения заказа (загрузки взаимозаменяемых групп оборудования) между предприятиями (цехами, станками, исполнителями) с различными производственными и технологическими характеристиками, но взаимозаменяемыми в смысле выполнения заказа. Требуется составить план размещения заказа (загрузки оборудования), при котором с имеющимися производственными возможностями заказ был бы выполнен, а показатель эффективности достигал экстремального значения.
Пример. Цеху металлообработки нужно выполнить срочный заказ на производство деталей. Каждая деталь обрабатывается на 4-х станках С1, С2, С3 и С4. На каждом станке может работать любой из четырех рабочих Р1, Р2, Р3, Р4, однако, каждый из них имеет на каждом станке различный процент брака. Из документации ОТК имеются данные о проценте брака каждого рабочего на каждом станке (табл. 2).
Таблица 2.
Процент брака каждого рабочего на каждом станке
Рабочие
Станки
С1
С2
С3
С4
Р1 2,3 1,9 2,2 2,7
Р2 1,8 2,2 2,0 1,8
Р3 2,5 2,0 2,2 3,0
Р4 2,0 2,4 2,4 2,8
Необходимо так распределить рабочих по станкам, чтобы суммарный процент брака
(который равен сумме процентов брака всех 4-х рабочих) был минимален. Чему равен этот

процент?
Обозначим за
– переменные, которые принимают значения 1,
если i-й рабочий работает на j-м станке. Если данное условие не выполняется,
. Целевая функция есть:
Вводим ограничения. Каждый рабочий может работать только на одном станке, то есть
Кроме того, каждый станок обслуживает только один рабочий:
Кроме того, все переменные должны быть целыми и неотрицательными:
Транспортная задача.
Математическая модель задачи.
Линейные транспортные задачи составляют особый класс задач линейного программирования. Задача заключается в отыскании такого плана перевозок продукции с m
складов в пункт назначения n который, потребовал бы минимальных затрат. Если потребитель j
получает единицу продукции (по прямой дороге) со склада i, то возникают издержки С
ij
Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы
Далее, предполагается, что где есть количество продукции, находящееся на складе i, и
– потребность потребителя
. Такая транспортная задача называется закрытой. Однако, если данное равенство не выполняется, то получаем открытую транспортную задачу, которая сводится к закрытой по следующим правилам:
1.
Если сумма запасов в пунктах отправления превышает сумму поданных заявок то количество продукции, равное остается на складах. В этом случае мы введем «фиктивного» потребителя с потребностью и положим транспортные расходы равными 0 для всех i.

2.
Если сумма поданных заявок превышает наличные запасы то потребность не может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления m+1 с запасом и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.
Математическая модель транспортной задачи имеет вид:
где количество продукции, поставляемое со склада i потребителю j, а издержки
(стоимость перевозок со склада i потребителю j).
Рассмотрим пример:
Пример. Компания «Стройгранит» производит добычу строительной щебенки и имеет на территории региона три карьера. Запасы щебенки на карьерах соответственно равны 800, 900 и
600 тыс. тонн. Четыре строительные организации, проводящие строительные работы на разных объектах этого же региона, дали заказ на поставку соответственно 300, 600, 650 и 750 тыс. тонн щебенки. Стоимость перевозки 1 тыс. тонн щебенки с каждого карьера на каждый объект приведены в таблице:
Таблица 3.
Карьер
Строительный объект
1
2
3
4
1
8 4
1 7
2
3 6
7 3
3
6 5
11 8
Необходимо составить такой план перевозки (количество щебенки, перевозимой с каждого карьера на каждый строительный объект), чтобы суммарные затраты на перевозку были минимальными.
Данная транспортная задача является закрытой, так как запасы поставщиков равны спросу потребителей
. Математическая модель ЗЛП в данном случае имеет вид:
– количество щебенки, перевозимой с i–го карьера на j–й объект.
Тогда целевая функция равна
Ограничения имеют вид

Вопрос 3. Решение ЗЛП с помощью MS EXCEL.
Для решения задач оптимизации в MS Excel используют надстройку Поиск решения,
которая вызывается из пункта главного меню «Сервис»(рис. 2).
Рис. 2
Если в версии Excel, установленной на Вашем компьютере, отсутствует данный подпункт меню «Сервис», необходимо вызвать пункт меню «Надстройки» и в предложенном списке дополнительных модулей выбрать «Поиск решения» (рис. 3).

Рис. 3.
Рассмотрим на примере использование данной надстройки. Решим с её помощью задачу.
Математическая модель задачи имеет вид:
(целевая функция)
при
Составим шаблон в редакторе Excel, как показано на рис. 4.
Рис. 4. Шаблон оформления задачи
Теперь занесём данную в задаче числовую информацию (рис. 5).

Рис. 5. Исходные данные задачи
В выделенные пустые ячейки (значения целевой функции и левых частей неравенств)
необходимо занести формулы, отображающие связи и отношения между числами на рабочем листе.
Ячейки B4 – С4 называются в Excel изменяемыми (в нашей модели это неизвестные переменные), т.е., изменяя их Поиск решения будет находить оптимальное значение целевой функции. Значения, которые первоначально вводят в эти ячейки, обычно нули (незаполненные клетки трактуются по умолчанию как содержащие нулевые значения).
Теперь необходимо ввести формулы. В нашей математической модели, целевая функция представляет собой произведение вектора коэффициентов на вектор неизвестных.
Действительно, выражение можно рассматривать как произведение вектора (3,2) на вектор (Х
1
,Х
2
).
В Excel существует функция СУММПРОИЗВ, которая позволяет найти скалярное произведение векторов. В ячейку Е4 необходимо вызвать данную функцию, а в качестве перемножаемых векторов задать адреса ячеек, содержащих коэффициенты уравнений (в данном случае, это В5:С5) и ячеек, в которые в результате решения будут помещены значения и
(ячейки В4:С4) (рис. 6).