МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ЛЕСОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
ИМЕНИ Г.Ф. МОРОЗОВА»
МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ
Методические указания для самостоятельной работы студентов
по направлению подготовки 38.03.01 – Экономика
Воронеж 2016
3
УДК 512.8
Раецкая, Е. В. Методы оптимальных решений [Текст] : методические указания для самостоятельной работы студентов по направлению подготовки 38.03.01 – Экономика / Е. В. Раецкая, И.В. Сапронов, Н.М. Спирина; М-во образования и науки РФ, ФГБОУ ВО «ВГЛТУ». – Воронеж, 2016. – 29 с.
Печатается по решению учебно-методического совета ФГБОУ ВО «ВГЛТУ» (протокол № 5 от 22 апреля 2016 г.)
|
Рецензент д-р физ.-мат. наук, доцента кафедры математического анализа |
ВГУ |
Зубова С.П. |
4
Введение
Целью изучения дисциплины «Методы оптимальных решений» является воспитание достаточно высокой математической культуры, привитие навыков современных видов математического мышления, ознакомление с математическими свойствами моделей и методами оптимизации; применению методов оптимизации, которые могут использоваться при анализе и решении широкого спектра экономических задач.
Для достижения поставленной цели, при самостоятельной работе решаются следующие задачи:
-самостоятельное усвоение студентом теоретического материала, построенного на основе четких формулировок и доказательстве основных теорем и выработка умения самостоятельно иллюстрировать его примерами и задачами; самостоятельное изучение истории появления наиболее важных понятий и результатов; наряду с изучением основных теоретических результатов при самостоятельной работе с учебными материалами, необходимо обращать внимание на пояснения об их приложениях к другим разделам математики и к техническим наукам, а также к решению экономических задач;
-закрепление теоретического материала и выработка умения самостоятельно
применять |
математические методы в технических и в экономических |
приложениях; |
|
Врезультате самостоятельного освоения дисциплины студент должен:
-знать основные понятия, определения и методы исследования объектов с помощью теорем и формул различных разделов курса математики;
-уметь: четко формулировать и доказывать основные положения курса, решать задачи и примеры по различным разделам курса с доведением решения до практического приемлемого результата (формулы, числа, графика, качественного вывода и т.п.), уметь при решении задач самостоятельно выбирать необходимые вычислительные методы и средства (ПЭВМ, таблицы и справочники); самостоятельно изучать научную литературу по данной дисциплине;
-иметь представление о численных алгоритмах решения математических и прикладных задач его профессиональной области.
Студент по результатам освоения дисциплины «Методы оптимальных
решений» должен обладать способностями:
-решать стандартные задачи профессиональной деятельности на основе информационной и библиографической культуры с применением информационно-коммуникационных технологий и с учетом основных требований информационной безопасности;
-выбрать инструментальные средства для обработки экономических данных в соответствии с поставленной задачей, проанализировать результаты расчетов и обосновать полученные выводы.
5
Содержание
Введение……………………………………………………………………………..3
1.Графический метод решения задач линейного программирования……...5
2.Метод Гаусса-Жордана решения системы линейных уравнений…………6
3.Базисные решения системы линейных уравнений…….……………….…..7
4.Допустимые базисные решения системы линейных уравнений………....9
5.Симплексный метод решения задачи линейного программирования....10
6.Метод потенциалов решения транспортной задачи…………………….....14
7.Метод отсечений решения задач целочисленного программирования…23
Вопросы для контроля.………………………………… ……………………….29
Библиографический список …………………………………………………….29
6
1.ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Рассмотрим стандартную задачу линейного программирования с двумя переменными: найти максимум линейной функции
|
F c1x1 c2 x2 |
(1.1) |
|||||
для переменных x1 , x2 удовлетворяющих системе ограничений-неравенств |
|||||||
a11x1 a12 x2 b1, |
|||||||
|
|
|
|
|
|
b2 |
, |
a21x1 a22 x2 |
|
||||||
|
|
|
|
|
|
|
(1.2) |
........................... |
|||||||
|
|
|
|
|
|
|
|
a |
m1 |
x a |
m2 |
x |
2 |
b |
|
|
1 |
|
|
m |
|||
и условиям неотрицательности |
|
|
|
|
|
|
|
x1 0, |
x2 |
0 . |
(1.3) |
||||
З а м е ч а н и е. Можно рассматривать стандартную задачу линейного |
|||||||
программирования с двумя переменными, в которой требуется найти минимум линейной функции (1.1). Тогда знаки всех неравенств в системе ограниченийнеравенств (1.2) заменяются знаками , а условия (1.3) остаются теми же.
Областью допустимых решений (ОДР) системы неравенств (1.2)
назовем множество всех точек координатной плоскости, координаты каждой из которых являются решением системы неравенств (1.2) и удовлетворяют условиям неотрицательности (1.3). Каждое неравенство ai1x1 ai 2 x2 bi
i 1,2,..., m системы неравенств (1.2) определяет полуплоскость, границей которой является прямая с соответствующим уравнением ai1x1 ai 2 x2 bi , поэтому ОДР системы неравенств (1.2) является пересечением всех этих полуплоскостей и первого координатного угла. Будем считать, что ОДР системы (1.2) не пуста.
Алгоритм решения стандартной задачи линейного программирования с двумя переменными графическим методом:
1) строим область допустимых решений системы неравенств (1.2);
7