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

14

спкмп

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

по предмету

Математические методы

Тема: «Линейное программирование»

Вариант № 18

Выполнил студент группы

Проверил преподаватель:

Саватеева О.Н.

Оценка___________

Подпись___________

Санкт–Петербург

2006

Содержание

1.              Симплекс-метод

1.1Составление математической модели

1.2Решение

1.3Реализация на ПК

2.              Графический метод решения задачи «Л.П.»

3.              Транспортная задача

3.1              Постановка задачи

3.2Нахождение начального плана транспортной задачи методом С-З угла

3.3Оптимизация

3.4Реализация на ПК

4.              Заключение

1.            Симплекс-метод

1.1.     Составление математической модели

На предприятии в процессе производства используются три технологических способа. При этом расходуются сырье, трудовые ресурсы и учитываются накладные расходы. Известны удельные затраты каждого ресурса , запасы ресурсов , (а также удельная прибыль ) и удельное потребление воды   при использовании каждого технологического способа

Решение:

При решении этой задачи возникают следующие этапы:

1)     Идентификация переменных

-первый технологический способ

-второй технологический способ

-третий технологический способ

2)     Определение целевой функции

3)     Определение ограничений задачи

Математическая модель:

1.2       Решение

              Предварительно задачу нужно привести к, так называемой , стандартной форме:

1)     Все ограничения задачи должны быть записаны в виде равенств с не отрицательной правой частью

                            =>                           

2)     Все переменные задачи должны быть не отрицательными

, где             

3)     Целевая функция либо минимизируется либо максимизируется (в нашем случае функция минимизируется)

              Ограничения представляющие собой неравенства по смыслу «<=» превращаются в равенство путём добавления в левую часть ограничения, так называемой остаточной переменной

              Ограничения в виде неравенств по смыслу «<=» превращаются в равенство путём вычитания из левой части, так называемой избыточной переменной 

              Если ограничения записаны с отрицательной правой частью, то путём умножения на (-1) приводим к положительной правой части

              Если какая-либо переменная – не ограничена в знаке ( «>» или «<» ), то её можно представить в виде разности двух неотрицательных элементов

,              где              , а             

              Если же ограничения являются неравенствами по смыслу «>=» или «=», то в этом случае прибегают к двухэтапному симплекс-методу

              Приведём задачу к стандартной форме.

              Все новые переменные записываются в целевую функцию с коэффициентом 0

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

              В задаче имеется только одна базисная переменная , поэтому необходимо в 2-е и 3-е ограничения ввести дополнительные искусственные базисные переменные и

              I этап

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

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

              Если задача максимизации, то в строке целевой функции выбираем  максимальный по модулю отрицательный коэффициент, в случае минимизации: максимальный положительный. Это будет соответствовать ведущему столбцу.

              Составляется отношение элементов столбца к соответствующим элементам ведущего столбца, кроме нулевых и отрицательных элементов.

              Вычисление симплекс-метода сводится в таблицу

              Из получившихся отношений выбирают min  величину. Это будет соответствовать ведущей строке.

              На пересечении ведущего столбца и ведущей строки стоит ведущий элемент.

              Ведущая строка соответствует переменной, которая выйдет из базиса, а ведущий столбец - переменной, которая войдёт в базис.

              Далее производится пересчет всей таблицы:

1)     Сначала пересчитывается новая ведущая строка, т.е. та, которая вошла в базис ()

2)     Все остальные строки пересчитываются одинаково:

3)     Целевая функция может быть пересчитана методом коэффициентов

              В результате решения I этапа , значит имеет эквивалентную ей, условие которой выписываем из последней таблицы за исключением и .

              II этап

              Замечание:

              Если в последней таблице, при найденном оптимальном решении, какая-либо из основных переменных не вошла в базис, то ее значение равно 0

              Ответ: ; ; , т.е.

1.3.     Реализация на ПК

              Для реализации задачи на ПК была использована программа Microsoft Excel

              Далее представлены формулы, используемые при реализации задачи:

              Ввод данных:

              I этап:

              II этап:

2.      Графический метод решения задачи «Л.П.»

              Линейный характер модели состоит в том, что и целевая функция и ограничения носят линейный характер.

              В общем виде любая задача линейного программирования сводится к следующей модели:

              Целевая функция -

              Ограничения , где

,              ,             

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

              В задаче может быть единственное решение, а может быть бесчисленное множество решений. Множество решений задачи состоит в Области Допустимых Решений (ОДР), на которой мы ищем оптимальное решение, т.е. или

              Если число переменных в задаче , то возможно ее графическое решение на плоскости, а именно в координатной системе

При графическом решении задачи в ЛП отмечают следующие этапы:

1)     Строят координатную плоскость

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

a)     Сначала строят границу полуплоскости в виде прямой

b)     С помощью контрольной точки выбирают нужную полуплоскость

              Таким образом строят все ограничения.

2)     Выбирают общую для всех ограничений область, которая и будет являться ОДР задачи.

              В данной задаче четырёхугольник ABCD. Каждая точка этой области является допустимым решением задачи.

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

              Нашли направление роста f. Двигая в этом направлении прямую f параллельно самой себе, доходим до крайней точки на ОДР.

              В точке А функция f достигает своего max: в точке

              Найдем координаты этой точки. Точка А образована пересечением ограничений II и IV : точка A IIIV

              Решим совместно систему:

              Подставим в координаты точки A выражение целевой функции, получаем ее значение max

              Ответ:

3.      Транспортная задача

3.1              Постановка задачи

              Пусть имеется m-поставщиков однородного груза с наличием груза у них , а также имеется n-потребителей с потребностью в нём соответственно . Стоимость перевозки единицы груза от i-го поставщика к j-му потребителю

              Требуется составить такой план перевозок, общая стоимость которого минимальна

, где             

-количество груза, перевозимого от i-го поставщика к j-му потребителю

              Транспортная задача часто задается в виде таблицы;

, где

              A1,A2,A3-поставщики

              B1,B2,B3,B4-потребители

              Перед решением задачи проверяется, является ли она сбалансированной, т. е.

Если , то задача сбалансированная

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

Если , то фиктивный поставщик с наличием груза при этом в таблицу добавляется новая строка

              Стоимости перевозок от фиктивного поставщика или к фиктивному потребителю всегда равны нулю (=0).

3.2        Нахождение начального плана транспортной задачи методом С-З угла

              После того как задача сбалансирована, т.е. приступают к нахождению начального плана. Существует два способа. Мы рассмотрим только один (метод северо-западного угла).

              Начинают с верхней левой клетки

a)     Если , то , 1-я строка выходит из рассмотрения

b)     Если , то , I-й столбец выйдет из рассмотрения

c)     Если , то , выходят из рассмотрения и 1-я строка и I-й столбец (обычно такая ситуация возникает в конце, т.е. в правом нижнем углу таблицы).

И так далее…

              Затем план проверяется на вырожденность.

              В не вырожденном плане число заполненных клеток должно быть

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

              Стоимость высчитывается по формуле:

3.3        Оптимизация

              После того как начальный план транспортной задачи определён, производится его проверка на оптимальность, для этого:

1)     Определяют потенциалы каждого поставщика и каждого потребителя. Для этого каждой заполненной клетке составляют уравнение

              ,              для

              Так как заполненных клеток , а неизвестных , то назначают сами, обычно . Из полученной системы определяют потенциалы

2)     Для каждой незаполненной клетки находят, так называемые «косвенные тарифы» , которые определяются также . Они записываются в левый нижний угол клетки.

3)     Производится проверка плана на оптимальность по условию (или ), т.е. если косвенные тарифы не превосходят натуральные, то план оптимальный.

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

a)     Помечаем клетку с наибольшей положительной разностью (если одинаковые - берем любую) и считаем эту клетку заполненной

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

c)     Расставляются знаки поочередно «+» и «-» в вершинах цикла в любом направлении, начиная с помеченной клетки «+»

d)     В клетках помеченных знаком «-» выбирается минимальное число

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

              Если все выполняется правильно, то целевая функция должна монотонно убывать

              И так далее до тех пор пока в каждой клетке не будет выполняться условие

I и II итерации

              III и IV итерации

V и VI итерации

3.4  Реализация на ПК

              Для реализации задачи на ПК была использована программа Microsoft Excel

4.      Заключение

В результате проделанной работы была изучена система линейного программирования и освоены следующие методы решения задач линейного программирования:

      Аналитический

      Симплекс-метод

      Графический

      Решение транспортной задачи методом потенциалов

В работе использовались следующие прикладные пакеты:

      Microsoft Excel

      Microsoft Word

      Пакет экономических расчётов Per

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