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

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-й столбец (обычно такая ситуация возникает в конце, т.е. в правом нижнем углу таблицы).

И так далее…

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

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

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