Лекция. Основы принятия решений 1.2. Основные понятия системного анализа..8

ОГЛАВЛЕНИЕ

Лекция. Основы принятия решений

 

1.1. Общие положения……………………………………………………….6

1.2. Основные понятия системного анализа………………………………..8

1.3. Основные понятия, применяемые при решении задач

оптимизации ………………………………..…………………………. 12

1.4. Постановка задач принятия оптимальных решений……………….. 13

1.5. Методология и методы принятия решений…………………………. 15

Контрольные опросы………………………………………………...17

Лекция. Математическое моделирование

2.1.Основные понятия..............................................................................18

2.2.Классификация моделей.....................................................................19

2.3.Классификация решаемых задач........................................................21

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

Лекция. Линейное программирование

3.1.Общая постановка задачи.................................................................. 23

3.2. Двойственность в задачах линейного программирования……..… 25

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

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

программирования…………………………………………………….. 28

3.5.Симплексный метод решения задач линейного

программирования……………………………………………………. 35

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

Лекция . Транспортная задача

Линейного программирования

4.2.Алгоритм решения транспортных задач………………………….…... 42 4.2.1.Метод наименьшего… 4.2.2.Метод потенциалов............................................................................. 44

Лекция. Динамическое программирование

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

6.2.Принцип оптимальности Беллмана....................................................66

6.3.Задача распределения средств на 1 год………………………………67

6.4. Задача распределения средств на 2 года............................... ……...71

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

 

7. Лекция. Управление производством

7.1.Задача о замене оборудования ………………………………………72

7.2 Управление запасами. Складская задача ……………………………79

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

Лекция. Элементы теории игр

8.1.Основные понятия………………………………………………………81

8.2.Антагонистические игры ………………………………………………82

8.3.Игры с «природой»..............................................................................85

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

Лекция. Системы массового облуживания

9.1.Формулировка задачи и характеристики СМО………………………94

9.2.СМО с отказами…………………………………………………………96

9.3.СМО с неограниченным ожиданием................................................. 96

9.4. СМО с ожиданием и с ограниченной длиной очереди…………… .97

9.5. Примеры решения задач.....................................................................98

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

 

 

Лекция. Нелинейное программирование

10.1. Основные понятия…………………………………………………….102

10.2. Безусловный экстремум …………………………………..………….103

10.3. Условный экстремум …………………………………………………104

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

 

Перечень задач для решения при усвоении материала………………….105

 

 

Литература............................................................................... 119

Вопросы для самоконтроля……………………………….……………120

 

 

ВВЕДЕНИЕ

 

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

Начало развития методов оптимизации связывают с сороковыми годами двадцатого столетия и получило название «Исследование операций». Само название дисциплины связано с применением математических методов для управления военными операциями.

Одним из первых исследований является работа Л. В. Канторовича

« Математические методы организации и планирования производства», вышедшая в 1939 г., а в зарубежной литературе – вышедшая в 1947 г. работа Дж. Данцинга , посвященная решению экстремальных линейных задач. В 1975 г. Л. В. Канторович стал лауреатом Нобелевской премии за свои работы по оптимальному использованию ресурсов в экономике.

50-е и последующие годы были отмечены широким применением в практику полученных фундаментальных теоретических исследований и связанных с этим переосмыслением потенциальных возможностей новой дисциплины. Важный вклад в развитие новой науки также внесли такие видные ученные, как Дж. Фон. Нейман, Д. Гейл, К. Эрроу, Р. Беллман, Р. Гомори, Е. С. Вентцель, М. К. Гавурин и др .ученные.

Конспект лекций разработан на основании рабочей программы для направления подготовки 080500.62 «Менеджмент».

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

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

Лекция. Основы теории принятия решений.

1.1.Общие положения.

1.2.Основные понятия системного анализа.

1.3.Основные понятия, применяемые при решении задач оптимизации.

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

1.5. Методология и методы оптимальных решений.

 

Общие положения

Человек наделён сознанием, существо свободное и обречено на выбор решений, стараясь сделать всё наилучшим образом.   Теория принятия оптимальных решений в наиболее общем смысле представляет собой совокупность математических и численных…

Основные понятия системного анализа

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

 

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

 

В системном анализе выделяют

-методологию;

-аппаратную реализацию;

-практические приложения.

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

 

Основные определения системного анализа.

  Связь - важный для целей рассмотрения обмен между элементами веществом,…  

Основные понятия, применяемые

при решении задач оптимизации.

 

Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.

 

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

 

Решение - Всякий определенный выбор зависящих от нас параметров.

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

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

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

 

Показатель эффективности - количественная мера, позволяющая сравнивать по эффективности разные решения.

Все решения принимаются всегда на основе информации, которой располагает лицо принимающее решение (ЛПР).

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

Постановка задач для принятия

Оптимальных решений

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

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

 

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

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

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

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

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

-построение модели, которая описывает взаимосвязи между переменными задачи и отражает влияние независимых переменных на значение показателя эффективности.

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

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

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

 

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

 

 

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

 

Все оптимизационные задачи имеют общую структуру. Их можно классифицировать как задачи минимизации(максимизации) M-векторного показателя эффективности W_m(x), m=1,2,...,M, N-мерного векторного аргумента x=(x₁,x₂,...,x_N), компоненты которого удовлетворяют системе ограничений-равенств h_k(x)=0, k=1,2...K, ограничений-неравенств g_j(x)>0, j=1,2,...J, областным ограничениям x_li<x_i<x_ui, i=1,2...N.

 

Все задачи принятия оптимальных решений можно классифицировать в соответствии с видом функций и размерностью W_m(x), h_k(x), g_j(x) и размерностью и содержанием вектора x:

-одноцелевое принятие решений - W_m(x) - скаляр;

-многоцелевое принятие решений - W_m(x) - вектор;

-принятие решений в условиях определенности - исходные данные - детерминированные;

-принятие решений в условиях неопределенности - исходные данные - случайные.

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

 

Более подробно будут рассмотрены задачи линейного программирования (W(x), h_k(x), g_j(x) - линейны), нелинейного программирования (W(x), h_k(x), g_j(x) - нелинейны), целочисленного программирования (x - целочисленны), динамического программирования (x - зависят от временного фактора),математический аппарат одноцелевого принятия решений в условиях неопределенности, , т. е. стохастическое программирование (известны законы распределения случайных величин), теорию игр и статистических решений (закон распределения случайных величин неизвестен).

 

 

1.5 Методология и методы

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

 

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

Метод- способ, прием выполнения тех или иных действий.

Все методы принятия управленческих решений можно объединить в три группы:

· - неформальные (эвристические);

· - коллективные;

· - количественные.

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

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

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

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

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

Решения принимаются руководителем на основе экспертных оценок с помощью одного из следующих принципов:

· - принципа большинства голосов;

· - принципа диктатора - за основу берется мнение одного лица группы;

· - принципа Курно - каждый эксперт предлагает свое решение; выбор не должен ущемлять интересов каждого в отдельности;

 

· - принципа Парето - эксперты образуют единое целое, одну коалицию;

 

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

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

 

В зависимости от типа математических функций, лежащих в основе моделей, различают:

· - линейное моделирование (используются линейные зависимости);

· - динамическое программирование (позволяет вводить дополнительные переменные в процессе решения задач);

· - вероятностные и статистические модели (реализуются в методах теории массового обслуживания);

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

· - имитационные модели (позволяют экспериментально проверить реализацию решений, изменить исходные предпосылки

 

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

1.Что означает понятие «системный анализ»?

2.Определения системного анализа?

3.Сформулируйте принципы системного подхода.

4.Раскройте основные понятия, применяемые при решении задач оптимизации.

5.Какая последовательность действий процесса постановки задачи?

6.Какие методы оптимальных решений вы знаете?

 

Лекция. Экономико - математическое моделирование

Основные понятия.

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

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

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

Применяемые в разных областях человеческой деятельности модели можно классифицировать по разным признакам:

-по характеру моделируемых объектов

-по сферам приложения

-по средствам моделирования

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

 

Классификация моделей

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Классификация решаемых оптимизационных задач.

По уровню информации о ситуации:

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

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

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

По виду информации о ситуации :

1.Статический вид – информация о ситуации не меняется во времени и известна заранее.

2.Динамический вид – информация о ситуации зависит от времени , прошедшего от начала операции.

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

1.Однокритериальные задачи

2.Монокритериальные задачи

 

По типу критерия оптимальности:

1.Линейные задачи

2.Нелинейные задачи

 

 

По типу области ограничения:

1.Выпуклая область

2.Целочисленная область

3.Булева область

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

1.Что означает понятие «модель»?

2.Классификация моделей.

3.Классификация решаемых оптимизационных задач.

4.Какое решение является оптимальным?

5.Дать определение показателя эффективности.

 

Лекция. Линейное программирование.

 

Общая постановка задачи

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

Виды математических моделей ЛП

Математическая модель задачи ЛП может быть каноничес­кой и неканонической.   Определение.Если все ограничения системы заданы урав­нениями и переменные Xj неотрицательные, то такая модель задачи…

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

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

Математические модели этих задач имеют следующий вид.

 

прямая задача:

двойственная задача:

 

 

Эти задачи экономически могут быть сформулированы следующим образом.

 

Прямая задача:сколько и какой продукции х_i(i-1, 2, … , n) надо произвести, чтобы при заданных стоимостях единицы продукции С_i, объемом имеющихся ресурсов b_j (j=1,2,…, m) и нормах расхода ресурсов а_ij максимизировать выпуск продукции в стоимостном виде.

Двойственная задача:какова должна быть оценка единицы каждого ресурса y_j (j=1, 2,…, m), чтобы при заданных b_j, c_i и а_ij минимизировать общую оценку затрат на все ресурсы.

Правилапостроения двойственной задачи по имеемой прямой задаче:

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

2.В задаче на максимум ограничения неравенства имеют вид – ≤, а в задаче на минимум – ³;

3.Каждому ограничению прямой задачи соответствует переменная двойственной задачи, в другой модели ограничению двойственной задачи соответствует переменная прямой задачи;

4.Матрица системы ограничений двойственной задачей получается из матрицы из матрицы систем ограничений прямой задачи транспонированием;

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

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

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

 

 

Пример:

Прямая задача:

Двойственная задача:

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

Взаимосвязь решений прямой и двойственной задач находится из трех теорем двойственности.

 

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

 

Первая теорема двойственности:

Если одна из двойственных задач имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем экстремальные значения целевых функций совпадают Z(X)=Z'(Y). Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.

 

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

 

 

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

Вторая теорема двойственности:

 

Для того чтобы план Х^* и Y^* пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:

 

 

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

 

 

если < b_j, то ;

 

если > 0, то .

 

Аналогично,

если > ;

если >0 то .

 

Экономически это означает, что если по некоторому оптимальному плану X^*= производства расход j-го ресурса меньше его запаса b_j, то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его j-й элемент больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс, т.е. полностью используемый по оптимальному плану производства, имеет положительную оценку, а избыточный ресурс, т.е. не используемый полностью имеет нулевую оценку.

Третья теорема двойственности:

 

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

 

В последнем выражении дифференциалы заменим приращениями. Тогда получим выражение:

,

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

 

3.4 Геометрический метод решения задач

линейного программирования

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

 

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

 

Для нахождения экстремального значения целевой функции при графическом решении задач ЛП используют вектор gradZ на плоскости Х₂ОХ₂ .

Этот вектор показывает направление наискорейшего изменения целевой функции. Координатами вектора grandZ являются коэффициенты целевой функции Z(x).

 

Алгоритм геометрического метода решения задач ЛП.

  1.Построить координатные оси Х1ОХ2 и с учетом коэффициентов уравнений системы…  

Рассмотрим задачу.

    Ресурсы Вид товара Объем ресурсов …  

Анализ решения данной задачи.

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

Симплексный метод решения задач ЛП

Общая постановка задачи

Симплексный метод – метод последовательного улучшения плана.

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

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

 

Алгоритм симплексного метода

1.Математическую модель задачи привести к каноническому (стандартному) виду.   2. Построить начальную симплекс-таблицу исходя из стандартного вида.

Задача

На предприятии имеется возможность выпускать n видов продукции (1,2,…n). При ее изготовлении используются ресурсы Р1, Р2, Р3. Размеры прямых затрат ресурсов ограничены соответственно величинами b1, b2, b3. Расход i –го ресурса на единицу продукции j-того вида составляют aij. Цена единицы продукции j-того вида равна cj ден. ед. Сформулировать прямую и двойственную задачу и раскрывать экономический смысл всех переменных.

 

Требуется:

Найти оптимальный план симплекс-методом.

Найти решение двойственной задачи

Указать дефицитность ресурсов

Обосновать эффективность плана производства

Оценить целесообразность приобретения ресурса

Оценить целесообразность выпуска новой продукции

Данные :

b1 = 25, b2 = 30, b3 = 42

a11= 2, a12= 3, a13= 2, a14= 1

a21= 4, a22= 1, a23= 3, a24= 2

a31= 3, a32= 5, a33= 2,a34= 2

c1= 6, c2= 5, c3= 4, c4= 3

Математическая модель прямой задачи

 

max (Z= 6x1+5x2+4x3+3x4)

2x1+3x2+2x3+x4< 25

4x1+x2+3x3+2x4< 30

3x1+5x2+2x3+2x4< 42

x1, x2, x3, x4 > 0

Математическая модель двойственной задачи

 

min (Z*= 25y1+30y2+42y3)

2y1+4y2+3y3> 6

3y1+y2+5y3> 5

2y1+3y2+2y3> 4

y1+2y2+2y3> 3

y1, y2, y3, y4 > 0

 

Стандартный вид

min (Z= -6x1-5x2-4x3-3x4) 2x1+3x2+2x3+x4+S1=25 4x1+x2+3x3+2x4+S2=30

Анализ решения

Продукции 1 вида производим 6,5 ед., второго вида 4 единицы, третьего и четвертого вообще не производим. Прибыль при этом составит 59 ден. единиц. …   Ресурс 1 типа стоит 1,4 ден. ед., 2 типа – 0,8 ден. ед. Третий тип ресурса у нас остался в количестве 2,5 ед., поэтому…

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

1.Определение математической модели экономической задачи.

2.Виды математических моделей ЛП.

3.Составление математической модели.

4.Экономическая формулировка математической модели прямой и двойственной задач.

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

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

7. Первая теорема двойственности.

8. Вторая теорема двойственности.

9. Третья теорема двойственности.

10.Алгоритм геометрического метода решения задач ЛП.

11.Симплексный метод решения задач ЛП и его применение.

12.Алгоритмм симплексного метода.

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

Лекция. Транспортная задача

 

 

Постановка задачи. Математическая модель

Транспортной задачи.

  Однородный груз сосредоточен у m поставщиков в объемах а1, а2, …, аm. Данный груз необходимо доставить n потребителям в объемах, b1, b2, … , bn.

Математическая модель транспортной задачи

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

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

 

1.Составить опорный план, т.е. начальное приближение.

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

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

Замечание: Метод северо – западного угла для составления исходного плана не используем.

Метод наименьшего элемента.

1.Сбалансировать задачу (убедиться, что задача сбалансирована). 2.Определить свободную клетку с наименьшей стоимостью перевозки. Если таких… 3.В выбранную клетку поставить максимально возможную грузоперевозку для потребителя от поставщика.

Метод потенциалов.

Выбрать переменную Ui или Vj, которой соответствует наибольшее количество занятых клеток, приравнять её к нулю, решить систему уравнений… 2.Для всех свободных клеток составить и проверить выполнение неравенств: Условия оптимальности: если для всех свободных клеток выполняется это неравенство, то тогда найден оптимальный план. …

Примеры решения транспортных задач.

Пример №1

Условие: Студенческие отряды СО-1, СО-2 и СО-3 численностью 70, 99 и 80 человек принимают участие в сельскохозяйственных работах. Для уборки картофеля на полях П₁, П₂, П₃ и П₄ необходимо выделить соответственно 47, 59, 49 и 43 человека. Производительность труда студентов зависит от урожайности картофеля, от численности отряда и характеризуется для указанных отрядов и полей в центнерах на человека за рабочий день и представлена в матрице:

 

Сумма = 198

Bj Ai	П1	П2	П3	П4
СО-1		3	7	2	5
СО-2		2	3	4	6
СО-3		6	4	3	5

 

Сумма = 249

 

Требуется:

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

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

 

Решение:

Проверяем задачу на сбалансированность.

 

Общее количество человек в студенческих отрядах на 51 больше требуемого общего количества человек для уборки картофеля.

Задача является не сбалансированной.

Чтобы сбалансировать задачу, добавляем фиктивное картофельное поле, для уборки которого нужно выделить 51 человека. Производительность труда студентов на фиктивном поле принимаем равной НУЛЮ.

 

Составляем исходную таблицу

Табл.1

Сумма = 249

Bj Ai	П1	П2	П3	П4	П5
СО-1		3	7	2	5	0
СО-2		2	3	4	6	0
СО-3		6	4	3	5	0

Сумма = 249

 

Обозначения:

П₅ – фиктивное картофельное поле;

С_ij – производительность труда студентов i -го СО на j – м картофельном поле;

X_ij – количество студентов, направляемое из i -го СО на j-ое картофельное поле;

U_i – условные оценки СО;

V_j – условные оценки картофельных полей

 

 

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

Математическая модель прямой задачи:

 

Целевая функция (на максимум)

Система ограничений:

Математическая модель двойственной задачи.

Решаем задачу по методу максимального элемента.

Составляем опорный план (табл. 2) Табл.2 Bj Ai П1 П2 П3 П4 П5 …  

Базисных клеток 7. План не вырожден.

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

 

Задаем U₂ = 0 и определяем значения потенциалов.

Вычисляем оценки для всех незаполненных клеток (D_ij)

 

 

Опорное решение не является оптимальным, так как имеются отрицательные оценки.

Переходим к следующему плану.

  Осуществляем сдвиг по циклу и строим следующий план (табл. 3) .

Табл. 4

 

Bj Ai	П1	П2	П3	П4	П5	Ui
СО-1		3	59 7	2		11	U1=0
5	0
СО-2		2	3	49 4	43 6	7 0	U2= 0
СО-3		47 6	4	3	5	33 0	U3 =0
Vj	V1=6	V2=7	V3=4	V4=6	V5= 0

 

Проверяем план на оптимальность методом максимального

элемента, как в п.З.

 

 

Задаем U₂ = 0 и определяем значения потенциалов.

Вычисляем оценки для всех незаполненных клеток (D_ij)

план табл. 4 оптимален.

 

Определяем значение целевой функции прямой и двойственной задачи:

 

Исходя из первой теоремы двойственности в условии нашей задачи Z_max=Z_min=1149 (Z=Z’) последний план оптимален

Ответ:

1.Чтобы за рабочий день было убрано максимально возможное количество картофеля, следует распределить студентов по полям следующим образом:

– Из СО-1 выделить 59 человек для уборки картофеля на втором поле П₂, а 11 человек останутся в СО;

– из СО-2 выделить 49 человек для уборки картофеля на П_З и 43 человека для уборки картофеля на П₄, а 7 человек останутся в СО;

– из СО-3 выделить 47 человек для уборки картофеля на П₁, а 33 человека оставить в СО.

2.При данном оптимальном распределении студентов с четырех полей будет убрано 1149 центнеров картофеля.

 

 

Пример № 2

План перевозок:

 

Поставщики Аi	Потребители Вj:
	Запасы аi	Себестоимость	В1	В2	В3	В4
А1
А2
А3

 

 

Решение:

 

Проверяем на сбалансированность

 

 

Задача не сбалансированная. Введем фиктивного потребителя В₅ с потребностью в грузе, равной 200 ед. Стоимость перевозки для фиктивного потребителя определим равной нулю.

В качестве общей стоимости C_ij¹ будем брать сумму затрат на доставку единицы продукции C_ij из соответствующего пункта и ее себестоимость C_i в этом пункте.

C_ij¹=C_ij + C_i

Математическая модель прямой задачи

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

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

1.Как сформулировать постановку транспортной задачи?

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

3.Как составить математическую модель прямой и двойственной транспортной задачи?

4.Какая клетка в плане транспортной задачи называется «базисной» и какая «свободной»?

5.Приведите пример сбалансированной и несбалансированной транспортной задачи. Как сбалансировать исходный план транспортной задачи?

6.Поясните понятие «вырожденность» и «невырожденность» плана. Как построить «невырожденный» план?

7.Алгоритм метода наименьшего (наибольшего) элемента.

8.Метод потенциалов и его алгоритм.

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

10.Какой критерий оптимальности плана транспортной задачи?

11.Поясните понятие «коэффициент перераспределения груза – W» и как он определяется?

12.Как построить контур перераспределения W?

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

 

Лекция. Целочисленное программирование.

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

В ряде экономических задач, относящихся к задачам линейного программирования, элементы решения должны выражаться в целых числах. В этих задачах… Задача целочисленного программирования формулируется следующим образом: Найти такое решение план Х=(х1, х2,…, хn), при котором линейная функция принимает максимальное или минимальное…

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

 

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

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

Если же полученное оптимальное решение не целочисленное, то строится дополнительное линейное ограничение. Оно обладает следующими свойствами:

1.Оно должно быть линейным;

2.Должно отсекать найденный оптимальный не целочисленный план;

3.Не должно отсекать ни одного целочисленного плана.

Алгоритм графического метода решения задачи

Целочисленного программирования.

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

Пример решения задачи целочисленного программирования.

Условие задачи.

Решение: 1.Находим координаты точек каждого линейного уравнения системы ограничений и строим прямые

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

1.Сформулируйте постановку задачи целочисленного программирования.

2.Математическая модель задачи целочисленного программирования, ее особенности.

3.Метод ветвей и границ и его применение.

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

5.Как построить граф целочисленной области возможных решений задачи?

6.Как определить целочисленный план и экстремальное значение целевой функции?

7.Сформулируйте задачу о коммивояжере.

8.Какие экономико-математические модели могут быть сведены к задаче о коммивояжере ?

9.Как построить математическую модель задачи о коммивояжере ?

10.Как называются переменные в математической модели задачи о коммивояжере ?

 

 

6.Лекция. Динамическое программирование.

 

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

Динамическое программирование – раздел оптимального программирования (оптимального управления), в котором процесс принятия решения и управления,… Динамическое программирование позволяет свести одну сложную задачу со многими… Экономический процесс является управляемым, если можно влиять на ход его развития.

Принцип оптимальности Беллмана.

Суть принципа: Каковы бы ни были начальное состояние на любом шаге и управление, выбранное на… Использование данного принципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с…

Задача распределения средств на 1 год.

 

Пример: имеется запас средств, который нужно распределить между предприятиями, чтобы получить наибольшую прибыль. Пусть начальный капитал S₀=100 д.ед.Функции дохода предприятий даны в матрице прибылей по каждому предприятию.

 

Х	1 предприятие f (х1)	2 предприятие f (х2)	3 предприятие f (х3)	4 предприятие f (х4)

Решение:

Схема решения:

 

 

4 предприятия Условная оптимизация

денег всего S₀=80

 

 

S_o____Iпр____S₁____IIпр_____S₂____IIIпр____S₃____IVпр________S₄

1шаг 2 шаг 3 шаг 4 шаг

х₁ х₂ х₃ х₄

f(x₁) f(x₂) f(x₃) f(x₄)

 

F₄=max{f(x₄)}

Безусловная F₃=max{ f(x₃)+F₄}

оптимизация F₂=max{ f(x₂)+F₃}

 

F₁=max{ f(x₁)+F₂}

 

Используется принцип Беллмана:

 

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

 

 

математическая модель прямой задачи:

 

Экономический смысл переменных:

 

x_i – количество денег, вкладываемых в i предприятие.

S_i – количество денег, оставшихся после вложения в i-предприятие (состояние системы на i-шаге);

F(x_i) – прибыль от вложенной суммы денег;

S₀ – начальный капитал.

 

 

Рассмотрим 4-й шаг:

На 4-ом предприятии может остаться либо 0, либо 20, либо 40, либо 60, либо 100 д.ед.Тогда прибыль от вложения денег можно получить следующую.

 

S3	Х4	f (x4)	F4

Рассмотрим 3-й шаг:

На 3-ем и 4-ем предприятии может остаться либо 0, либо 20, либо 40, либо 60, либо 100 д.ед. Рассмотрим первую возможность. Если 3-му предприятию мы выдаем 20 д.ед. то 4-му предприятию ничего не остается, и наоборот. Соответственно 40 д.ед.можно поделить так (0;40), (20;20);

60 д.ед. – (0;60), (20;40), (40;20), (60;0).

 

Прибыль от вложения денег в 3-е предприятие берется в исходной матрице прибылей, а прибыль от вложений, денег в 4-е предприятие берется из таблицы предыдущего шага

 

Прибыль на 3-м шаге берется максимальной по каждому вложению.

 

Вклад	Проект	Остаток	Прибыль из матрицы	Прибыль за шаг		Прибыль на шаге
S2	Х3	S3	f (x3)	F4	f+F	F3

Рассмотрим 2-й шаг.

Рассмотрим 1-й шаг.

  Анализ результатов:  

Лекция . Управление производством . Управление запасами.

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

Поэтому возникает задача наиболее подходящего момента замены оборудования.

 

7. 1 Управление производством.

Задача о замене оборудования.

 

Рассмотрим задачу о замене оборудования на следующем

ПРИМЕРЕ:

 

 

В начале планового периода продолжительностью N = 4 года имеется оборудование, возраст которого t, причем оборудование не должно быть старше 6 лет (примем t = 2 года).

 

ИЗВЕСТНЫ:

- r(t) - стоимость продукции, произведенной в течение каждого года планового периода с помощью этого оборудования;

- U(t) - ежегодные затраты, связанные с эксплуатацией оборудования (эти характеристики зависят от возраста оборудования;

- s - остаточная стоимость оборудования (принимаем s = 4 д.ед.), не зависящая от его возраста;

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

 

 

ТРЕБУЕТСЯ:

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

 

1. Составить матрицу максимальных прибылей F_n(t) за 4 года;

2.Сформулировать по матрице максимальных прибылей оптимальные стратегии замены оборудования возрастов t₁ и t₂ лет в плановом периоде, продолжительностью 4 и 3 года.

 

Таблица соответствия стоимости продукции и затрат от возраста

 

Возраст t
Ст.продукции r(t)
Ст.расходов u(t)

 

 

РЕШЕНИЕ:

Математическая модель задачи:

Z = ΣF_i(x_i)→max

сохранить

x_i - управление

 

заменить

 

Экономический смысл переменных:

N - плановый период эксплуатации оборудования;

Z_C - прибыль в случае сохранения оборудования;

Z_З - прибыль в случае замены оборудования;

S₀ - первоначальное состояние системы;

S^H_i - предполагаемый возраст оборудования в начале i-го периода, т.е. после того, как мы примем решение сохранить или заменить его;

S_i - возраст в конце i-го периода;

r(t) - прибыль от эксплуатации;

u(t) - расходы на эксплуатацию;

s - остаточная стоимость оборудования;

p - стоимость нового оборудования;

t - возраст оборудования;

f_i - доход на i-ом шаге;

F_i - максимальный доход на i-ом шаге.

 

Прибыль, если в начале года выбрано управление «сохранение» оборудования:

Z_c = r(t) - u(t)

Прибыль в случае «замены»:

Z_З = s - p + r(0) - u(0)

 

Состояние системы (S) характеризуется возрастом оборудования

t = 0, 1, …. Значение t = 0 соответствует новому оборудованию.

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

Основное функциональное уравнение на последнем N-ом шаге:

F_N(S_N-1, x_N) = max Z_N(S_N-1, x_N)

 

При произвольном шаге (i<N) основное функциональное уравнение принимает вид

F_i(S_i-1, x_N) = max {Z_i(S^H_i, x_i) + F_i+1(S_i)}

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

- при управлении «сохранение»

F_i(S^H_i, x_i) = r(S_i, x_i) - u(S^H_i)

- при управлении «замена»

Z_i(S^H_i, x_i) = s - p + r(0) - u(0)

 

 

Для нашего примера расчет начинается с последнего, четвертого года планового периода:

F₄(S₃, x₄) = max Z₄(S^H₃, x₄)

при этом:

- в случае «сохранения» оборудования:

Z₄(S^H₄, x₄) = r(S^H₄) - u(S^H₄)

- в случае «замены»:

Z₄(S^H₄, x₄) = 4 - 13 + 27 - 15 = 3

Составляется 1-ая таблица, рассматриваемая все возможные НАЧАЛЬНЫЕ состояния оборудования, т.е. его возраст S₃ = 1 - 6 лет, начиная с конца - последнего шага.

 

Таблица 1. F₄(S₃, x₄) = max Z₄(S^H₃, x₄)

Шаг 4

Возраст S3 в конце 3-го шага	Управление x4	Предполагаемый возраст SH4 в начале 4-го шага	Прибыль Z4	Max доход на F4 шаге
	Сохранение			11сохр
Замена
	Сохранение			10сохр
Замена
	Сохранение			9сохр
Замена
	Сохранение			8сохр
Замена
	Сохранение			6сохр
Замена
	Сохранение			3замен.
Замена

 

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

Теперь анализируем ситуацию перед третьим годом исследуемого периода.

F₃(S₂, x₄) = max {Z₃(S^H₃, x₃) + F₄(S₃)}

при этом:

- в случае «сохранения оборудования»

Z₃(S^H₃, x₃) = r(S^H₃) - u(S^H₃)

- в случае «замены»

Z₃(S^H₃, x₃) = 4 - 13 + 27 - 15 = 3

Следует оптимизировать расходы за последний и предпоследний годы (за двухлетний период).

Оптимальная прибыль за 4-ый год берется из таблицы 1.

Учтем, что S^H₂ - возраст оборудования в начале третьего года сразу после принятия решения о его «сохранении» или «замене»;

S₃ - возраст оборудования к концу третьего года.

Данные в колонку F₄ переносятся из предыдущей таблице в соответствии со значением параметра S₃.

 

 

Таблица 2.F₃(S₂, x₄) = max {Z₃(S^H₃, x₃) + F₄(S₃)} Шаг 3

S1	x3	SH2	Z3 из таблицы 1	Возраст S3 в конце 3 шага	F4	Z3 + F4	F3
	Сохранение						21сохр
Замена
	Сохранение						19сохр
Замена
	Сохранение						17сохр
Замена
+4	Сохранение						14сохр
Замена
	Сохранение						14замен
Замена
	Сохранение			-	-	-	14замен
Замена

 

 

Также проводится условная оптимизация на начало второго года (шаг 2) и составляется таблица 3.

 

Таблица 3. F₂ (S_1,x₄) = max {Z₂(S^H₂, x₂) + F₃(S₂)} Шаг 2

S1	x2	SH1	Z2	S2	F3	Z2 + F3	F2
	Сохранение						30сохр
Замена
	Сохранение						27сохр
Замена
	Сохранение						24замен
Замена
	Сохранение						24замен
Замена
	Сохранение						24замен
Замена
	Сохранение			-	-	-	24замен
Замена

 

Также проводится условная оптимизация на начало первого года (шаг 1) и составляется таблица 4, которая завершает условную оптимизацию.

Таблица 4.F₁ (S_0, x₄) = max {Z₁(S^H₁, x₁) + F₂(S₁)}Шаг 1

S0	х1	SH1	Z1	S1	F2	Z1 + F2	F1
	Сохранение						38сохр
Замена
	Сохранение						34сохр
Замена
	Сохранение						33сохр
Замена
	Сохранение						33замен
Замена
	Сохранение						33замен
Замена
	Сохранение			-	-		33замен
Замена

 

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

Для наглядности основные результаты, содержащиеся в последних столбцах четырех последних построенных таблиц, оформляются в виде сводной таблицы, которая называется матрицей максимальных прибылей, и выделяются элементы, ниже которых расположены показатели суммарной прибыли, соответствующие выбору управления «ЗАМЕНА».

 

Элементы, расположенные выше линии выделения, находятся в области «СОХРАНЕНИЯ» оборудования.

 

Матрица максимальных прибылей

 

t	ГОДЫ
1-4	2-4	3-4
0		-	-	-
			21
2	34			10
		24
	33
			14
				3

 

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

 

В матрице прибылей для t = 2 в первой колонке стоит суммарная прибыль 34 д.ед. за четыре года, при этом выбор управления «СОХРАНЕНИЕ».

 

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

 

Оптимальная прибыль за второй - четвертый годы - 24 д.ед., и мы находимся в области «ЗАМЕНЫ» оборудования, следовательно, к началу 3-го года оборудование будет иметь возраст 1 год.

 

Прибыль за третий - четвертый годы для такого оборудования равна

21 д.ед., за последний четвертый год - 10 д.ед. (при возрасте t = 2).

 

ВЫВОД: рекомендуется замена оборудования в начале 2-го года

Эксплуатации.

Управление запасами. Складская задача.

Складская задача относится к динамическим детерминированным задачам управления запасами. Следовательно, для решения этой задачи можно применить принцип Беллмана.

 

 

Рассмотрим задачу.

Планируется деятельность предприятия на три месяца.

 

ЗАДАНЫ:

- начальный уровень запасов S₀ = 20

- остаток запасов S₃ = 0

- затраты на пополнение φ(x) = 0.4x

- затраты на хранение ψ(y) = 0.2y + 1 в данном периоде в зависимости

от y - среднего уровня хранимых запасов.

 

ОПРЕДЕЛИТЬ:

- размеры пополнения запасов в каждом месяце для удовлетворения заданного расхода d₁ = 30, d₂ = 20, d₃ = 30 из условий минимизации суммарных затрат.

Используются формулы Уилсона:

Средний уровень хранения y_k = d_k/2 + S_k

Уравнение состояния S_k = S_k-1 + x_k - d_k

Решение:

Задача относится к динамическому программированию и решается с применением принципа Беллмана.

1 этап - от конца к началу проводим условную оптимизацию.

Третий месяц

S2	x3	y3	φ(x3)	ψ(y3)	φ + ψ	Z3

 

 

Второй месяц

 

Первый месяц

x1 = 10 S1 = 0 y1 = 15 φ(x1) = 4 ψ(y1) = 4 x2 = 20 S2 = 0 y2 = 10 φ(x2) = 8 ψ(y2) = 3 x3 = 30 S3 = 0 y3 = 15 φ(x3) = 12 ψ(y3) = 4

Основные понятия.

 

 

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

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

Игра называется антагонистической или игрой с нулевой суммой, если выигрыш одного из игроков равен проигрышу другого, поэтому для полного «задания» игры достаточно указать величину выигрыша первого игрока.

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

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

Такие стратегии называются оптимальными.

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

Матрица, элементы которой характеризуют выигрыш первого игрока (МЫ –игрок А) и проигрыш второго (игрок В) при их возможных стратегиях (обозначается |α_ij|),называется платежной матрицей игры.

Величина α = max min a_ij называется нижней ценой игры –

j i

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

 

Величина β = min max a_ijназывается верхней ценой игры –

i j

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

 

Выигрыш, соответствующий оптимальному решению, называется ценой игры γ. Цена игры удовлетворяет неравенству α ≤ γ ≥ β.Такие игры называются играми в смешанных стратегиях.

Если нижняя и верхняя цены игра совпадают, то их общее значение

α = β = γ чистой ценой игры или седловой точкой. Такие игры называются играми в чистых стратегиях.

Минимаксные стратегии, соответствующие цене игры, являются оптимальными стратегиями, а их совокупность (А_iВ_j) – оптимальным решением или решением игры.

Игра, в которой интересы игроков противоположны называется антагонистичной.

 

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

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

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

 

Антагонистические игры.

Прежде всего, надо уметь находить верхнюю и нижнюю цены игры, т.к. достаточно много игр решается в чистых стратегиях.   Найти нижнюю и верхнюю цены игры для матрицы Ai Bj αi α=max αi …

Геометрический метод решения задач теории игр

Геометрический метод решения игр с нулевой суммой применяется к играм, где хотя бы у одного игрока имеется только две стратегии. Иногда возможно… 1. Игрок А стремится увеличить свой выигрыш, поэтому он не будет использовать… 2. Игрок В стремится уменьшить свой проигрыш, поэтому он не будет использовать стратегии, которые заведомо дают…

Решение.

1. Максиминный критерий Вальда. max min а_ij

^{j i}

Вычислим минимальные значения по строкам min а_ij, а далее из них выберем максимальное.

5 10 18 25 5

А = 8 7 8 23 7

21 18 12 21 12

20 22 19 15 15

 

Таким образом, получаем Н =max min а_ij = 15 при применении стратегии А₄. ^{j i}

Ответ: оптимальной стратегией 1-го игрока А является

стратегия А₄.

Критерий Гурвица.

H= max[γ min аij+(1- γ) max аij] j i i

Критерий Сэвиджа (критерий минимаксного риска).

 

Необходимо построить матрицу рисков.

Для этого:

1) вычислить максимальные значения по столбцам

 

5 10 18 25

А = 8 7 8 23

21 18 12 21

20 22 19 15

21 22 19 25

 

2) вычислить матрицу рисков: r_ij= max а_ij- а_ij

j

21-5 22-10 19-18 25-25 16 12 1 0

r_ij= 21-8 22-7 19-8 25-23 = 13 15 11 2

21-21 22-18 19-12 25-21 0 4 7 4

21-20 22-22 19-19 25-15 1 0 0 10

 

3) вычислить максимальные значения по строкам и из них выберем строку с минимальным значением:

 

16 12 1 0 16

13 15 11 2 15

r_ij= 0 4 7 4 7

1 0 0 10 10

 

Получаем H =minmax r_ij = 7 при применении стратегии А₃.

^{j i}

Ответ: оптимальной стратегией первого игрока является

стратегия А₃.

 

 

4. Критерий Лапласа. _n

Вычислить средние арифметические по строкам [1/n ∑ а_ij]

5 10 18 25 0.25 (5+10+18+25)=14.5 ^j=1

A = 8 7 8 23 0.25 (8+7+8+23)=11.5

21 18 12 21 0.25 (21+18+12+21)=18

20 22 19 15 0.25 (20+22+19+15)=19

_n

Получаем H =max [1/n ∑ а_ij] =19 при применении стратегии А₄.

^{i j=1}

Ответ: оптимальной стратегией первого игрока является

стратегия А₄.

 

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

А1 5 10 18 25 H = max∑Pj аij А2 8 7 8 23 j j=1 А3 21 18 12 21

I. Формулировка задачи и характеристики СМО

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

СМО с отказами.

Заявка, поступившая в систему с отказами и нашедшая все каналы занятыми, получает отказ и покидает систему необслуженной. Показателем качества…   9.2.2 Формулы для расчета установившегося режима

СМО с неограниченным ожиданием

Основные понятия

 

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

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

Для таких систем характерно отсутствие отказа в обслуживании, т.е.

P_отк=0 и Р_обс=1.

Для систем с ожиданием существует дисциплина очереди:

1)обслуживание в порядке очереди по принципу «первым пришел – первым обслужен»;

2)случайное неорганизованное обслуживание по принципу «последний пришел - первым обслужен»;

3)обслуживание с приоритетами по принципу «генералы и полковники вне очереди».

9.3.2 Формулы для расчета установившегося режима

1. Вероятность простоя каналов, когда нет заявок (k=0):

_n

P₀=1/Σ(ρ^к/к!)+ρⁿ⁺¹/n!(n-ρ)

^k=0

Предполагается, что ρ/n<1, т.е. интенсивность нагрузки меньше числа каналов.

2. Вероятность занятости обслуживанием k заявок: P_k= ρ^к P₀/k!, 1≤ k≤ n

3. Вероятность занятости обслуживанием всех каналов: P_n =P₀ρⁿ / n!

4. Вероятность того, что заявка ожидается в очереди: Р_оч= ρⁿ⁺¹/n!(n-ρ)* P₀

5. Среднее число заявок в очереди: _

L_оч= ρⁿ⁺¹/(n+λ)!(n-ρ)²* P₀

6. Среднее время ожидания заявки в очереди: _ _

t_оч= L_оч/λ

7. Среднее время ожидания заявки в СМО: _ _

t_смо= t_оч+ t_обс

8. Среднее число занятых обслуживанием каналов: _

n₃=ρ

9. Среднее число свободных каналов: _ _

n_св= n- n₃ _

10. Коэффициент занятости каналов обслуживания: k₃= n₃/ n

 

11. Среднее число заявок в СМО: _ _ _

z= L_оч+ n₃

СМО с ожиданием и с ограниченной длиной очереди

Основные понятия

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

Основной характеристикой качества системы является отказ заявке в обслуживании.

Ограничения на длину очереди могут быть из-за:

1)ограничения сверх времени пребывания заявки в очереди;

2)ограничения сверх длины очереди;

3)ограничения общего времени пребывания заявки в системе.

 

Формулы для установившегося режима

1. Вероятность простоя каналов, когда нет заявок (k=0): P0=1 : {Σ ρк/к!+ρn+1/n!(n-ρ)[1-(ρ/n)m]} n – число каналов;

А С В

 

Точки А и В являются точками локального экстремума, а точка С является точкой глобального экстремума.

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

 

10.2. Безусловный экстремум

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

 

Найти экстремум функции z=х²+ху+у²-2х-3у.

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

Первая производная по х: z׳_х=2х+у-2

Первая производная по у: z׳_у=х+2у-3

Решим систему уравнений. 2х+у=2

х+2у=3

Получаем критическую точку (1/3; 4/3).

 

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

Вторая производная по х: z׳׳_хх=2

Вторая производная по у: z׳׳_уу=2

Смешанные производные z׳׳_ху=z׳׳_ух=1

Составим определитель 2 1

1 2 ∆ = 4-1=3

 

 

Следовательно, экстремум есть. Так как z=2>0, то в точке (1/3; 4/3) точка минимума.

Условный экстремум

Определить матрицы L и все ее главные миноры порядка больше чем m+1 должны иметь знак (-1)m, где m – число ограничений задачи.   Задача на максимум.

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

  1 ТЕМА. «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ». Задача 1.1.

Табл. 1.1.

Параметр	Номер варианта
а11
а12
а13
а21
а22
а23
а31					5
а32
а33
b1
b2
b3
С1
С2
С3
K
Dbk
Сk

 

Таблица 1.2.

Параметр	Номер варианта
b1
b2
b3
а11
а12
а13
а21
а22
а23
а31
а32
а33
С1
С2
С3

2 ТЕМА. «ТРАНСПОРТНАЯ ЗАДАЧА»

Задача 2.1

 

В пунктах А_i (i=1, 2, 3)производится однородная продукция в количестве а_i единиц. Себестоимость единицы продукции в i-м пункте равна C_i. Готовая продукция поставляется в пункты В_j (j=1, 2, 3, 4), потребности которых составляют b_j ед. стоимость перевозки единицы продукции из пункта A_i в пункт B_j задана матрицей C_ij.

 

Требуется:

1.Написать математическую модель прямой и двойственной задач с указанием экономического смысла всех переменных;

2.Составить план перевозки продукции, при котором минимизируются суммарные затраты по ее изготовлению и доставке потребителям для условия что продукция произведенная в пункте A_i, где себестоимость её производства наименьшая, распределяется полностью;

3.Вычислить суммарные минимальные затраты Z_min;

4.Узнать в какие пункты развозится продукция от поставщиков;

5.Установить пункты, в которых останется нераспределенная продукция, и указать её объем.

Необходимые исходные числовые данные приведены в таблице 2.1.

Задача 2.2.

 

Трудовые бригады Б₁, Б₂, Б₃ численностью, а₁, а₂, и а₃ человек, сформированы для уборки картофеля.

Для уборки картофеля на четырех полях П₁, П₂, П₃ и П₄ необходимо выделить b₁, b₂, b₃, и b₄ работников. Производительность труда работника зависит от урожайности картофеля, а так же от численности бригады и характеризуется для указанных бригад и полей элементами матрицы P_ij (в центнерах на человека за рабочий день).

 

 

Требуется:

 

 

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

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

 

Необходимые исходные числовые данные приведены в таблице 2.2.

Таблица 2.1.

Параметр	Номер варианта
а1
а2
а3
С1
С2
С3
b1					296
b2
b3
b4
С11
С12
С13
С14
С21
С22
С23
С24
С31
С32
С33
С34

 

 

Таблица 2.2.

Параметр	Номер варианта
А1
А2
А3
B1
B2
B3
B4					41
Р11
Р12
Р13
Р14
Р21
Р22
Р23
Р24
Р31
Р32
Р33
Р34

 

3 ТЕМА. «ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ»

Задача 3.1.

 

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

 

Таблица 3.1

 

Вариант	Математическая модель задачи
Целевая функция	Ограничения	Условие неотрица-тельности
			x1, x2 ≥ 0
			x1, x2 ≥ 0
			x1, x2 ≥ 0
			x1, x2 ≥ 0
			x1, x2 ≥ 0
			x1, x2 ≥ 0
			x1, x2 ≥ 0
			x1, x2 ≥ 0
			x1, x2 ≥ 0
			x1, x2 ≥ 0

 

 

ТЕМА. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.

 

Задача 4.1.

 

Выделены денежные средства S₀=100 д.ед. для вложения в инвестиционные проекты для реконструкции и модернизации производства на четырех предприятиях.

По каждому предприятию известен возможный прирост f_i(х)(i=1, 2, 3, 4) выпуска продукции в зависимости от выделенной суммы.

Требуется:

1. Распределить средства S₀ между предприятиями так, чтобы суммарный прирост продукции на всех четырех предприятиях достиг максимальной величины;

2. Используя решение основной задачи, найти оптимальное распределение между тремя предприятиями.

Данные необходимо для решения, приведены в таблице 4.1.

Таблица 4.1.

Параметр	Номер варианта
f1 (20)
f2 (20)
f3 (20)
f4 (20)
f1 (40)
f2 (40)
f3 (40)					6
f4 (40)
f1 (60)
f2 (60)
f3 (60)
f4 (60)
f1 (80)
f2 (80)
f3 (80)
f4 (80)
f1 (100)
f2 (100)
f3 (100)
f4 (100)

 

ТЕМА. УПРАВЛЕНИЕ ПРОИЗВОДСТВОМ.

УПРАВЛЕНИЕ ЗАПАСАМИ.

ЗАДАЧА 5.1

 

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

Оборудование не должно быть старше 6 лет.

 

ИЗВЕСТНЫ:

- стоимость r(t) продукции, произведенной в течение года с помощью этого оборудования;

- ежегодные расходы u(t), связанные с эксплуатацией этого оборудования;

- его остаточная стоимость s;

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

 

ТРЕБУЕТСЯ:

1) составить матрицу максимальных прибылей за 6 лет;

2) составить по матрице максимальных прибылей оптимальные стратегии замены оборудования возрастов t₁ и t₂ лет в плановом периоде продолжительностью 6 и N лет.

 

ВАРИАНТЫ ЗАДАЧ

Для всех вариантов r(t) = 20 - 2t, u(t) = 2 + 2t

 

Таблица5.1

Параметр	Номер варианта
s
р
N
t1
t2

 

 

СКЛАДСКАЯ ЗАДАЧА

ЗАДАЧА 5.2   Торговое предприятие должно в течение 3-х месяцев отпустить со склада некоторое количество товара di , (i = 1, 2, 3).…

ТЕМА. ЭЛЕМЕНТЫ ТЕОРИИ ИГР.

АНТАГОНИСТИЧЕСКИЕ ИГРЫ

ЗАДАЧА 6.1 Из платежной матрицы найти нижнюю и верхнюю цену игры. Упростить матрицу,…  

ТЕМА . СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ

ЗАДАЧА 7.1 Вариант 1. Дежурный по администрации города имеет 8 телефонов. Телефонные звонки поступают с интенсивностью 120 заявок в час.…

ТЕМА . НЕЛИНЕЙНОЕ ПРОГРАМИРОВАНИЕ.

ЗАДАЧА 8.1

Определить безусловный экстремум для целевой функции, заданной в таблице 8.1

 

Таблица 8.1

Номер варианта	Функция
	х²+у²+ху-4х-5у
	ху(1-х-у)
	3х+6у-х²-ху+у²
	2ху-4х-2у
	у²- х²+ху-2х-6у
	х2-у2-3ху
	х2+8у2-6ху+1
	2х2-ху²+5х²+у²
	6х+12у-2х²-2ху+2у²
	2х²+у²-4ху-2х-у+1

 

 

Рекомендуемая литература.

 

1.М.Ю. Афанасьев, Б.П. Суворов. Исследование операций в экономике. Учебное пособие.-М.:Изд.Инфра-М, 2003,-443с.

 

2.Бонди Б. Основы линейного программирования.-М.:Радио и связь,1989.-174с.

 

 

3.Вентцель Е.С. Исследование операций.-М.:Наука,1988.-208с.

 

4.Замков О.О. и др. Математические методы в экономике.-М:Изд-во МГУ,1987.408с.

 

 

5.Исследование операций в экономике,под ред.Н.Ш.Кремера.-М.:Изд.Банки и биржа.-1997.-408с.

 

6.М.С.Красс, Б.П. Чупрынов, Основы математики и ее приложения в экономическом образовании.-М.:Изд.Дело, 2000,-686с.

 

 

7.О.А. Косоруков, А.В. Мищенко. Исследование операций. Учебник для вузов.-М.:Изд. Экзамен,2003,-445с.

 

8.Е.С. Кундышева. Математическое моделирование в экономике. Уч. пособие.-М:Изд «Дашков и К⁰» , 2004,-350с.

9.Экономико – математическое моделирование .Учебник для студентов вузов.Под общ.ред.И.Н.Дрогобыцкого. – изд.»Экзамен»,2004. – 800с

10.Шапкин А.С.,Мазаева Н.П. Математические методы и модели исследования операций:Учебник. – М.:Изд.-торговая корпорация «Дашков и К⁰»,2004.-400 с.

11.М.С.Красс, Б. П. Чупрынов Математические методы и модели для магистрантов экономики: Учебное пособие. – СПб.:Питер,2006.-496с.

 

12. Г. В. Абраменко. Применение системного анализа в технике и экономике. Под ред. Ю. И. Краснощекова.- М.: ЦЭИ Химмаш, 2001. – 190с.

 

13 А. С. Малин. Исследование систем управления. Уч. для вузов. Гос. Университет Высшая школа экономики. – 2-е изд. – М.: изд-во ГУ ВШЭ, 2004. – 399с.

 

14. В. Н. Спициадель. Теория и практика принятия оптимальных решений. Учеб. пособие.М-во общего и проф. образования РФ, Балт. гос. тех.ун-т ВОЕНМЕХ им. Д. Ф. Устинова. – СПб.: Бизнес-пресса,2002. – 394 с.

 

15. П. Д. Шимко. Оптимальное управление экономическими системами.

Учеб.пособие. - СПб. Издательский дом «Бизнес-пресса»,2004. – 240с.

 

 

Вопросы для самоконтроля.

 

1.Основные принципы применения методов математического моделирования. Основные определения.

 

2.Построение математических моделей и их особенности. Постановка задачи об оптимальном плане производства.

 

3.Общая задача ЛП, стандартный вид задачи ЛП.

 

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

 

5.Экономический смысл двойственных задач.

 

6.Экономический смысл теорем двойственности.

 

7.Задача о плане производства при условии ограниченных ресурсов (графический метод).

 

8.Понятие целевой функции задачи линейного программирования. Ее экономический смысл.

 

9.Системы линейных неравенств в математических моделях. Их решение графическим методом.

 

10.Решение задач ЛП симплекс-мотодом. Графическое решение.

 

11.Анализ решения задач ЛП.

 

12.Транспортные задачи. Экономическая постановка ТЗ. Математическая модель прямой и двойственной задачи.

 

13.Транспортная задача. Построение начального допустимого плана. Сбалансированность ТЗ.

 

14.Метод наименьшего элемента ТЗ.

 

15.Метод потенциалов ТЗ.

 

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

 

17.Транспортная задача с возможностью расширения производства.

 

18.Пояснить понятие: план выпуска продукции, оптимальный план производства, целевой функции

 

19.Какие переменные называются базисными, какие свободными. Показать их в модели и в плане производства.

 

20.Пояснить экономический смысл всех переменных в математической модели. Какова их размерность.

 

21.Общая постановка задачи целочисленного программирования. Особенности задачи и ее решения.

 

22. Решение задачи целочисленного программирования методом ветвей и границ. Задача о коммивояжере.

 

23.Математическая постановка задачи о оптимальном размещении капитальных вложений, ее решение.

 

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

 

25.Основные понятия теории игр. Классификация задач теории игр.

 

26. Решение задачи игры с нулевой суммой в чистых стратегиях.

 

27. Решение задачи игры с нулевой суммой в смешанных стратегиях.

 

28. Решение задачи игры с нулевой суммой в смешанных стратегиях геометрическим методом.

 

29. Критерии Байеса и Лапласа для выбора оптимальной стратегии при “играх с природой”.

 

30. Критерии Вальда, Севиджа и Гурвица для выбора оптимальной стратегии при “играх с природой”.

 

31. Решения задач теории игр. Решение задач графическим методом.

 

32.Платежная матрица и ее построение.

 

33.Динамическое программирование и его задачи.

 

34.Общие уравнения алгоритма, реализующие принцип Беллмана в задачах динамического программирования.

35.Задача распределения ресурсов.

 

36.Задача распределения средств между предприятиями.

 

37.Задача о замене оборудования.

 

38.Нелинейное программирование. Методы решения задач НЛП.

39.Основные понятия системного анализа.

40.Основные понятия, применяемые при решении задач

оптимизации.

 

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

 

42.Методология и методы принятия решений.