Кирсанова О.В., Семёнова Г.А. Математическое программирование (типовой расчёт)

Подождите немного. Документ загружается.

О.В. Кирсанова

Г.А. Семёнова

МАТЕМАТИКА. МАТЕМАТИЧЕСКОЕ

ПРОГРАММИРОВАНИЕ

В УПРАЖНЕНИЯХ И ЗАДАЧАХ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ОРЛОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

О.В. Кирсанова, Г.А. Семѐнова

МАТЕМАТИКА. МАТЕМАТИЧЕСКОЕ

ПРОГРАММИРОВАНИЕ В УПРАЖНЕНИЯХ

И ЗАДАЧАХ

Рекомендовано Орловским филиалом ИСМО РАО

(Институт содержания и методов обучения Российской академии

образования) в качестве учебно-методического пособия

для студентов высших учебных заведений, обучающихся

по экономическим специальностям (направлениям)

Орел 2010

УДК 519.85(076)

ББК 22.18я7

К43

Рецензенты:

кандидат педагогических наук, доцент кафедры «Математика»

Орловского государственного аграрного университета

Е.В. Александрова,

доктор технических наук, доцент,

заведующий кафедрой «Прикладная математика и информатика»

Орловского государственного технического университета

О.В. Пилипенко

Кирсанова, О.В.

К43 Математика. Математическое программирование в упражне-

ниях и задачах: учебно-методическое пособие для вузов /

О.В. Кирсанова, Г.А. Семѐнова. – Орел: ОрелГТУ, 2010. – 182 с.

Данное пособие содержит упражнения и задачи по основным разде-

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

робными решениями. К

аждое задание представлено 31 вариантом, что

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

альное задание. Использование пособия поможет активизировать са-

мостоятельную работу студентов.

Предназначено студентам высших учебных заведений, обучающим-

ся по экономическим специальностям, изучающим раздел «Математиче-

ское программирование» дисциплины «Математика». Может быть ис-

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

УДК 519.85(076)

ББК 22.18 я7

СОДЕРЖАНИЕ

Введение ..................................................................................................... 4

Глава 1. Линейное программирование.................................................... 5

Глава 2. Транспортная задача .................................................................65

Глава 3. Специальные разделы математического

программирования ...................................................................................91

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

3.2. Параметрическое программирование .................................... 108

3.3. Нелинейное программирование ............................................. 125

Глава 4. Динамическое программирование......................................... 137

4.1. Задача оптимального распраделения инвестиций ................ 138

4.2. Задача выбора оптимальной стратегии эксплуатации

оборудования ................................................................................... 146

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

грузов ................................................................................................ 155

4.4. Задача построения оптимальной последовательности

операций в коммерческой деятельности ...................................... 167

4.5. Задача о прокладке пути между двумя пунктами ................ 172

4.6. Задача о выборе траектории движения .................................. 173

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

ВВЕДЕНИЕ

Настоящее учебно-методическое пособие содержит задания по

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

линей-

ному (симплексный метод, теория двойственности, транспортная за-

дача, целочисленное и параметрическое программирование), нели-

нейному, динамическому программированию.

При написании учебно-методического пособия авторы стре-

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

«Математическое программирование» на подобранных по опреде-

лѐнной системе упражнениях и задачах.

В пособие включены типовые задачи и даются методы их ре-

шения с целью лучшего усвоения материала.

Активная самостоятельная работа студентов – залог успешно-

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

учебного процесса по математике служит система типовых

расчетов.

Основой системы типовых расчѐтов является индивидуализа-

ция заданий. Задачи – расчетные задания, входящие в настоящий

сборник, представлены 31-м вариантом каждая, что позволяет

предложить всем студентам учебной группы индивидуальные

задания.

Расчетные задания выполняются частями по мере продвиже-

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

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

формата. Неверно решенные примеры возвращаются на доработку

с указанием характера ошибки. В специальном журнале препода-

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

Завершающим этапом является защита типового расчѐта. Во

время защиты проверяется умение студента правильно отвечать

на теоретические вопросы, пояснять ход решения задач, решать

задачи аналогичного типа.

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

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

дачи и найдите ее оптимальный план графическим методом. Составь-

те экономико-математическую модель двойственной задачи и найди-

те ее оптимальный план, воспользовавшись формулой

YCА





Малое предприятие в течение планового периода выпускает два

вида продукции: табуретки и стулья. При их производстве исполь-

зуются три вида ресурсов. Данные по их расходу на выпуск одного

изделия и запасы ресурсов приведены в табл. 1.

Таблица 1

Ресурсы

Изделия

Запас ресурса

табуретка

стул

дерево, м

0,02

0,1

гвозди, кг

0,1

0,05

обивка, м

0,3

Прибыль от продажи табуретки и стула соответственно равна

40 и 50 руб. Требуется спланировать количество выпускаемых табу-

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

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

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

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

табуреток (переменная x

) и выпускаемых стульев (переменная x

Выразим через выбранные неизвестные суммарную прибыль от реа-

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

всех табуреток (40x

) и выпускаемых стульев (50x

). Тогда цель зада-

чи (максимизация прибыли) запишется в виде:

F = 40x

+ 50x

 max.

Перейдем к формулировке ограничений. Структура всех трех ог-

раничений одинакова:

Теперь остается выразить полный расход ресурса через выбран-

ные неизвестные x

и x

. Так, расход дерева на выпуск всех табуреток



запас ресурса

расход ресурса

составит 0,02 x

, а на выпуск всех стульев – 0,1 x

(см. первую

строку табл. 1). В сумме это даст полный расход дерева и ограниче-

ние примет вид линейного неравенства: 0,02 x

+ 0,1 x

 4. Анало-

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

0,1 x

+ 0,05 x

 7,

0,3 x

+ 0,3 x

 24.

Объединяя их в систему, получим

0,02 0,1 4,

0,1 0,05 7,

0,3 0,3 24.

















Далее, исходя из смысла введенных переменных (число произво-

димых изделий не может быть отрицательным), на них необходимо

наложить условия неотрицательности: x

 0 и x

 0.

Окончательно выпишем математическую модель задачи в форме

задачи линейного программирования (ЗЛП)

.0,0

,243,03,0

,705,01,0

,41,002,0

max,54

















xxF

Найдем решение этой задачи графическим методом. Для этого

введѐм на плоскости декартову прямоугольную систему координат.

Тогда допустимую область задачи можно изобразить графически, как

множество точек плоскости, координаты которых удовлетворяют

сразу всем неравенствам задачи.

Рассмотрим неравенство 0,02 x

+ 0,1 x

 4. Оно определяет

полуплоскость, лежащую по одну сторону от прямой линии

0,02 x

+ 0,1 x

= 4. Чтобы определить, какую именно полуплоскость

определяет данное неравенство, достаточно взять произвольную точ-

ку плоскости и подставить в неравенство еѐ координаты. Если нера-

венство верно, то полуплоскость, в которой лежит данная точка, – ис-

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

сторону от прямой 0,02 x

+ 0,1 x

= 4. Например, возьмѐм точку (0; 0),

тогда 0,02·0

+ 0,1·0  4 – верно.

Аналогичные исследования можно провести и для неравенств

0,1 x

+ 0,05 x

 7 и 0,3 x

+ 0,3 x

 24. Тогда, с учѐтом неотрицатель-

ности переменных x

, x

, получаем заштрихованную область (рис. 1).

Рис. 1

Известно, что значения целевой функции F = 40x

+ 50x

неогра-

ниченно возрастают, если перемещать прямую 40x

+ 50x

= a в на-

правлении еѐ вектора нормали – градиента

)50 ;40(n

, и убывают,

если перемещать эту прямую в направлении вектора (

n

). Опти-

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

допустимой областью, то есть X* = (50; 30) – оптимальное решение,

max

= 40·50 + 50·30 = 3500 (у.е.).

Итак, для получения прибыли в размере 3500 у.е. необходимо

производить 50 табуреток и 30 стульев.

Составим двойственную задачу.

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

(дерево, гвозди и обивку) у малого предприятия, и необходимо уста-

новить оптимальные цены на эти ресурсы y

, y

(1)

(2)

(3)

0 10 20 30 40 50 60 70 x

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

чтобы затраты на все ресурсы Z в количествах 4, 7 и 24 единиц по це-

нам соответственно y

, y

были минимальны, т. е.

Z = 4y

+ 7y

+ 24y

min.

С другой стороны, малое предприятие, продающее ресурсы, заин-

тересовано в том, чтобы полученная выручка была не менее той сум-

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

в готовую продукцию. На изготовление одной табуретки расходуется

0,02 м

дерева, 0,1 кг гвоздей и 0,3 м

обивки по ценам соответствен-

но y

, y

. Поэтому для удовлетворения требования продавца затра-

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

должны быть не меньше ее цены – 40 у.е., т.е.

403,01,002,0

321

 yyy

Аналогично, на изготовление одного стула расходуется 0,1 м

де-

рева, 0,05 кг гвоздей и 0,3 м

обивки по ценам соответственно

1 2 3

,,y y y

Поэтому для удовлетворения требования продавца затраты на ресур-

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

менее его цены – 50 у.е., т.е.

503,005,01,0

321

 yyy

Таким образом, мы получаем математическую модель двойствен-

ной задачи:

.0,0,0

,503,005,01,0

,403,01,002,0

min,2474

321













yyy

yyyZ

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

лируется следующим образом.

Найдите такой набор цен (оценок) ресурсов Y = (y

, y

), при ко-

тором общие затраты на все ресурсы будут минимальными (целевая

функция) при условии, что суммарная цена ресурсов, используемых

при производстве одной табуретки и одного стула, будет не меньше

прибыли от их реализации (система ограничений).

Оптимальное решение двойственной задачи может быть получено

из равенства:



 ACY

где C

– матрица коэффициентов целевой функции при базисных пе-

ременных в оптимальном решении; A – матрица коэффициентов в ис-

ходной системе ограничений при базисных переменных оптимально-

го решения.

Выясним, какие переменные являются базисными в оптимальном

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

виду:

.0,0,0,0,0

,243,03,0

,705,01,0

,41,002,0

max,5040

54321

521

421

321

















xxxxx

xxx

xxF

Подставляя найденные компоненты x

= 50, x

= 30 оптимального

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

торые выражают остатки ресурсов x

= 0, x

= 0,5, x

= 0. Тогда опти-

мальное решение примет вид X*(50; 30; 0; 0,5; 0). В этом решении ба-

зисными переменными оказались x

, x

, так как они отличны от

нуля. Поэтому:

 

05040

0,02 0,1 0

0,1 0,05 1

0,3 0,3 0











Для матрицы А найдем обратную

1

Определитель матрицы:

   

0,02 0,1 0

0,02 0,1

0,1 0,05 1 1 1 0,02 0,3 0,1 0,3 0,024

0,3 0,3

0,3 0,3 0



           

Алгебраические дополнения:

 

0,05 1

1 0,05 0 1 0,3 0,3;

0,3 0



      

   

0,1 1

1 0,1 0 1 0,3 0,3;

0,3 0



       

 

0,1 0,05

1 0,1 0,3 0,05 0,3 0,015;

0,3 0,3



      