Линейное программирование

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

ФИЛИАЛ  ГОУ ВПО МОСКОВСКОГО ГОСУДАРСТВЕННОГО ИНДУСТРИАЛЬНОГО УНИВЕРСИТЕТА В г. ВЯЗЬМЕ

СМОЛЕНСКОЙ ОБЛАСТИ (ВФ ГОУ МГИУ)

                              КУРСОВАЯ РАБОТА

Дисциплина: «Информатика»

Тема: Вариант 8

Специальность: 060500 «Бухгалтерский учет, анализ и аудит»

Отделение: заочное

Группа: Вз06Б22п

Студент: Иванова Марина Александровна

Преподаватель:   Соколова Н.В.

          2007 г.

Задание 1

Для производства изделий А, В, С, D предприятие использует несколько видов сырья. Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в таблице. В ней же указаны прибыль от реализации одного изделия каждого вида и общее количество сырья данного вида, которое необходимо предприятию.

Принимаем, что сбыт обеспечен и что изделия А, В, С, D могут производиться в любых соотношениях. Перед менеджером по выпуску товара поставлена задача составить такой план выпуска, при котором прибыль предприятия от реализации всех изделий была бы максимальной.

Для расчётов использовать встроенную программу «Поиск решения».

Задание 2

Для оценки расхода листовой нержавеющей стали, необходимой для раскроя некоторой детали, следует приближенно вычислить площадь, заданную интегралом с помощью метода трапеций. Если отрезок интегрирования разбит на n=2 и n=4 равные части. Оценить погрешность результата и сравнить приближенные значения интеграла с точными:

   ;    (I=e-2≈0,718)

Разработать алгоритм решения данной задачи, представить его в виде блок-схемы и программы на языке программирования Turbo Pascal, с помощью созданной программы найти приближенную площадь. Графическое решение задачи выполнить с применением прикладной программы MS Excel.

Задание 3(общее для всех вариантов)

              Разработка web – страниц (web – узла), содержащих информационные, рекламные или справочные материалы о продукции машиностроения или услугах, связанных с обслуживанием автомобилей (услуги автосервиса).  Рекомендуемым объёмом выполнения настоящего задания, соответствующим положительной оценке, является 3-5 тематических HTML - страниц. Разработка web – узла может преследовать различные цели: рекламу предприятия машиностроения и/ или его продукции (услуг); систематизацию справочных материалов в помощь автолюбителю или лицу, производящему профилактическое обслуживание и /или ремонт машиностроительной продукции (автомобилей); систематизацию и структурирование материалов познавательного и/ или информационного характера о достижениях в области автомобилестроения, самолётостроения и т.д.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ………………………………………………………….               5

ГЛАВА 1. ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И МЕТОДЫ ИХ РЕШЕНИЯ

1.1 Линейное программирование. Общая постановка задачи линейного программирования…………………………………………………………………. 6

1.2  Методы решения задач линейного программирования. Алгоритмы графического метода и симплекс-метода………………………………………… 7

1.3 Выполнение задачи линейного программирования с помощью пакета

прикладных программ «Поиск решения»………………….……………………. 11

ГЛАВА 2. ПРИМЕНЕНИЕ ЧИСЛЕННЫХ МЕТОДОВ ДЛЯ ВЫЧИСЛЕНИЯ ПЛОЩАДЕЙ ФИГУР

2.1                            Численное интегрирование. Квадратурные формулы

прямоугольников, трапеции, параболы (Симпсона)……………………………. 14

2.2                            Язык программирования Turbo Pascal…………………………  20

2.3                            Выполнение задачи по вычислению площади фигуры с помощью численных методов……………………………………………... 21

ГЛАВА 3. СОЗДАНИЕ ГИПЕРТЕКСТОВЫХ ДОКУМЕНТОВ ДЛЯ ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ В ГЛОБАЛЬНОЙ СЕТИ ИНТЕРНЕТ

3.1  Глобальная сеть Интернет. «Всемирная паутина»…………………..  28

3.2 HTML – средство разработки web-страниц и web-узлов……………. 30

3.3 Основные принципы и этапы разработки web-страниц и web-

узлов………………………………………………………………………………..  33

3.4 Разработка web-узла для агентства недвижимости. Структура и алгоритм разработки  web-узла…………………………………………………... 35

ЗАКЛЮЧЕНИЕ…………………………………………………………….. 39

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ………………………...40

                                                     ВВЕДЕНИЕ

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

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

Объектами исследования настоящей курсовой работы являются прикладные программы общего назначения MS Excel, MS Front Page’2000, прикладные программы web – дизайна: Adobe Photoshop 7, MS Photo Editor, численные методы, применяемые для вычисления площадей геометрических фигур, и инструментальные средства программирования: Turbo Pascal, HTML.

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

Информационной базой исследования является учебная литература, техническая документация по языку программирования Turbo Pascal,  программам MS Front Page’2000, MS Excel.

Глава 1. ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И МЕТОДЫ

                                      ИХ РЕШЕНИЯ

             1.1 Линейное программирование. Общая постановка задачи

          линейного программирования

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

Задачи линейного программирования были первыми, подробно изученными задачами поиска экстремума функции при наличии ограничений типа неравенств. В 1820 г. Ж. Фурье и затем в 1947 г. Дж. Дансинг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции -  симплекс-метод, ставший основным при решении задач линейного программирования.

Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман; советский академик, лауреат Нобелевской премии Л. В. Канторович, сформулировавший ряд задач линейного программирования и предложивший в 1939 г. метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода.

Термин «линейное программирование» был предложен Дж. Данцингом в 1949 г. для изучения теоретических и алгоритмических задач, связанных с оптимизацией линейных функций при линейных ограничениях.

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

Для задач линейного программирования характерно: показатель эффективности (целевая функция) выражается линейной зависимостью; ограничения на решения – линейные равенства или неравенства.

Трудности решения задач линейного программирования зависят от: вида зависимости, связывающей целевую функцию с элементами решения; размерности задачи, то есть от количества элементов решения х1, х2,…, xn; вида и количества ограничений на элементы решений.                 

1.2.Методы решения задач линейного программирования. Алгоритмы графического метода и симплекс-метода

Отдельные свойства линейных неравенств рассматривались еще в первой половине 19 века в связи с некоторыми задачами аналитической механики.

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

Реальные задачи линейного программирования содержат очень большое число ограничений и неизвестных и выполняются на ЭВМ. Симплекс-метод -  наиболее общий алгоритм, использующийся для решения таких задач. Суть метода заключается в том, что после некоторого количества специальных симплекс - преобразований задача линейного программирования, приведенная к специальному виду, разрешается.

    Алгоритм симплекс-метода.

Определить число и состав базисных и свободных переменных.

Выразить базисные переменные через свободные переменные.

Выразить целевую функцию через свободные переменные.

Построить начальную симплекс-таблицу.

Проверить решение на оптимальность: если в F-строке (кроме С0) все Сj0, то получено оптимальное решение: X=(B1,...,Bm,0,...,0), F=C0. Если же существует Cj<0, то решение можно улучшить, но предварительно надо проверить факт существования решения.

Проверить существование решения: рассмотрим все столбцы, у которых Сj<0, если существует хотя бы один столбец, у которого все коэффициенты Ai,j<0, то задача решения не имеет, т.к. множество допустимых решений D не ограничено и целевая функция неограниченно возрастает. Если таких столбцов нет, то переходим к следующему этапу.

Выбрать свободную переменную, которую надо ввести в базис (выбор разрешающего столбца): это столбец, с минимальным значением Сj (пусть это k-й столбец)

Выбрать базисную переменную, которую надо вывести из базиса (выбор разрешающей строки): рассмотрим k-й столбец и все его элементы, которые больше нуля, т.е. Ai,k>0; для всех этих элементов находим отношение Bi/Ai,k и выбираем строку, которая соответствует минимальному значению этого отношения (пусть это i-я строка); соответствующая i-я переменная Xi выводится из базиса; при нескольких одинаковых отношениях берем любую строку; элемент Ai,k называется разрешающим элементом.

Пересчитать симплекс-таблицу: составляем новую симплекс-таблицу заменив в составе базисных переменных Xi на Xk; заполняем сначала новую k-ю строку, записывая в нее элементы старой i-ой строки, поделенные на разрешающий элемент; после заполнения k-ой строки заполняем оставшиеся строки; для этого k-ю строку умножаем последовательно на такие числа, чтобы после сложения ее с каждой строкой старой таблицы в k-ом столбце получить везде ноль (кроме единицы в k-ой строке).

После заполнения новой симплекс-таблицы алгоритм возвращается к 5-му пункту.

В конце, когда в F-строке все коэффициенты (кроме С0) будут больше нуля, тогда получаем оптимальное решение, либо когда существует столбец , у которого Cj<<0 и все коэффициенты Ai,j<<0, в этом случае решения на существует.

Если после подготовки задачи линейного программирования к специальному виду для решения симплекс-методом, не в каждой строке системы ограничений есть базисная переменная (входящая в данную строку с коэффициентом 1, а в остальные строки с коэффициентом0), то для решения данной задачи воспользуемся методом искусственного базиса. Суть метода довольно проста: