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

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

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

Графический метод решения задачи линейного программирования заключается в построении множества допустимых решений, и нахождении в данном множестве точки, соответствующей 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)

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