Шпаргалка по "Исследованию операций в экономике"

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

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

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

     Критерием является MAX цена очередного продукта из интересуемой группы f.

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

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

     a) система неравенств (ограничения  рациональности поведения потребителя)  (см. 4.2. Прогнозирование в рамках  обобщенного непараметрического  метода);

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

     в) бюджетное ограничение в виде равенства - требование постоянства суммы затрат на покупку продуктов из группы f (с учетом 15% инфляции, например).

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

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

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

     Найти минимальное значение функции 

     (2.1) Z = С1х1+С2х2

     при

     a11x1 + a22x2 b1

     (2.2)a21x1 + a22x2 b2

     aM1x1 + aM2x2 bM

     (2.3) х1 0, х2 0

     Допустим, что система (2.2) при условии (2.3) совместна  и ее многоугольник решений ограничен. Каждое из неравенств (2.2) и (2.3), как отмечалось выше, определяет полуплоскость с  граничными прямыми: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), х1=0, х2=0. Линейная функция (2.1) при фиксированных значениях Z является уравнением прямой линии: С1х1 + С2х2 = const. Построим многоугольник решений системы ограничений (2.2) и график линейной функции (2.1) при Z = 0 (рис. 2.1). Тогда поставленной задаче линейного прграммирования можно дать следующую интерпретацию. Найти точку многоугольника решений, в которой прямая С1х1 + С2х2 = const опорная и функция Z при этом достигает минимума.

     Значения Z = С1х1 + С2х2 возрастают в направлении вектора N =(С1, С2), поэтому прямую Z = 0 передвигаем параллельно самой себе в направлении вектора Х. Из рис. 2.1 следует, что прямая дважды становится опорной по отношению к многоугольнику решений (в точках А и С), причем минимальное значение принимает в точке А. Координаты точки А (х1, х2) находим, решая систему уравнений прямых АВ и АЕ.

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

     Случай 1. Прямая С1х1 + С2х2 = const, передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу (рис. 2.2).

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

     9. Симплекс- метод.

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

     Этот  метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, ..., Xr. Тогда наша система уравнений может быть записана как

     

     Симплекс-метод  основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.

     10. Постановка транспортной задачи. Методы определения опорных планов.

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

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

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

     сij – стоимость перевозки одной  единицы продукции из пункта Ai– i-го поставщика, в пункт Вj – j-го потребителя.

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

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

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

     Это условие для решения закрытых и открытых транспортных задач (ЗТЗ).

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

     

     Если  это неравенство выполняется  строго, то задача называется «открытой» или «несбалансированной», если же , то задача называется «закрытой» транспортной задачей, и будет иметь вид (2):

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

     Это условие для решения закрытых транспортных задач (ЗТЗ).

     

     11. Алгоритм решения  транспортной задачи.

     Применение  алгоритма требует соблюдения ряда предпосылок:

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

     2. Запас продуктов в каждом пункте  производства должен быть известен.

     3. Потребности в продуктах в  каждом пункте потребления должны  быть известны.

     4. Общее предложение должно быть  равно общему спросу.

     Алгоритм  решения транспортной задачи состоит  из четырех этапов:

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

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

     Этап 3. Если полученное распределение ресурсов не является оптимальным, то ресурсы перераспределяются, снижая стоимость транспортировки.

     Этап 4. Повторная проверка оптимальности  полученного распределения ресурсов.

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

     12. Модели управления  запасами.

     

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

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

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

     детерминированными;

     вероятностными.

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

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

     Наиболее  простым является случай детерминированного статического спроса на продукцию. Однако такой вид потребления на практике встречается достаточно редко. Наиболее сложные модели - модели нестационарного типа.

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

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

     процесс пополнения запаса. Может быть мгновенным либо распределенным во времени;

     наличие ограничений по оборотным средствам, складской площади т.п.