Курсовая работа по "Численным методам"



Задание

  1. Решить задачу линейного программирования:
    • графическим методом
    • симплекс- методом
    • методом симплекс-таблица

  1. Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально - денежных ресурсов в количестве b1, b2, b3 единиц. При этом для продажи 1 группы товаров на 1тыс.руб. товарооборота расходуется ресурса первого вида в количестве a11 единиц, ресурса второго вида в количестве a21 единиц, ресурса третьего вида в количестве a31 единиц. Для продажи 2 и 3 групп товаров на 1 тыс.руб. товарооборота расходуется соответственно ресурса первого вида в количестве a12, a13 единиц, ресурса второго вида в количестве a22, a23 единиц, ресурса третьего вида в количестве a32, a33 единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно с1, с2, с3 (тыс. руб.). Определить плановый объём и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

 

 

 

 

a11 =9      а12 = 9     a13= 3

a21 = 3     a22 = 6     a23 = 9

a31 = 7     a32 = 4     a33 = 12

b1 = 801  b2 = 453  b3 = 280

с1 = 3       с2 = 4      с3 = 3

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

 

Содержание

  1. Введение………………………………………………………….…………4

Теоретическая часть…………………………………………………………6

    1. Понятия линейного программирования……………………………6
    2. Общая задача линейного программирования……………..….……6
    3. Симплекс-метод……………………………………………..………7
    4. Алгоритм Симплекс-метода: ………………………………………8
    5. Метод искусственного базиса: ………………………………….…8
    6. Двойственный симплекс-метод………………………………….…9
  1. Практическая часть………………………………………………………12
    1. Решение задачи линейного программирования…………………12
      • графический метод……………………………………………………….12
      • метод симплекс-таблица…………………………………………………26
    2. Решение задачи на определение планового объёма и структуры товарооборота……………………………………………………………………36
    3. Решение двойственной задачи линейного программирования…39
  • составление двойственной задачи линейного программирования……39
  • установка сопряженных пар переменных прямой и двойственной задач……………………………………………………………………………...39
  • решение двойственной задачи…………………………………..….……39
  1. Заключение………………………………………………………..………44
  1. Использованная литература……………………………………...………45

 

  1. Введение.

Термин линейное программирование появился в Америке в середине 40-х годов (первая американская работа по частной задаче линейного программирования опубликована в 1941 г.). В Советском  Союзе исследования в этой области  начались ранее. В конце 30-х годов  целый ряд существенных результатов  по линейному программированию был  установлен Л.В. Канторовичем.

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

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

Линейное программирование (ЛП) –  один из первых и наиболее подробно изученных разделов математического  программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина "математическое программирование". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина "линейное программирование" возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин "линейное программирование" возник в результате неточного перевода английского "linearprogramming". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом английского "linearprogramming" было бы не "линейное программирование", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термины линейное программирование, нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

Итак, линейное программирование возникло после второй мировой войны и  стало быстро развиваться, привлекая  внимание математиков, экономистов  и инженеров благодаря возможности  широкого практического применения, а также математической стройности.

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

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

Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или  максимума) линейной функции при  линейных ограничениях.

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

 

ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ

1. Задача линейного программирования

Понятия ЛП: Линейное программирование решает задачи, которые относятся к такой сфере человеческой деятельности как сельское хозяйство, военное дело, промышленное производство, транспорт и здравоохранение.

Линейное программирование - это  наука о методах, исследование и  отыскивания min (max) линейной функции, на переменные которой наложены линейные ограничения.

Линейность - это свойство математических выражений и функций  

выражение ax+by является линейным относительно переменных x и y.

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

(1.1) при условиях

, где  (1.2)

 (i=k+1, m)   (1.3)

    (1.4)

     Функция (1) называется  целевой функцией задачи (1.2)-(1.4) условия(1.2)-(1.4) ограничениями данной задачи.

     Стандартной задачей  линейного программирования называется, задача которая состоит в определении максимума значения  функции (1) при выполнении условий (1.2)-(1.4), где k=m и t=n.

     Канонической задачей  линейного программирования называется  задача, которая состоит в определении  максимума значения функции (1) при выполнении условий (1.3)-(1.4), где k=0 и t=n.

     Совокупность чисел  x=x1,x2,…xn, удовлетворяющих ограничениям задачи (1.2)-(1.4) называется планом.

Общая задача линейного  программирования

Постановка задачи: Найти наибольшее (наименьшее) значение показателей  эффективности целевой функции

Z=c1x1 + c2x2 + … + cnxn -> max (min)

При системе линейных ограничений:

 

n – количество переменных

m – количество ограничений

Необходимо найти значение x1, x2, …, xn, неотрицательные, соответствующие системе ограничений (2), в которой функция Z принимает max (min) значение.

Этапы решения задачи ЛП графическим  методом:

1.Систему ограничений представить  в виде системы равенств;

2.Получить многоугольник допустимых  решений;

3.Начерить прямую целевой функции;

4.Построить перпендикуляр к  прямой целевой функции, которая  проходит через т. (0;0)

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

2.Симплекс – метод

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

Идея симплексного метода состоит  в том, что поставленная описательная задача переводится в математическую форму. Математическая формулировка задачи содержит уравнение целевой функции с указанием желаемого результата — определение минимума или максимума целевой функции; системы линейных ограничений, заданных равенствами или неравенствами. Полученное математическое описание приводят к матричному виду. Затем матричное описание задачи приводят к канонической форме. После того как система линейных уравнений приведена к канонической форме, приступают к решению задачи линейного программирования. Алгоритм решения этой задачи состоит из последовательности построения матриц. Каждый шаг решения приближает к получению желаемого результата

а)Алгоритм Симплекс-метода:

1.Заменяя систему неравенств на систему уравнений, добавляем дополнительные переменные;

2.Выражаем дополнительные переменные  через остальные;

3.Находим первое опорное решение  при независимых переменных;

4.Если при решении задачи  в записи целевой функции есть  отрицательные (положительные) коэффициенты, то:

а).Рассматриваем элементы из записи целевой функции с наибольшим по модулю ‘’-‘’ коэффициентом (при решении на min рассматривается наибольший ‘’+’’ коэффициент).

Переменные с наибольшим коэффициентом  выражаем через остальные;

б).Находим min соответствие свободных элементов к коэффициенту выбранной переменной;

в).Подставляем полученное выражение в другие уравнения и целевую функцию;

г).Находим опорное решение при всех независимых переменных, равных нулю;

5.Смотрим пункт 4).

 

6.Получаем оптимальный план.

  б)Метод искусственного базиса:

Если в системе ограничений  в неравенствах содержится знак = или >=0, то для построения первого опорного плана вводят искусственные базисные переменные.

 

Z=x1 + 1,1x2 + 7,5x3 -> min

Решение:

 

Для получения решения в каждое уравнение добавляют неотрицательные  искусственные переменные (0)

 

Для искусственных переменных коэффициент  целевой функции M.

Если решается задача на min M – очень большое ‘’+’’ число, если на max – очень маленькое ‘’-‘’

Продолжить решение системы  по алгоритму симплекс– метода.

 в) Двойственный симплекс-метод.

Рассмотрим алгоритм двойственного  симплекс-метода.

Запишем условия задачи:


 

Введём новую функцию 

  1. Приведём условия задачи  к каноническому виду:

 

 

 

  1. Запишем симплекс таблицу, соответствующую задаче.

№

Б

u0

u1

u2

v1

v2

v3

v4

1

u1

c1

1

0

a11

a21

a31

a41

2

u2

c2

0

1

a12

a22

a32

a42

3

-z

  

0

0

-b1

-b2

-b3

-b4


 

  1. Все коэффициенты в строке целевой функции – неположительные  ,  следовательно выполнены условия оптимальности решения
  2. В столбце свободных членов есть отрицательный элемент , следовательно, выделенное базисное решение не является допустимым (так как все неизвестные должны быть неотрицательными). Строку с отрицательным свободным членом назовём «разрешающей».
  3. Находим в разрешающей строке отрицательные элементы. Если таковых нет, задача решения не имеет.
  4. В разрешающей строке есть отрицательные элементы . Составляем соотношения коэффициентов целевой функции (они не положительные) к отрицательным элементам разрешающей строки и находим среди этих отношений наименьшее:

.

Столбец коэффициентов в ограничениях задачи с наименьшим отношением назовём  «разрешающим».

  1. На пересечении разрешающей строки и разрешающего столбца находится отрицательный разрешающий элемент (в таблице условно выделен элемент –a31). Производим преобразование Гаусса-Жордана с найденным разрешающим элементом.
  2. В результате этого преобразования коэффициенты при неизвестных в строке целевой функции останутся неположительными, а число отрицательных элементов в столбце свободных членов уменьшится.
  3. Через конечное число шагов или будет получено оптимальное решение, или же будет установлено, что допустимых (неотрицательных) решений нет.

Существует целый класс задач (типа задачи о диете), условия которых  естественным образом формулируются  сразу во 2-й стандартной форме. Для решения таких задач двойственный симплекс метод более удобен, чем  обычный алгоритм.

 

 

  1. Практическая часть.

 

    1. Решение задачи линейного программирования.
      • Графический метод.

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

      

x1

0

2

x2

3

1


     

x1

2

3

x2

4

6


x1

4

4

x2

0

3


x1

0

7

x2

5

5


     - ось Ох2

- ось Ох1

 

Рассмотрим целевую функцию  задачи Z = 2x1+x2 → max.

Построим прямую, отвечающую значению функции Z = 0: Z = 2x1+x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области.

Так как точка D получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим: x1 = 2.75, x2 = 2.25

Откуда найдем максимальное значение целевой функции:

Zmax = 2·2.75 + 1·2.25 = 7.75

Рассмотрим целевую функцию  задачи Z = 2x1+x2 → min.

Построим прямую, отвечающую значению функции Z = 0: Z = 2x1+x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области.

Так как точка A получена в результате пересечения прямых (1) и (4), то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим: x1 = 0.4286, x2 = 0.8571

Откуда найдем минимальное значение целевой функции:

Zmin = 2·0.4286 + 1·0.8571 = 1.71

Ответ: Zmax = 7.75; Zmin = 1.71

 

  • метод симплекс-таблица.

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≥) вводим базисную переменную x3 со знаком минус. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5. В 4-м неравенстве смысла (≥) вводим базисную переменную x6 со знаком минус.

Введем искусственные  переменные x: в 1-м равенстве вводим переменную y1;  в 4-м равенстве вводим переменную y2;

Из уравнений выражаем искусственные переменные y1,y2:

y1== 3-x1-3x2+x3

y2=0-2x1+x2+x6

Составим новую линейную функцию h=-(y1+y2) .

h=-(3-x1-3x2+x3+0-2x2+x6)=-(3-3x1-2x2+x3+x6)=-3-(-3x1-2x2+x3+x6)

h=-3-(-3x1-2x2+x3+x6)

Для постановки задачи на максимум целевую функцию запишем так:

Z=0-(-2x1-x2) => max

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

Решим систему уравнений  относительно базисных переменных:

y1, x4, x5, y2,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,6,5,0,3,0)

 

 

 

 

Базис 

Свободные

член

Переменные

Оценочные

отношения

x1

x2

x3

x4

x5

x6

y1

y2

y1

3

1

3

-1

0

0

0

1

0

3

x4

6

3

-1

0

1

0

0

0

0

2

x5

5

1

1

0

0

1

0

0

0

5

y2

0

2

-1

0

0

0

-1

0

1

0

z

0

-2

-1

0

0

0

0

0

0

  

h

-3

-3

-2

1

0

0

1

0

0

  



 

 

 

 

 

 

 

Базисное решение называется допустимым, если оно неотрицательно.

Переходим к основному  алгоритму симплекс-метода.

Итерация №1.

1. Проверка критерия  оптимальности.

Текущий опорный план не оптимален, так как в индексной  строке находятся отрицательные  коэффициенты.

2. Определение  новой базисной переменной.

В индексной строке h выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент.

3. Определение  новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai2

и из них выберем наименьшее:

max=[3, 2,5,0]=0

Следовательно, 4-ая строка является ведущей.

Разрешающий элемент равен (2) и находится на пересечении  ведущего столбца и ведущей строки.

 

 

 

 

 

 

Базис 

Свободные

член

Переменные

Оценочные

отношения

x1

x2

x3

x4

x5

x6

y1

y2

y1

3

1

3

-1

0

0

0

1

0

3

x4

6

3

-1

0

1

0

0

0

0

2

x5

5

1

1

0

0

1

0

0

0

5

y2

0

2

-1

0

0

0

-1

0

1

0

z

0

-2

-1

0

0

0

0

0

0

  

h

-3

-3

-2

1

0

0

1

0

0

  



 

 

 

 

 

 

4. Пересчет симплекс-таблицы.

Формируем следующую часть  симплексной таблицы.

Вместо переменной y2 в план 1 войдет переменная x1

Строка, соответствующая  переменной x1 в плане 1, получена в результате деления всех элементов строки y2 плана 1 на разрешающий элемент =0

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x2 плана 1 записываем нули.

Таким образом, в новом  плане 1 заполнены строка x1 и столбец x1 .

После преобразований получаем новую таблицу:

Базис 

Свободные

член

Переменные

Оценочные

отношения

x1

x2

x3

x4

x5

x6

y1

y2

y1

3

0

3,5

-1

0

0

0,5

1

-0,5

  

x4

6

0

0,5

0

1

0

1,5

0

-1,5

  

x5

5

0

1,5

0

0

1

0,5

0

-0,5

  

x1

0

1

-0,5

0

0

0

-0,5

0

0,5

  

z

0

0

-2

0

0

0

-1

0

1

  

h

-3

0

-3,5

1

0

0

-0,5

0

1,5

  

Курсовая работа по Численным методам 📙 Курсовая → 🆔 114497

Курсовая работа по Численным методам 📙 Курсовая → 🆔 114497

Курсовая работа по "Численным методам"