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

Автор работы: Пользователь скрыл имя, 30 Апреля 2013 в 01:38, курсовая работа

Краткое описание

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

Содержание

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

Вложенные файлы: 1 файл

Kursovaya_rabota_po_ChM_Shapakov.docx

— 216.11 Кб (Скачать файл)



Задание

  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

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