Введение
1 Моделирование задач линейного программирования
1.1 Задача о кратчайшем пути
2 Решение задач линейного программирования с использованием MicrosoftExcel
2.1 Решение задачи коммивояжера средствами Microsoft Excel
2.3 Решение других задач линейного программирования средствами MS Excel
2.3.1 Задача о назначении
2.3.2 Задача распределения ресурсов
2.3.3 Транспортная задача
2.3.4 Задача на определение оптимального рациона
2.3.5 Задача на определение оптимальной производительной структуры
Заключение
Библиографический список литературы
Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.
Линейное программирование успешно применяется в военной области, сельском хозяйстве, экономике, медицине, транспортной отрасли, в социальных науках. Широкому распространению данного метода способствовали высокоэффективные алгоритмы, реализующие данный метод. В частности задачи оптимального планирования производства также могут быть отнесены к задачам линейного программирования.
К классу задач линейного программирования относится большое количество разнообразных задач планирования и управления, как, например:
1) определение оптимального плана выпуска продукции (задача на оптимальное распределение ресурсов);
2) определение оптимального рациона (оптимизация состава смеси);
3) оптимизация межотраслевых потоков (планирование производства различных видов продукции по отраслям);
4) транспортная задача (оптимальное распределение потоков товарных поставок по транспортной сети);
5) задача о размещении производства (планирование с учетом затрат на производство и транспортировку продукции);
6) задача о назначениях (оптимальное распределение различных видов транспортных средств) и др.
В настоящее время одним из перспективных, но недостаточно распространенных способов численного решения задач линейного программирования является использование надстройки «Поиск решения» электронных таблиц Microsoft Excel.
В частности, «Поиск решения» предоставляет возможность:
- использования планов большой размерности (т.е. с большим количеством варьируемых переменных);
- задания ограничений сложного вида;
- отыскания оптимального из допустимых решений;
- генерирования множества различных решений, сохраняемых в дальнейшем в виде сценариев;
- автоматического создания отчета по решению задачи.
Теоретической основой надстройки «Поиск решения» является симплекс-метод, позволяющий находить оптимальное решение задачи планирования с помощью итерационного процесса перехода к улучшающимся планам.
Цель работы – изучить решение задач линейного программирования на компьютере средствами пакета MS Excel.
Задачи:
- привести алгоритм задачи коммивояжера;
- привести алгоритм задачи о назначениях;
- реализовать алгоритм задачи коммивояжера и задачи о назначениях средствами MS Excel;
- показать решение других задач линейного программирования средствами MS Excel.
1. Алексеева Е. В. Построение математических моделей целочисленного линейного программирования. Примеры и задачи: Учеб. пособие / Новосиб. гос. ун-т. – Новосибирск, 2012. – 131 с.
2. Барышев А.В., Федотова Е.Л. К вопросу использования надстройки Excel «поиск решения» в задачах линейного программирования // Интернет-журнал «НАУКОВЕДЕНИЕ» Том 7, №3 (2015) http://naukovedenie.ru/PDF/54TVN315.pdf (доступ свободный). Загл. с экрана. Яз. рус., англ. DOI: 10.15862/54TVN315
3. Вуколов, Э.А. Основы статистического анализа. Практикум по статистическим методам и исследованию операций с использованием пакетов STATISTICAи EXCEL: учебное пособие. – 2-е изд., испр. и доп. – М.: ФОРУМ, 2008. – 464 с.
4. Попова О.Н. Моделирование сетевых задач средствами MathCadи Excel / О.Н. Попова // Информатика и образование. – 2013. – № 12. – С. 68-78.
5. ТахаХемди А. Введение в исследование операций. – 7-е изд. – М.: Издательский дом «Вильямс», 2014. – 912 с.
