Решение задач линейного программирования средствами электронных таблиц - Дипломная работа

Решение задач линейного программирования средствами электронных таблицВ 1820 году Фурье и затем в 1947 году Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции - симплекс-метод, ставший основным при решении задач линейного программирования. Присутствие в названии предмета термина «программирование» объясняется тем, что первые исследования и первые приложения линейных оптимизационных задач были в сфере экономики, так как в английском языке слово «programming» означает планирование, составление планов или программ. Термин «линейное программирование» был предложен Данцигом в 1949 году для изучения теоретических и алгоритмических задач, связанных с оптимизацией линейных функций при линейных ограничениях. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман - математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя, и Канторович - советский академик, лауреат Нобелевской премии (1975), сформулировавший ряд задач линейного программирования и предложивший в 1939 году метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода. Эгервари рассмотрел математическую постановку и решил задачу линейного программирования, имеющую название «проблема выбора», метод решения получил название «венгерского метода».Научная новизна и практическая значимость исследуемой проблемы - рассмотренные методы обучения позволят повысить эффективность учебного процесса, имеют важное значении при подготовке активных форм практических занятий. В первой главе работы рассмотрены понятия задачи линейного программирования и методы их решения.Линейное программирование - математическая дисциплина, посвященная теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Термин оптимизация (от лат. optimum - наилучшее) понимается как выбор наилучшего (оптимального) варианта из множества возможных. Общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида: Задача, в которой фигурируют ограничения в форме неравенств, называется основной задачей линейного программирования (ОЗЛП) Задача линейного программирования будет иметь канонический вид, если в основной задаче вместо первой системы неравенств имеет место система уравнений с ограничениями в форме равенства: , Основную задачу можно свести к канонической путем введения дополнительных переменных. Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств.В линейном программировании используется графический метод, с помощью которого определяют выпуклые множества (многогранник решений). Если основная задача линейного программирования имеет оптимальный план, то целевая функция принимает значение в одной из вершин многогранника решений (см. рисунок). Решение задачи линейного программирования графическим методом включает следующие этапы: На плоскости X10X2 строят прямые. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед. Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации.Задачи линейного программирования могут изучаться в рамках различных курсов информационного и физико-математического профилей. К таким курсам относится элективный курс «Информационные системы и модели» (авторский коллектив: д-р пед. наук, профессор И. Г. Учебный курс «Информационные системы и модели» предназначен для изучения в старших классах профильной школы. Курс «Информационные системы и модели» является преемственным по отношению к базовому курсу информатики, обеспечивающему требования к ее изучению в основной школе.Курс состоит из двух разделов.Данный раздел учебника углубляет содержательные линии моделирования и информационных технологий в школьной информатике. База данных - ядро любой информационной системы - рассматривается в качестве информационной модели соответствующей предметной области.Овладение основами компьютерного математического моделирования поможет учащимся углубить научное мировоззрение, развить творческие способности, а также выбрать будущую профессию.

Содержание

Введение

1. Задачи линейного программирования и методы их решения

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

1.2 Методы решения задач линейного программирования

1.3 Изучение элементов линейного программирования в профильных и элективных курсах информатики

2. Электронные таблицы и их применение в решении задач

2.1 Краткие сведения об электронных таблицах MS Excel

2.2 Технология решения задач линейного программирования с помощью поиска решений в среде Excel

2.3 Задания к контрольной работе

Заключение

Список литературы