Laby_Mat_metody

2

Автор:

Марзан Сергей Андреевич — заведующий кафедрой математического моделирования БрГУ имени А.С. Пушкина

Рецензент:

Н.Н. Сендер — заведующий кафедрой высшей математики БрГУ имени А.С. Пушкина

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

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

2.2.1Образец оформления решения . . . . . . . . . . . . . . . . . . 16

2.3Варианты задач к лабораторной работе . . . . . . . . . . . . . . . . 19

3.3Инструкция по выполению работы . . . . . . . . . . . . . . . . . . . 21

3.3.1Пример решения задачи линейного программирования . . . . 22

4.2.1Образец оформления решения . . . . . . . . . . . . . . . . . . 34

4.3Варианты задач к лабораторной работе . . . . . . . . . . . . . . . . 36

5.3Инструкция по выполению работы . . . . . . . . . . . . . . . . . . . 38

5.3.1Образец оформления решения . . . . . . . . . . . . . . . . . . 38

5.4Варианты задач к лабораторной работе . . . . . . . . . . . . . . . . 40

6.1Цель работы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

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

6.3Решение задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5

13.3 Исходные параметры модели задачи о назначениях . . . . . . . . . 105

13.4Варианты заданий к лабораторной работе . . . . . . . . . . . . . . . 107

13.4.1Особенности решения задач с булевыми переменными . . . . 108

14.2.1Образец оформления решения . . . . . . . . . . . . . . . . . . 111

14.3Варианты заданий к лабораторной работе . . . . . . . . . . . . . . . 119

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

6

Предисловие

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

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

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

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

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

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

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

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

4.Решение задач, сформулированных на базе построенной математической

модели.

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

7

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

6. Реализация полученного решения на практике.

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

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

Список используемых обозначений:

1)ЛП – линейное программирование.

2)ЦФ – целевая функция.

3)РЗ – распределительная задача.

4)ТЗ – транспортная задача.

8

ЛАБОРАТОРНАЯ РАБОТА 1

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

1.1 Цель работы

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

1.2 Порядок выполнения работы

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

•титульный лист;

•решение задачи графическим методом;

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

1.2.1Образец оформления решения

Задача 0. Собственные средства банка в сумме с депозитами составляют 100 млн. дол. Часть этих средств, но не менее 35 млн. дол., должна быть размещена в кредитах. Кредиты являются неликвидными активами банка, так как в случае непредвиденной потребности в наличности обратить кредиты в деньги без существенных потерь невозможно. Другое дело ценные бумаги, особенно государственные. Их можно в любой момент продать, получив некоторую прибыль или, как правило, без большого убытка. Поэтому существует правило, согласно которому коммерческие банки должны покупать в определенной пропорции ликвидные активы — ценные бумаги, чтобы компенсировать неликвидность кредитов. Считаем, что существует следующее ликвидное ограничение: ценные бумаги должны составлять не менее 30% средств, размещенных в кредитах и ценных бумагах. Пусть c1 = 0, 15 — доходность кредитов, а c2 = 0, 1 — доходность ценных бумаг. Сколько денежных средств банка нужно размещать в кредитах и ценных бумагах, чтобы получить максимальную прибыль? До какого уровня может снижаться доходность кредитов, не меняя при этом оптимальное решение? [1]

Решение. Пусть x1 — средства, размещенные в кредитах (млн. дол.), x2

— средства, вложенные в ценные бумаги. Тогда должны выполняться следующие

Если c1 — доходность кредитов, а c2 — доходность ценных бумаг, то цель банка состоит в том, чтобы получить максимальную прибыль от кредитов и ценных бумаг:

f = c1x1 + c2x2 → max при условиях (1.1) − (1.4).

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

проходящую через начало координат. Перемещая эту прямую параллельно в на-

−→

правлении вектора c , найдем последнюю точку пересечения прямой уровня и допустимого множества X . Это будет точка C и ее координаты получаются при решении следующей системы линейных уравнений:

{

x1 + x2 = 100, 3x1 − 7x2 = 0.

Итак, оптимальный портфель активов (точка максимума) есть (x1; x2)=(70; 30) . Максимальная прибыль составит

fmax = f(x1; x2) = 0, 15 · 70 + 0, 1 · 30 = 13, 5.

10

Рис. 1.1: Графическое решение задачи о банке

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

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

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

Проанализируем графически результаты изменения значения целевого коэффициента c1 , т.е. доходности кредитов.

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

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

Определим тангенсы углов наклона:

1) целевой прямой f(x) = 0, 15c1 + 0, 1c2 , учитывая, что c2 = 0, 1 фиксиро-

вано

tg αf = 0c,11;

2) связывающего ограничения x1 + x2 ≤ 100 tg αBC = 1;