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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


курсовая работа Решение задач линейного программирования табличным симплекс-методом

Информация:

Тип работы: курсовая работа. Добавлен: 25.04.2012. Сдан: 2011. Страниц: 5. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Рязанский Колледж Электроники 
 
 
 
 
 

Курсовой  проект по дисциплине
«Математические методы»
Тема:
«Решение задач линейного программирования табличным симплекс-методом» 
 
 
 
 
 
 
 
 

Выполнил Проверил
студент группы 11ПВТ-305 преподаватель
Удалов Виталий  Игоревич Евстифеева Г.В. 
 

Оценка ______ 

Рязань 2006 год
Введение.
Многие  задачи, с которыми приходится иметь  дело в повседневной практике, являются многовариантными. Среди множества возможных вариантов в условиях рыночных отношений приходится отыскивать наилучшие в некотором смысле при ограничениях, налагаемых на природные, экономические и технологические возможности. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику. Такие методы объединяются под общим названием — математическое программирование.
Математическое  программирование — область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т. е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.
Функцию, экстремальное значение которой  нужно найти в условиях экономических  возможностей, называют целевой, показателем эффективности или критерием оптимальности. Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель. Математическая модель задачи — это отражение оригинала в виде функций, уравнений, неравенств, цифр и т. д. Модель задачи математического программирования включает:
    совокупность неизвестных величин, действуя на которые, систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, управлением, стратегией, поведением и др.);
    целевую функцию (функцию цели, показатель эффективности, критерий оптимальности, функционал задачи и др.). Целевая функция позволяет выбирать наилучший вариант -из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение. Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности, число комплектов, отходы и т. д.;
Эти условия  следуют из ограниченности ресурсов, которыми располагает общество в любой момент времени, из необходимости удовлетворения насущных потребностей, из условий производственных и технологических процессов. Ограниченными являются не только материальные, финансовые и трудовые ресурсы. Таковыми могут быть возможности технического, технологического и вообще научного потенциала. Нередко потребности превышают возможности их удовлетворения. Математически ограничения выражаются в виде уравнений и неравенств. Их совокупность образует область допустимых решений (область экономических возможностей). План, удовлетворяющий системе ограничений задачи, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным. Оптимальное решение, вообще говоря, не обязательно единственно, возможны случаи, когда оно не существует, имеется конечное или бесчисленное множество оптимальных решений.
Один  из разделов математического программирования - линейным программированием.   Методы и модели линейного программирования широко применяются при оптимизации процессов во всех отраслях народного хозяйства: при разработке производственной программы предприятия, распределении ее по исполнителям, при размещении заказов между исполнителями и по временным интервалам, при определении наилучшего ассортимента выпускаемой продукции, в задачах перспективного, текущего и оперативного планирования и управления; при планировании грузопотоков, определении плана товарооборота и его распределении; в задачах развития и размещения производительных сил, баз и складов систем обращения материальных ресурсов и т. д. Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий, составление смесей, раскрой материалов), производственно-транспортных и других задач.
     Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л. В. Канторовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в экономике.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Примеры экономических задач
1.Задача  о наилучшем использовании  ресурсов.
 Пусть  некоторая производственная единица  (цех, завод, объединение и т. д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции (товаров), известных под номерами, обозначаемыми индексом j . Ее  будем обозначать . Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т. д.). Все эти виды ограничивающих факторов называют ингредиентами . Пусть их число равно m; припишем им индекс i  . Они ограничены, и их количества равны соответственно условных единиц. Таким образом, - вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т. д. Примем в качестве такой меры, например, цену реализации
, т. е.  вектор цен. Известны также технологические коэффициенты , которые указывают, сколько единиц i–го ресурса требуется для производства единицы продукции j-го вида. Матрицу коэффициентов называют технологической и обозначают буквой А. Имеем . Обозначим через план производства, показывающий, какие виды товаров нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах.
Так как  - цена реализации единицы j'-й продукции, цена реализованных единиц будет равна , а общий объем реализации
Это выражение  — целевая функция, которую нужно  максимизировать.
Так как  - расход i-го ресурса на производство единиц j-й продукции, то, просуммировав расход i-го ресурса на выпуск всех n видов продукции, получим общий расход этого ресурса, который не должен превосходить единиц:

Чтобы искомый план был реализован, наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объёмы  выпуска продукции:
  .
Таким образом, модель задачи о наилучшем  использовании ресурсов примет вид:
                 (1)
при ограничениях:
       (2)
                        (3)
Так как  переменные входят в функцию и систему ограничений только в первой степени, а показатели являются постоянными в планируемый период, то (1)-(3) – задача линейного программирования. 

2. Задача о смесях.
В различных  отраслях народного хозяйства возникает проблема составления таких рабочих смесей на основе исходных материалов, которые обеспечивали бы получение конечного продукта, обладающего определенными свойствами. К этой группе задач относятся задачи о выборе диеты, составлении кормового рациона в животноводстве, шихт в металлургии, горючих и смазочных смесей в нефтеперерабатывающей промышленности, смесей для получения бетона в строительстве и т. д.  Высокий уровень затрат на исходные сырьевые материалы и необходимость повышения эффективности производства выдвигает на первый план следующую задачу: получить продукцию с заданными свойствами при наименьших затратах на исходные сырьевые материалы.
3. Задача о раскрое  материалов.
Сущность  задачи об оптимальном раскрое состоит  в разработке таких технологически допустимых планов раскроя, при которых получается необходимый комплект заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму. Рассмотрим простейшую модель раскроя по одному измерению. Более сложные постановки ведут к задачам целочисленного программирования.
4. Транспортная задача.
Рассмотрим  простейший вариант модели транспортной задачи, когда речь идет о рациональной перевозке некоторого однородного продукта от производителей к потребителям; при этом имеется баланс между суммарным спросом потребителей и возможностями поставщиков по их удовлетворению. Причем потребителям безразлично, из каких пунктов производства будет поступать продукция, лишь бы их заявки были полностью удовлетворены. Так как от схемы прикрепления потребителей к поставщикам существенно зависит объем транспортной работы, возникает задача о наиболее рациональном прикреплении, правильном направлении перевозок грузов, при котором потребности полностью удовлетворяются, вся продукция от поставщиков вывозится, а затраты на транспортировку минимальны.
5. Задача о размещении  заказа.
Речь идет о  задаче распределения заказа (загрузки взаимозаменяемых групп оборудования) между предприятиями (цехами, станками, исполнителями) с различными производственными и технологическими характеристиками, но взаимозаменяемыми в смысле выполнения заказа. Требуется составить план размещения заказа (загрузки оборудования), при котором с имеющимися производственными возможностями заказ был бы выполнен, а показатель эффективности достигал экстремального значения. 

                                                
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Симплексный метод 

  В 1949 году американский математик Дж. Данциг разработал эффективный метод решения данного класса задач — симплекс-метод. Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит в следующем:
1)   умение находить начальный опорный план;
2)   наличие признака оптимальности опорного плана;
3)   умение переходить к нехудшему опорному плану.
    Симплексный метод задач линейного программирования основан на переходе от одного опорного плана к другому, при котором  значение целевой функции возрастает (при условии, что данная задача имеет  оптимальный план, и каждый ее опорный  план является невырожденным). Указанный переход возможен, если известен какой-нибудь исходный опорный план. Рассмотрим задачу, для которой этот план можно непосредственно записать.
    Пусть дана функция, для которой необходимо найти наибольшее или наименьшее значение, если значения всех неизвестных неотрицательные. 

    ? = C0 + C1x1 + C2x2 +...+ Cnxn 

    и система m линейных уравнений с n неизвестными. Это называется системой ограничений: 

              a11x1 + a12x2 +...+ a1nxn = b1
               a21x1 + a12x2 +...+ a2nxn = b2
      ...
      am1x1 +am2x12 +...+ amnxn = bm 
 

    Целевую функцию представим в виде: 

    ? - C1x1-C2x2 -...-Cnxn = C0 

    Составим  симплекс-таблицу.В дальнейшем будем  считать, что ранг матрицы системы  ограничений равен r.В системе ограничений выбран базис(основные неизвестные)x1,x2,...xn и коэффициенты в правой части не отрицательны.
    В этом случае система ограничений  будет иметь вид: 

               x1 +...+ a1,r+1xr+1 +...+ a1nxn = b1
                       x2 + a2,r+1xr+1 +...+ a2nxn = b2
                     ...
                        xr+ ar,r+1xr+1 +...+ arnxn = br 
 

    Тогда целевая функция имеет вид: 
 

    ? + Cr+1xr+1 + Cr+2xr+2 -...- Cnxn = C0 
 

    Нахождение  оптимального плана симплексным  методом включает    следующие  этапы:
1. Находят опорный  план.
      2. Составляют симплекс-таблицу. В общем виде: 

Базисные  неизвестные Свободные члены x1 x2 ... xr xr+1 xj xn
x1 x2
...
xi
...
xr
b1 b2
...
bi
...
br
1 0
...
0
...
0
0 1 

0 

0
  0 0
...
0
...
1
a1,r+1 a2,r+1
...
ai,r+1
...
ar,r+1
a1j a2j
...
aij
...
arj
a1n a2n
...
ain
...
arn
? C0 0 0 ... 0 Cr+2 Cj Cn
 
 
3. В  нижней строчке симплекс-таблицы необходимо отыскать отрицательные числа (не считая коэффициент Со). Если таких чисел нет, то данное базисное решение является оптимальным.
4. Пусть  элемент Сj<0,тогда в j-ом столбце необходимо найти положительный элемент. Если все коэффициенты этого столбца отрицательные, то решения не существует.
5. Если  положительный коэффициент в  j-ом столбце один, то выбранную строку с номером i надо поделить все коэффициенты на число aij.Результат деления записываем в новую симплекс-таблицу. Если же положительных коэффициентов несколько, необходимо составить отношение bi/aij и из полученных значений выбрать наименьшее, соответствующее i-ой строке.
6. В  новой симплекс-таблице в столбце  базисных неизвестных вместо  xi пишется xj. Продолжается заполняться таблица. В столбце с номером j необходимо получить нули(включая строку с целевой функцией). Для этого надо умножить i-ую записанную строку на нужное число и сложить с остальными строками.
    В результате осуществился переход к  новому базису, при этом значение целевой функции увеличилось. Выше указанные действия, начиная с пункта 3, повторяются до тех пор, пока в нижней строке таблицы все коэффициенты переменных не окажутся положительными. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Организационно-ознакомительная  часть
Нарисуйте таблицу с нужным числом строк и столбцов, нажав соответствующую кнопку. Заполните первую строчку таблицы коэффициентами f(x), левый столбец - номерами базисных переменных, внутренние поля таблицы - элементами расширенной матрицы системы. Для оценки правых частей используйте кнопку «ОЦЕНИТЬ Своб/Xn», выделив любой элемент соответствующего столбца, при этом оценки появятся в правом столбце. Выбирайте разрешающий элемент (начиная со 2-го шага) в нижней строке таблицы.  Для совершения симплекс-перехода выделите разрешающий элемент и нажмите кнопку «SIMPLEX» . Последняя клетка столбца «Своб» содержит текущее значение целевой функции.
      Программа позволяет освободиться от долгих вычислений, особенно при большом количестве переменных, что позволяет значительно  сэкономить время, так как пользователю приходится вводить лишь начальные данные и выбирать разрешающие элементы по выводимым данным. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Текст программы 

Private Sub DrawTab_Click() 'Нарисовать таблицу
m = Val(InputBox("Задайте  число уравнений (не>20):"))
If m < 1 Or m > 20 Then
    MsgBox ("Неверно  задано число уравнений!")
    GoTo 1
End If
n = Val(InputBox("Задайте  число переменных (не>20):"))
If n < 1 Or n > 20 Then
    MsgBox ("Неверно  задано число переменных!")
    GoTo 1
End If
For i = 1 To m + 3
    Cells(i, 1).Select
    With Selection.Borders(xlEdgeLeft)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(i, 1).Borders(xlEdgeRight)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(i, 1).Borders(xlEdgeTop)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(i, 1).Borders(xlEdgeBottom)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
   
    With Cells(i, n + 3).Borders(xlEdgeLeft)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(i, n + 3).Borders(xlEdgeRight)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(i, n + 3).Borders(xlEdgeTop)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(i, n + 3).Borders(xlEdgeBottom)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
Next i
For j = 1 To n + 3
    With Cells(1, j).Borders(xlEdgeLeft)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(2, j).Borders(xlEdgeLeft)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(m + 3, j).Borders(xlEdgeLeft)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(1, j).Borders(xlEdgeRight)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(2, j).Borders(xlEdgeRight)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(m + 3, j).Borders(xlEdgeRight)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(1, j).Borders(xlEdgeTop)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(2, j).Borders(xlEdgeTop)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(m + 3, j).Borders(xlEdgeTop)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(1, j).Borders(xlEdgeBottom)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(2, j).Borders(xlEdgeBottom)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
    With Cells(m + 3, j).Borders(xlEdgeBottom)
            .LineStyle = xlContinuous
            .Weight = xlMedium
    End With
Next j
For j = 2 To n + 1
    Cells(2, j).Value = "X" + Str$(j - 1)
Next j
Cells(2, n + 2).Value = "Своб"
Cells(2, n + 3).Value = " Своб /Xn"
Cells(1, 1).Value = "f(x)"
Cells(2, 1).Value = "Переменные"
Cells(m + 3, 1).Value = "f(x) после подстановки"
Columns("A:A").Select
Selection.Columns.AutoFit
Cells(1, 1).Select
Cells(100, 100).Value = m
Cells(100, 101).Value = n
Cells(25, 1).Value = "Заполните  таблицу данными, затем выберите  наименьшее отрицательное значение  в поле: 'f(x)' и нажмите: 'Оценить Своб/Xn'"
1
End Sub 

Private Sub SXn_Click() 'SXn
Cells(25, 1).Value = ""
If Cells(100, 100).Value = "" Or Cells(100, 101).Value = "" Then
    MsgBox ("Не задано число уравнений и/или переменных!" + Chr(13) + "Воспользуйтесь кнопкой НАРИСОВАТЬ ТАБЛИЦУ")
    GoTo 1
End If
m = Cells(100, 100).Value
n = Cells(100, 101).Value 
 

adr$ = ActiveCell.Address
l = Len(adr)
p = InStr(2, adr, "$")
adrR$ = Right(adr, l - p)
adrC$ = Mid(adr, 2, l - Len(adrR$) - 2)
   
y = Asc(adrC$) - 65 

If y < 1 Or y > n Then
    MsgBox ("Выбран столбец вне пределов таблицы!")
    GoTo 1
End If 

For i = 1 To m
    If Cells(i + 2, y + 1).Value = 0 Then
        Cells(i + 2, n + 3).Value = ""
        Else
        Cells(i + 2, n + 3).Value = Cells(i + 2, n + 2).Value / Cells(i + 2, y + 1).Value
    End If
Next i
Cells(25, 1).Value = "Выберите наименьшее значение в столбце: 'Своб/Xn', затем выберите разрешающий элемент и нажмите 'SIMPLEX'"
1
End Sub 

Private Sub Simplex_Click() 'Симплекс-преобразование
Cells(25, 1).Value = ""
If Cells(100, 100).Value = "" Or Cells(100, 101).Value = "" Then
    MsgBox ("Не задано число уравнений и/или переменных! Воспользуйтесь кнопкой НАРИСОВАТЬ ТАБЛИЦУ")
    GoTo 1
End If
m = Cells(100, 100).Value
n = Cells(100, 101).Value
ReDim a(m, n), c(n), b(m), w(m) 
 

adr$ = ActiveCell.Address
l = Len(adr)
p = InStr(2, adr, "$")
adrR$ = Right(adr, l - p)
adrC$ = Mid(adr, 2, l - Len(adrR$) - 2)
   
x = Val(adrR$) - 2
y = Asc(adrC$) - 65 

If x < 1 Or x > m Or y < 1 Or y > n Then
    MsgBox ("Выбрана клетка вне пределов таблицы!")
    GoTo 1
End If
For i = 1 To m
    If i = x Then
        For j = 1 To n
         a(i, j) = Cells(i + 2, j + 1).Value / Cells(x + 2, y + 1).Value
         b(i) = Cells(i + 2, n + 2).Value / Cells(x + 2, y + 1).Value
        Next j
    Else
        For j = 1 To n
            a(i, j) = Cells(i + 2, j + 1).Value - Cells(x + 2, j + 1).Value * Cells(i + 2, y + 1).Value / Cells(x + 2, y + 1).Value
            b(i) = Cells(i + 2, n + 2).Value - Cells(x + 2, n + 2).Value * Cells(i + 2, y + 1).Value / Cells(x + 2, y + 1).Value
        Next j
    End If
Next i 

Cells(x + 2, 1).Value = y 

For i = 1 To m
    For j = 1 To n
        Cells(i + 2, j + 1).Value = a(i, j)
    Next j
    Cells(i + 2, n + 2).Value = b(i)
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.