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

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

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

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

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

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

Тема: Вариант 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), то для решения данной задачи воспользуемся методом искусственного базиса. Суть метода довольно проста:

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

Новая задача решается симплекс-методом, причем все искусственные базисные переменные должны стать свободными (выйти из базиса) и их сумма должна равняться нулю, в обратной случае в данной системе невозможно выделить допустимый базис.

Графический метод решения задачи линейного программирования заключается в построении множества допустимых решений, и нахождении в данном множестве точки, соответствующей max/min целевой функции.

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

Алгоритм графического метода.

Строится область допустимых решений системы ограничений. Для этого на плоскости решается графически система ограничений.

При этом возможны случаи:

область допустимых решений - пустое множество;

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

область допустимых решений - выпуклый многоугольник;

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

В первом случае ЗЛП не имеет оптимального решения из-за несовместности системы ограничений.

Во втором случае - это единственное решение и будет оптимальным решением.

Строится вектор-градиент целевой функции, выходящий из начала координат.

Строится линяя уровня целевой функции, перпендикулярная вектору-градиенту и проходящая через область.

Линия уровня смещается параллельно в направлении вектора-градиента (в противоположном направлении) в задаче максимизации (минимизации) до выхода из области. Точки, в которых произошел выход из области, являются точками экстремума.

Если экстремум достигается в двух угловых точках, то, по теореме об альтернативном оптимуме, оптимальным решением будет любая точка отрезка, соединяющего эти точки:

                                         , .         (1.1)

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

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

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

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

Введем следующие обозначения:

пусть X1 – количество произведенного товара изделия A,

           X2 – количество произведенного товара изделия B,

           X3 – количество произведенного товара изделия C,

           X4 – количество произведенного товара изделия D.

Составим математическую модель:

    ЦФ:       

   ОГР.:     

Создадим форму для ввода условий задачи и введем исходные данные

Рис. 1.1. Экранная форма исходных данных

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

Чтобы сделать это надо выполнить следующие действия:

- курсор в F6 ;  курсор на кнопку fx (мастер функций); в появившемся

окне выбрать «Математические» и «СУММПРОИЗВ».

В окне мастера функций нажать Далее>, в появившемся окне в

поле “массив 1” ввести (протаскивая курсор мыши по ячейкам) адреса изменяемых ячеек B3:E3. В поле “массив 2” вводятся адреса ячеек содержащих прибыль от реализации изделий B6:E6, после нажать Готово.

           Функции в ячейки F9 – F14 вводятся аналогично.

           В меню «Сервис» выбираем процедуру «Поиск решения». В появившемся окне нужно установить адрес целевой ячейки F6, значение целевой ячейки: максимальное, адреса изменяемых ячеек B3:Е3. Чтобы ввести ограничения задачи, нажать кнопку «Добавить». В появившемся диалоговом окне слева ввести адрес В9: Е9 (израсходованное количество сырья 1), затем выбрать знак <= и в правой части количество сырья на складе, H9. После ввода нажать кнопку «Добавить» и аналогично ввести ограничения остальных видов сырья. Снова нажать кнопку «Добавить» и ввести ограничение: B3:Е3 >= B4:Е4 (соответствующее ограничению X1, X2, X3, X4 >= 0). После ввода последнего ограничения нажать ОК.

Настройка параметров решения задачи.

В окне «Поиск решения» нажать «Параметры» в появившемся окне установить флажок в пункте «Линейная модель». В этом случае при решении задачи будет использоваться симплекс - метод. Остальные значения можно оставить без изменения. После нажать кнопку ОК.

Для решения задачи в окне «Поиск решения» нажать кнопку «Выполнить».

           Для просмотра результатов выбираем тип отчета: «Результаты» и нажимаем кнопку ОК.

             Рис.1.2.    Экранная форма полученных результатов.

То есть для получения оптимальной прибыли предприятию необходимо выпускать «изделие А» в размере  13,22034, а «изделие D» в размере 56,44068.

Тогда прибыль предприятия составит 2720,339.

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

                     ВЫЧИСЛЕНИЯ ПЛОЩАДЕЙ ФИГУР

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

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

Численное интегрирование — вычисление значения определённого интеграла (как правило, приближенное), основанное на том, что величина интеграла численно равна площади криволинейной трапеции, ограниченной осью абсцисс, графиком интегрируемой функции и отрезками прямых и , где и — пределы интегрирования.

К простейшим методам относятся методы прямоугольников, в которых подынтегральную функцию на отрезке интегрирования заменяют полиномом нулевой степени, т.е. константой: . Подставляя в формулу (4.12) и выполняя интегрирование, получаем

.                               (2.1)

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

К формуле (2.1) можно также придти, если заменить определенный интеграл интегральной суммой, непосредственно опираясь на определение понятия определенного интеграла.

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

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

,                            (2.2)

.                                  (2.3)

В формулах (2.2) и (2.3) введены обозначения , , которыми мы будем пользоваться и в дальнейшем.

В случае постоянного шага интегрирования формулы (2.2) и (2.3) приобретают вид:

,                            (2.4)

.                    (2.5)

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

,     .                (2.6)

В случае  постоянного шага интегрирования, когда ,  формула средних прямоугольников (2.6) будет иметь следующий вид:

                                                      ,    (2.7)

где    .

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

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

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

(2.8)

Поставляя это выражение в формулу (2.3) и выполняя интегрирование по частичным отрезкам приходим к формуле трапеций:

                   (2.9)

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

В случае постоянного шага интегрирования формула трапеций принимает вид:

.  (2.10)

Для удобства вычислений и оптимизации вычислительных погрешностей формулу (2.10) часто записывают следующим образом:

.                                             (2.11)

Несмотря на то, что в методе трапеций используется более высокий порядок интерполяции подынтегральной функции (кусочно-линейная интерполяция), по сравнению с методом прямоугольников, который использует интерполяцию нулевого порядка (кусочно-постоянная), точность метода трапеций оказывается ниже точности метода средних прямоугольников. Более высокая точность метода средних прямоугольников объясняется “удачным” выбором узловых точек, в которых вычисляется высота элементарного прямоугольника.

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

(2.12)

Интегрируя это выражение на отрезке получим :

.                                                                            (2.13)

Приближенное значение интеграла на интервале получим суммированием частичных интегралов (2.13) по всем отрезкам :

.     (2.14)

Полученное соотношение называется формулой Симпсона или формулой парабол.

Если подынтегральную функцию интерполировать полиномом второй степени на отрезке с привлечением дополнительной точки – середины отрезка, то в этом случае число отрезков разбиения n может быть произвольным (не обязательно четным), а формула Симпсона в этом случае будет иметь вид:

.     (2.15)

Напомним, что , .

Формула (2.14) пригодна для вычисления интегралов от функций, заданных как аналитическим выражением, так и таблично, тогда как формула (2.15) применима только в тех случаях, когда подынтегральная функция задана аналитически.

Формулы, используемые для приближенного вычисления интеграла, называются квадратурными формулами. Нетрудно заметить, что все полученные нами формулы имеют следующую структуру:

,           (2.16)

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

Погрешности приведенных выше методов вычисляются по следующим формулам:

методы левых и правый прямоугольников –     (2.17)

методы средних прямоугольников –                 (2.18)

метод трапеций –                                                  (2.19)

метод Симпсона –                                             (2.20)

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