Теория принятия оптимальных решений

Размещено на http://www.allbest.ru/

1. Предмет и задачи теории принятия оптимальных решений. Исследование операций, основные понятия и определения исследования операций

линейное программирование двойственность задача

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

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

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

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

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

Операция - это управляемое мероприятие, то есть от нас зависит, каким способом выбрать некоторые параметры, характеризующие его организацию.

Каждый определенный выбор зависящих от нас параметров называется решением.

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

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

Пример 1: перевозка однородного груза.

Существуют пункты отправления:

А1, А2, А3,…, Аm.

Имеются пункты назначения:

В1, В2, В3,…, Вn.

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

Совокупность этих чисел: x11, x12, x13,…, x1m,…, xn1, xn2,…, xnm образует решение.

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

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

2. Модели и моделирование. Назначение и классификация моделей, их роль в научном познании. Основные типы экономико-математических моделей

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

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

Моделирование, в таком случае, представляет собой процесс построения, изучения и применения моделей. Главная особенность моделирования состоит в том, что это метод опосредованного познания при помощи объектов-заменителей. Модель выступает как инструмент познания, который исследователь ставит между собой и объектом с целью изучения последнего, т.е. объект рассматривается как бы через "призму" его модельного представления. Процесс моделирования, таким образом, включает в себя три элемента: субъект исследования (исследователь), объект исследования, модель. Ситуацию иллюстрирует рисунок 1.1.



Рисунок 1.1 - Роль модели в процессе исследования

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

Классифицировать экономико-математические модели можно по различным основаниям.

1. По целевому назначению модели можно делить на:

- теоретико-аналитические, применяемые для исследования наиболее общих свойств и закономерностей развития экономических процессов;

- прикладные, используемые для решения конкретных задач.

2. По уровням исследуемых экономических процессов:

· производственно-технологические;

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

3. По характеру отражения причинно-следственных связей:

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

· недетерминированные (вероятностные, стохастические), учитывающие фактор неопределённости.

4. По способу отражения фактора времени:

· статические. Здесь все зависимости относятся к одному моменту или периоду времени);

· динамические, характеризующие изменения процессов во времени.

5. По форме математических зависимостей:

- линейные. Наиболее удобны для анализа и вычислений, вследствие чего получили большое распространение;

- нелинейные.

6. По степени детализации (степени огрубления структуры):

- агрегированные ("макромодели");

- детализированные ("микромодели").

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

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

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

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

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

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

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

8. Стохастическое программирование. Здесь исследуемые параметры являются случайными величинами.

9. Нелинейное программирование относится к наименее изученному, применительно к экономическим явлениям и процессам, математическому направлению.

10. Теория графов - направление математики, где на основе определенной символики представляется формальное описание взаимосвязанности и взаимообусловленности множества элементов (работ, ресурсов, затрат и т.п.). До настоящего времени наибольшее практическое применение получили так называемые сетевые графики.

3. Общая постановка задачи исследования операций. Разделы математического программирования, области их применения

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

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

Модель задачи математического программирования включает:

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

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

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

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

Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л. В. Канторовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в экономике. Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач -- симплекс-метод. Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит в следующем:

1) умение находить начальный опорный план;

2) наличие признака оптимальности опорного плана;

3) умение переходить к нехудшему опорному плану.

4. Постановка задачи линейного программирования в общем виде Основная задача линейного программирования, эквивалентные формы ее записи

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

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

Формы записи задачи линейного программирования:

Общей задачей линейного программирования называют задачу

(2.1)

при ограничениях

(2.2)

(2.3)

(2.4)

(2.5)

- произвольные

(2.6)

где - заданные действительные числа; (2.1) - целевая функция; (2.1) - (2.6) -ограничения;

- план задачи.

Пусть ЗЛП представлена в следующей записи:

(2.7)

(2.8)

(2.9)

Чтобы задача (2.7) - (2.8) имела решение, системе её ограничений (2.8) должна быть совместной. Это возможно, если r этой системы не больше числа неизвестных n. Случай r>n вообще невозможен. При r=nсистема имеет единственное решение, которое будет при оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть r<n. В этом случае система векторов содержит базис -- максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, вообще говоря, может быть несколько, но не более . Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные n - r переменных будут свободными, их обозначают СП. Не ограничивая общности, будем считать, что базис составляют первые m векторов . Этому базису соответствуют базисные переменные , а свободными будут переменные .

Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (8) называют опорным решением (планом).

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

(2. 10)

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

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

5. Виды задач ЛП в зависимости формы задания ограничительных условий. Приведение к каноническому виду и обратно. Теорема о соответствии решений различных видов задач

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

Задачи линейного программирования являются самыми простыми и лучше изученными задачами. Для них характерно: показатель эффективности (целевая функция) выражается линейной зависимостью; ограничения на решения - линейные равенства или неравенства.

Трудности решения ЗЛП.

Трудности решения задач линейного программирования зависят от: вида зависимости, связывающей целевую функцию с элементами решения; размерности задачи, то есть от количества элементов решения х1, х2,…, xn; вида и количества ограничений на элементы решений.

Классификация задач оптимизации.

Задача о рациональном питании (задача о пищевом рационе).

ПОСТАНОВКА ЗАДАЧИ.

Ферма производит откорм скота с коммерческой целью. Для простоты допустим, что имеется всего четыре вида продуктов: П1, П2, П3, П4; стоимость единицы каждого продукта равна соответственно С1, С2, С3, С4. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков - не менее bi единиц; углеводов - не менее b2 единиц; жиров - не менее b3 единиц. Для продуктов П1, П2, П3, П4 содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано в таблице, где aij (i=1,2,3,4; j=1,2,3) - какие - то определённые числа; первый индекс указывает номер продукта, второй - номер элемента (белки, углеводы, жиры).

|продукт |элементы |

|белки |углеводы |жиры |

|П1 |A11 |A12 |A13 |

|П2 |A21 |A22 |A23 |

|П3 |A31 |A32 |A33 |

|П4 |A41 |A42 |A43 |

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

Задача о планировании производства

ПОСТАНОВКА ЗАДАЧИ

Предприятие производит изделия трёх видов: U1, U2, U3.

По каждому виду изделия предприятию спущен план, по которому оно обязано выпустить не мене b1 единиц изделия U1, не мене b2 единиц изделия U2 и не мене b3 единиц изделия U3. План может быть перевыполнен, но в определённых границах; условия спроса ограничивают количества произведённых единиц каждого типа: не более соответственно (1, (2, (3 единиц. На изготовление изделий идёт какое-то сырьё; всего имеется четыре вида сырья: s1, s2, s3, s4, причём запасы ограничены числами (1, (2, (3, (4 единиц каждого вида сырья. Теперь надо узнать какое количество сырья каждого вида идёт на изготовление каждого вида изделий. Обозначим aij количество единиц сырья вида si (I= 1, 2, 3, 4), потребное на изготовление одной единицы изделия Uj

(j= 1, 2, 3). Первый индекс у числа aij - вид изделия, второй - вид сырья.

Значения aij сведены в таблицу (матрицу).

|Сырьё|Изделия |

| |U1 |U2 |U3 |

|S1 |a11 |a21|a31|

|S2 |a12 | | |

|S3 |a13 |a22|a32|

|S4 |a14 | | |

| | |a23|a33|

| | | | |

| | |a24|a34|

При реализации одно изделие U1 приносит предприятию прибыль c1, U2 - прибыль c2, U3 - прибыль c3. Требуется так спланировать производство

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

Фабрике предписан план согласно которому она должна производить в месяц не менее b1 метров ткани Т1, b2 метров ткани Т2, b3 метров ткани Т3; количество метров каждого вида ткани не должно превышать соответственно (1, (2, (3 метров. Кроме того, все без исключения станки должны быть загружены. Требуется так распределить загрузку станков производством тканей Т1, Т2, Т3, чтобы суммарный месячный доход был максимален.

Задача о снабжении сырьём

ПОСТАНОВКА ЗАДАЧИ. Имеется три промышленных предприятия: П1, П2, П3, требующих снабжения определённым видом сырья. Потребности в сырье каждого предприятия равны соответственно a1, a2, a3 единиц. Имеются пять сырьевых баз, расположенных от предприятий на каких - то расстояниях и связанных с ними путями сообщения с разными тарифами. Единица сырья, получаемая предприятием Пi c базы Бj , обходится предприятию в сij рублей (первый индекс - номер предприятия, второй - номер базы).

|Предприятия |Базы |

| |Б1 |Б2 |Б3 |Б4 |Б5 |

|П1 |С11 |С12 |С13 |С14 |С15 |

|П2 |С21 |С22 |С23 |С24 |С25 |

|П3 |С31 |С32 |С33 |С34 |С35 |

Возможности снабжения сырьём с каждой базы ограничены её производственной мощностью: базы Б1, Б2, Б3, Б4, Б5 могут дать не более b1, b2, b3, b4, b5 единиц сырья. Требуется составить такой план снабжения предприятий сырьём (с какой базы, куда и какое количество сырья везти), чтобы потребности предприятий были обеспечены при минимальных расходах на сырьё.

6. Свойства решений ЗЛП. Допустимое решение. Базисное решение. Опорный план. Выпуклые множества в n-мерном пространстве

1. Каждому опорному/базисному решению ЗЛП соответствует крайняя угловая точка выпуклого многогранника D, представляющего собой область допустимых решений задачи (*),и наоборот.

2. Целевая функция z ЗЛП (*) достигает своего оптимума в крайней точке выпуклого многогранника D, порожденного условиями задачи (*). Если целевая функция z ЗЛП (*) достигает своего оптимума более чем в одной крайней точке выпуклого многогранника D, порожденного условиями задачи (*), то она достигает своего оптимума в любой точке, являющейся выпуклой комбинацией данных крайних точек.

Опр. Упорядоченный набор n-чисел называется n-мерным вектором или n-мерной точкой, где координаты n-мерного вектора. Множество n-мерных векторов, для которых определены операции сложения и умножения вектора на число называется n-мерным векторным пространством.

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

Рассм. в пространстве две точки и . Радиус вектора этих точек обозн. и .

Опр. Отрезком n-мерного пространства, соединяющим концы векторов и называется множества этого пространства, удовлетворяющих соотношению

Теорема. Множество решений СЛАУ есть выпуклое множество. Система ограничений ЗЛП: (1.1) (1.2.)

Множество допустимых решений системы ограничения ЗЛП есть пересечение множеств всех решений системы уравнений (1.1) и неравенств (1.2) - это множество выпуклое.

Теорема. Каждому опорному решению системы ограничений ЗЛП соответствует крайняя точка множества допустимых решений системы ограничений и наоборот каждой крайней точке множества допустимых решений системы ограничений соответствует опорное решение этой системы.

Теорема. Множество допустимых решений системы ограничений основной ЗЛП есть выпуклый многогранник.

7. Геометрическая интерпретация и графический метод решения задачи ЛП. Многогранник допустимых решений и оптимальное решение ЗЛП

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

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

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

Рассмотрим стандартную задачу ЛП относительно двух переменных:

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

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

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

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

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

Геометрическая интерпретация целевой функции.

Выражение целевой функции

в зависимости от значения Z представляет собой семейство параллельных прямых, называемых линиями уровня. Причем в точке (0,0) целевая функция Z=0, а с увеличением Z прямые семейства «приближаются» к границе области допустимых решений, которые определяются системой линейных неравенств.

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

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

.

Направление вектора показывает направление возрастания целевой функции, а противоположный вектор (антиградиент) - направление убывания целевой функции.



8. Аналитические методы решения ЗЛП. Симплексный метод решения задачи линейного программирования (аналитический симплекс-метод)

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

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

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

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

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

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

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

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

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



Таблица 1.

базисные переменные	Свободные члены в ограничениях	Небазисные переменные
		x1	x2	...	xl	...	xn
xn+1	b1	a11	a12	...	a1l	...	a1n
xn+2	b2	a21	a22	...	a2l	...	a2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+r	b2	ar1	ar2	...	arl	...	arn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+m	bm	am1	am2	...	aml	...	amn
F(x)max	F0	-c1	-c2	...	-c1	...	-cn

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

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

Пятый шаг. Если Вы дошли до пятого шага, значит нашли решение, которое допустимо. Однако, это не значит, что оно оптимально. Оптимальным оно будет только в том случае, если положительны все элементы в F-строке. Если же это не так, то необходимо улучшить решение, для чего находим для следующего перерасчета ведущие строку и столбец по следующему алгоритму. Первоначально, находим минимальное отрицательное число в строке F, исключая значение функции. Столбец с этим числом и будем ведущим. Для того, что бы найти ведущую строку, находим отношение соответсвующего свободного члена и элемента из ведущего столбца, при условии, что они положительны. Минимальное отношение позволит определить ведущую строку. Вновь пересчитываем таблицу по формулам, т.е. переходим к шагу 3.

Шестой шаг. Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена сверху и Fmax->?. Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.

10. Двойственность в линейном программировании. Взаимно-двойственные задачи и их свойства. Виды математических моделей двойственных задач

Основные определения теории двойственности.

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

Рассмотрим задачу темы 3.8 о планируемом выпуске продукции.

F = 3х1 + 5х2 + 4х3 + 5х4 > max.

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

Количество переменных в двойственной задаче равно количеству неравенств в исходной.

Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.

Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.

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

Заметим, что строки матрицы задачи I являются столбцами матрицы задачи II. Поэтому коэффициенты при переменных yi в задаче II - это, соответственно, коэффициенты i-го неравенства в задаче I.

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

Теоремы двойственности

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

Теорема 1 (первая теорема двойственности).

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

F(x*) = G(y*),

где х*, у* - оптимальные решения задач I и II

Теорема 2 (вторая теорема двойственности).

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

11. Экономическая интерпретация взаимно-двойственных задач. Основные свойства взаимно-двойственных задач

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

Переменные у1, у2, у3 будут обозначать условную предполагаемую цену за ресурс 1, 2, 3 вида соответственно. Тогда доход от продажи видов сырья, расходуемых на производство одной единицы продукции I, равен: 5у1 + 1· у3. Т.к. цена продукции I типа равна 3 ед., то 5у1 + у3 3, в силу того, что интересы предприятия требуют, чтобы доход от продажи сырья был не меньше, чем от реализации продукции. Именно в силу такого экономического толкования система ограничений двойственной задачи принимает вид:

А целевая функция

G = 400y1 + 300y2 + 100y3

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

F(x*) = G(y*)

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

Еще раз обратим внимание на то, что уi - это лишь условные, предполагаемые, а не реальные цены на сырье. Иначе читателю может показаться странным, что например, у1* = 0. Этот факт вовсе не означает, что реальная цена первого ресурса нулевая, ничего бесплатного в этом мире нет. Равенство нулю условной цены означает лишь, что этот ресурс не израсходован полностью, имеется в излишке, недефицитен. Действительно, посмотрим на первое неравенство в системе ограничений задачи I, в котором подсчитывается расход первого ресурса:

5х1* + 0,4х2* + 2х3* + 0,5х4* = 66 < 400.

его избыток составляет х5 = 334 ед. при данном оптимальном плане производства. Этот ресурс имеется в избытке, и поэтому для производителя он недефицитен, его условная цена равна 0, его не надо закупать. Наоборот, ресурс 2 и 3 используются полностью, причем у3 = 4 а у2 = 1, т.е. сырье третьего вида более дефицитно, чем второго, его условная цена больше. Если производитель продукции имел бы возможность приобретать дополнительно сырье к уже имеющемуся, с целью получения максимального дохода от производства, то увеличив сырье второго вида на единицу, он бы получил дополнительно доход в у2 денежных единиц, с увеличением на единицу сырья третьего вида, значение целевой функции увеличилось бы еще на у3 единицы.

Если перед производителем стоит вопрос, "выгодно ли производить какую-либо продукцию при условии, что затраты на единицу продукции составят 3, 1, 4 единиц 1, 2, 3-го видов сырья соответственно, а прибыль от реализации равна 23 единицам", то в силу экономического истолкования задачи ответить на этот вопрос несложно, поскольку затраты и условные цены ресурсов известны. Затраты равны 3, 1, 4, а цены у1* = 0, у2* = 1, у3* = 4. Значит, можно посчитать суммарную условную стоимость ресурсов, необходимых для производства этой новой продукции: 3 · 0 + 1 · 1 + 4 · 4 = 17 < 23. значит продукцию производить выгодно, т.к. прибыль от реализации превышает затраты на ресурсы, в противном случае ответ бы на этот вопрос был отрицательным.

Основные свойства

В одной задаче ищут максимум целевой функции, а в другой минимум.

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

Каждая из задач задана в стандартной форме, причем в задаче на максимум все неравенства вида ”?”, а в задаче на минимум - все неравенства вида “?”.

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

Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

Условия неотрицательности переменных имеются в обеих задачах.

12. Двойственные задачи ЛП. Первая теорема двойственности и ее графическая интерпретация

13. Теорема о взаимосвязи переменных взаимно-двойственных задач, вторая теорема двойственности

14. Объективно-обусловленные оценки и их смысл. Третья теорема двойственности

Теоремы двойственности

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

Теорема 1 (первая теорема двойственности).

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

F(x*) = G(y*),

где х*, у* - оптимальные решения задач I и II

Теорема 2 (вторая теорема двойственности).

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

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

Итак, имеем исходную задачу I, которую мы решили в п. 3.8, и ее оптимальное решение

х* = (0, 40, 0, 100) и F(х*) = 700.

Найдем решение двойственной задачи II у* = (у1, у2, у3) из п. 3.9.1, не прибегая к симплекс-методу, а воспользовавшись второй теоремой двойственности и известным оптимальным планом х*.

Рассмотрим выполнение неравенств задачи I при подстановке х* в систему ограничений.

Поскольку 1, 5, 7 неравенства строгие (имеют знак "<" или ">"), то соответствующие им неравенства в задаче II из пары сопряженных обязаны обратиться в равенства. имеем:

или

т. е. у* = (0, 1, 4) - оптимальное решение.

Заметим, что действительно

G(y*) = 400y1 + 300y2 + 100y3 = 400 · 0 + 300 · 1 + 100 · 4 = 700 = F(x*).

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

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

Установив такую связь, внимательный читатель заметит, что, решив задачу I симплекс-методом и получив последнюю симплекс-таблицу (табл. 3.15), мы фактически решим и задачу II.

Запишем таблицу 2, учитывая соответствие между переменными хi и yj (табл. 2).

Таблица 2.

		у4	у2	у6	у3
	базисные	-х1	-х6	-х3	-х7	свободные
у1	х5					334
у5	х2					40
у7	х4					100
	-F	1	1	1	4	700

В силу соответствия и II теоремы двойственности переменные у1, у5, у7 обязаны равняться 0, т. к. х5, х2, х4>0 строго. А переменные у4, у2, у6, у3 принимают значения из индексной строки 1, 1, 1, 4 соответственно, т. к. им соответствующие переменные х1, х6, х3, х7 = 0, как свободные. Итак, из последней таблицы задачи II, не проводя даже никаких вычислений и пользуясь лишь соответствием переменных:

у* = (у1*, у2*, у3*, у4*, у5*, у6*, у7*) = (0, 1, 4, 1, 0, 1, 0).

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

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

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

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

В постоптимальном анализе исследуются три класса параметров:

1. Компоненты вектора ограничений bt

После нахождения оптимального решения .представляется вполне логичным выяснить, как отразится на оптимальном решении изменение запасов ресурсов. Отметим, что неравенства модели типа "<" обычно могут быть интерпретированы, как ограничения на использование лимитированного ресурса. А ограничения типа ">" могут быть интерпретированы, как некоторые требования к моделируемому процессу.

При анализе изменений запасов ресурсов особенно важны два следующих ас??кта:

> На сколько можно увеличить (уменьшить) запас некоторого ресурса для улучшения полученного оптимального значения целевой функции z?

> На сколько можно снизить (увеличить) запас некоторого ресурса при сохранении полученного оптимального значения целевой функции z?

2. Коэффициенты ЦФ Cj

Определяется пределы допустимых изменений коэффициентов целевой функции.

> Каков диапазон изменения (увеличения или уменьшения) того или иного коэффициента целевой функции, при котором не происходит изменение оптимального решения?

> Насколько следует изменить тот или иной коэффициент целевой функции, чтобы сделать некоторый недефицитный ресурс дефицитным и, наоборот, дефицитный ресурс сделать недефицитным?

1. Существует диапазон изменения А коэффициентов ЦФ как базисных, так и небазисных ??ременных, в кото?ы? текущее оптимальное решение остается оптимальным.

- для небазисных ??ременных существует только нижняя или верхняя граница;

- для базисных - обычно существуют и нижняя и верхняя границы.

2. Изменение коэффициента ЦФ базисной ??ременной всегда приводит к изменению значения ЦФ.

3. Эффект от изменения коэффициентов ЦФ может рассматриваться с двух позиций:

- с точки зрения сбыта нас интересуют равновесные цены;

- с точки зрения производства нас интересует диапазон изменения коэффициента ЦФ, ' в пределах которого текущий план производства остается оптимальным.

Нахождение диапазонов изменения запасов ресурсов

Недефицитные ресурсы

Если в оптимальном решении дополнительная ??ременная S i-ro ограничения базисная, то это ограничение является не связывающим (не активным в точке оптимума), а ресурс - недефицитный. В этом случае значение дополнительной базисной ??ременной дает диапазон изменения, в котором соответствующая компонента di может:

* Уменьшатся (в случае знака ограничения "<")

* Увеличивается (в случае знака ограничения ">").

Пусть S0 - значение соответствующей дополнительной ??ременной в точке оптимума. Тогда решение остаётся допустимым и оптимальным в диапазоне bi+ ?

Дефицитные ресурсы

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

Для ограничения типа "<":

Для ограничения типа ">":

Изменение коэффициентов Ц.Ф.

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

Z = Ств*в,

а одна из компонент вектора Св изменяется. Изменение коэффициента небазисной ??ременной не меняет значения задачи.

Для задачи на mах:

Базисные ??ременные:

Для базисной ??ременной диапазон устойчивости, в котором может изменяться коэффициент Ci , оставляя текущее решение оптимальным, задаётся выражением: Ci + ?

где dj - относительная оценка ??ременной xj в текущем оптимальном решении.

Eсли отсутствуют соответственно.

Не базисные ??ременные:

Для не базисной ??ременной диапазон устойчивости, в котором может изменятся коэффициент Сi оставляя текущее решение оптимальным, задаётся выражением:

Для задачи на min: Базисные ??ременные:

Для базисной ??ременной диапазон устойчивости, в котором может изменяться коэффициент Сi , оставляя текущее решение оптимальным, задаётся выражением: Сi + ?

He базисные ??ременные:

Для не базисной ??ременной диапазон устойчивости, в котором может изменятся коэффициент С; оставляя текущее решение оптимальным, задаётся выражением: (dN) < ? < ?

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

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

Общая характеристика транспортной задачи

Условие:

Однородный груз сосредоточен у m поставщиков в объемах a1, a2, ... am.

Данный груз необходимо доставить n потребителям в объемах b1, b2 ... bn.

Известны Cij , i=1,2,...m; j=1,2,...n -- стоимости перевозки единиц груза от каждого i-го поставщика каждому j-му потребителю.

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

Исходные данные транспортной задачи записываются в виде таблицы:

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

вектора А=(a1,a2,...,am) запасов поставщиков

вектора B=(b1,b2,...,bn) запросов потребителей

матрицы стоимостей:

Математическая формулировка транспортной задачи такова: найти переменные задачи X=(xij), i=1,2,...,m; j=1,2,...,n, удовлетворяющие системе ограничений (цифра 2 на математической модели) , (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1)

17. Транспортная задача. Постановка задачи, типы транспортной задачи

Классическая постановка транспортной задачи общего вида такова.

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

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

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

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

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

Потребители Поставщики	В1	В2	…	Вn	запасы
А1	С11	C12		C1n	а1
А2	С21	C22		C2n	а2
…
Am	Cm1	Cm2		Cmn	аm
Потребности	в1	в2		вn

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

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

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

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

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

Если это неравенство выполняется строго, то задача называется «открытой» или «несбалансированной», если же

,

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

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

В силу ограничений (2) нетрудно увидеть, что ЗТЗ является задачей ЛП и может быть решена симплекс-методом после приведения ее к специальному виду. Но структура системы ограничений имеет некоторою специфику, а именно: каждая переменная хij входит ровно два раза в неравенства системы, и все переменные входят в неравенства системы с коэффициентом 1. В силу этой специфики существует более простой метод решения, называемый методом потенциалов, который, по сути, является некоторой модификацией симплекс-метода. По-прежнему идеей является переход от одного опорного плана к другому, обязательно «лучшему» с точки зрения значения целевой функции. Каждому опорному плану также соответствует своя распределительная таблица. Переход осуществляется от одного плана к другому, пока полученный план не будет удовлетворять условию оптимальности. Необходимо научиться строить первоначальный опорный план. В качестве первоначального плана годится любое решение системы уравнений (2). Заметим, что это система линейных уравнений, состоящая из m + n уравнений с m*n неизвестными. Можно доказать, что линейно независимых уравнений в системе (2) m + n - 1, ввиду условия сбалансированности, т.е. базисных переменных должно быть m + n- 1. Итак, в качестве плана будем представлять себе таблицу размера m • n, в которой должно быть занято m + n - 1 клеток, отвечающих базисным переменным xij.

...