Узнать стоимость написания работы
Оставьте заявку, и в течение 5 минут на почту вам станут поступать предложения!
Реферат

Реферат по предмету "Информатика"


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

Оглавление
Введение
Метод решения задачи
Производственный план
Задание по курсовому проекту
Решение задания по курсовому проекту вручную
Алгоритм программы
Текст программы
Список используемой литературы
Введение
Каждый человек время от времени оказывается в ситуации, когда достижение некоторого результата может быть осуществлено не единственным способом. В таких случаях приходится отыскивать наилучший способ. Однако в различных ситуациях наилучшим могут быть совершенно различные решения. Все зависит от выбранного или заданного критерия. Пусть, например, ученик живет далеко от школы и может добраться до школы на трамвае за 30 минут или же часть пути проехать на трамвае, а потом пересесть на троллейбус и затратить при этом всего 20 минут. Оценим оба решения. Очевидно, второе решение будит лучшим, если требуется попасть в школу за минимальное время, т.е. оно лучше по критерию минимизации времени. По другому критерию (например, минимизации стоимости или минимизации числа пересадок) лучшим является первое решение. На практике оказывается, что большинство случаев понятие «наилучший» может быть выражено количественными критериями — минимум затрат, минимум отклонений от нормы, максимум скорости, прибыли и т.д. Поэтому возможна постановка математических задач отыскания оптимального (optimum — наилучший) результат, так как принципиальных различий в отыскании наименьшего или наибольшего значения нет. Задачи на отыскание оптимального решения называются оптимизационными задачами. Оптимальный результат, как правило, находиться не сразу, а в результате процесса, называемого процессом оптимизации. Применяемые в процессе оптимизации методы получили название методов оптимизации. В простейших случаях мы сразу переводим условие задачи на математический язык и получаем ее так называемую математическую формулировку. Однако на практике процесс формализации задачи достаточно сложен. Пусть, например, требуется распределить различные виды обрабатываемые в данном цехе изделий между различными типами оборудования таким образом, чтобы обеспечить выполнение заданного плана выпуска изделий каждого вида с минимальными затратами. Весь процесс решения задачи представляется в виде следующих этапов:
Изучение объекта. При этом требуется понять происходящий процесс, определить необходимые параметры (например, число различных и взаимозаменяемых типов оборудования, его производительность по обработке каждого вида изделий и т.д.).
Описательное моделирование — установление и словесная фиксация основных связей и зависимостей между характеристиками процесса с точки зрения оптимизируемого критерия.
Математическое моделирование — перевод описательной модели на формальный математический язык. Все условия записываются в виде соответствующей системы ограничений (уравнения и неравенства). Любое решение этой системы называется допустимымрешением. Критерий записывается в виде функции, которую обычно называют целевой. Решение задачи оптимизации состоит в отыскании на множестве решений системы ограничений максимального или максимального значения целевой функции.
Выбор(или создание) метода решения задачи. Так как задача уже записана в математической форме, ее конкретное содержание нас не интересует. Дело в том, что совершенно разные по содержанию задачи часто приводятся к одной и той же формальной записи. Поэтому при выборе метода решения главное внимание обращается не на содержание задачи, а на полученную математическую структуру. Иногда специфика задачи может потребовать какой — либо модификации уже известного метода или даже разработки нового.
Выбор или написание программы для решения задачи на ЭВМ. Подавляющая часть задач, возникающих на практике, из-за большого числа переменных и зависимости между ними могут быть решены в разумные строки только с помощью ЭВМ. Для решения задачи на ЭВМ прежде всего следует составить (или использовать уже готовую, если аналогичная задача уже решалась на ЭВМ) программу, реализующую выбранный метод решения.
Решение задачи на ЭВМ. Вся необходимая информация для решения задачи на ЭВМ вводится в память машины вместе с программой. В соответствии с программой решения ЭВМ производит необходимую обработку в веденной числовой информации, получает соответствующие результаты, которые выдает человеку в удобной для него форме.
Анализ полученного решения. Анализ решения бывает двух видов: формальный(математический), когда проверяется соответствие полученного решения построенной математической модели (в случае несоответствия проверяются программа, исходные данные, работа ЭВМ и т.д.), и содержательный (экономический, технологический и т.п.), когда проверяется соответствие полученного решения тому объекту, который моделировался. В результате такого анализа в модель могут быть внесены изменения или уточнения, после чего весь разобранный процесс повторяется. Модель считается построенной и завершенной, если она с достаточной точностью характеризует деятельность объекта по выбранному критерию. Только после этого модель может быть использована для расчета.
Метод решения задачи
Симплексный метод был разработан известным американским математиком Дж. Данцигом и в настоящее время стал универсальным методом решения задач линейного программирования. Алгоритм метода состоит из ряда шагов.
При решении задачи симплекс методом необходимо систему уравнений привести к виду, когда какие-либо r переменные (базисные) выражены через остальные (небазисные), причем свободные члены этих выражений должны быть неотрицательными.
Пусть для определенности X1, X2, X3… Xr выражены через остальные переменные Xr+1, Xr+2,Xr+3,...Xn.
Система ограничений принимает вид:
/>( 1 )
где />
Базис (X1, X2, X3… Xr) обозначим через Б. Пусть все небазисные переменные равны нулю:
/>.
Найдем из системы ( 1 ) значение базисных переменных :
/>
В результате получаем базисное решение/> соответствующее базису Б .
Целевая функция F ( X1, ...., Xn) также выражается через небазисные переменные :
/>/>
Замечаем, что значение целевой функции, соответствующее базисному решению, равно :/>C0: FБ = C0.
Следующим шагом алгоритма является проверка достижения оптимума. Если оптимум не достигнут, то из базиса Б удаляется одна из переменных в небазисные, а вместо нее из числа прежних небазисных переменных вводится новая. Получаем новый базис Б’ .
С новым базисом поступаем так же в соответствии с содержанием шагов 1 и 2. Если в результате этого оптимум не достигнут, то все шаги повторяем снова, причем каждый новый шаг заключается в переходе от базиса Б к новому базису Б’, такому, что значение Fб уменьшается или, по крайней мере, не увеличивается: Fb’
Этот процесс оканчивается одним из трех случаев: либо находится оптимум, либо доказывается противоречивость ограничений, либо доказывается неограниченность целевой функции при базисных решениях, т. е. Тот случай, когда задача решений не имеет.
Проследим за этой последовательностью шагов на примерах.
Задача 4.2.1.Минимизировать F=X2-X1при неотрицательных X1 и X2, удовлетворяющих системе ограничений:
/>
Решение. Запишем ограничения как уравнения, выражающие базисные переменные через небазисные :
X3=2+2X1-X2
X4 = 2-X1+2X2
X5= 5-X1-X2
Пусть базис Б состоит из переменных X3,X4,X5. Тогда базисное решение -(0;0;2;2;5). Теперь надо выразить F через небазисные переменные. В нашем конкретном случае это, оказывается, уже сделано.
Проверим, достигла ли целевая функция своего минимального значения. Коэффициент при X1 в выражении для F отрицателен. Следовательно, возрастание X1 приведет к дальнейшему уменьшению F. Однако при увеличении X1 переменные X3X4X5 могут уменьшатся, и необходимо следить за тем, чтобы ни одна из них не стала отрицательной. Так как увеличение X1ведет к увеличению X3, то для этой переменной такой опасности не существует. Из анализа других базисных переменных получаем, что значение X1 может быть увеличено до 2. Такое увеличение даст X4=0, X3=6, X5=3. Этот результат нас устраивает, так как число положительных переменных такое же, как и решение. Новый базис Б’ состоит из X1, X3, X5. Чтобы приступить к выполнению следующего шага, выразим эти переменные и целевую функцию F через небазисные переменные X2 и X4. Это легко сделать, если решить второе уравнение относительно новой базисной переменной X1, а подстановка этого выражения в остальные уравнения и целевую функцию F дает:--PAGE_BREAK--
/>
Коэффициент при X2 функции F отрицателен. Поэтому можно и дальше уменьшать целевую функцию F, увеличивая X2.однако X2 можно увеличивать не более, чем до 1: это следует из уравнения X5=3-3 X2+ X4 ( если X2>1, X4=0, то X5
/>
Базис Б’’ состоит из переменных X1, X2, X3 ,
/>
Увеличивая X4 и X5, мы уже не можем получить дальнейшего уменьшения F. Следовательно, нами получено оптимальное решение. Наименьшее значение F, равное -3, достигается при X1=4, X2=1, X3=9.
Сравним значение целевой функции, соответствующие различными базисами:
F Б = 5, F Б’ = — 2, F Б’’ = — 3, 5 > — 2 > — 3 .
Задача решена.
Производственный план
Составление плана (программы) колхоза, цеха, завода, отрасли промышленности является одной из важнейших задач экономики народного хозяйства. Решение таких задач осложняется тем, что приходится находить значение не двух и не трех переменных величин — число переменных может быть от нескольких десятков до нескольких сотен и даже тысяч. Рассмотрим простейшую задачу составления производственного плана.
Задание по курсовому проекту
Некоторому заводу требуется составить оптимальный по реализации производственный план выпуска трех видов изделий при определенных возможностях пяти видов машин. План выпуска должен быть таким, чтобы от реализации выпущенной по этому плану продукции завод получил бы наибольшую прибыль.
Все данные, необходимые для решения задачи, приведены в таблице ниже. В таблице указано все необходимое для обработки каждого изделия, предложенными машинами. Все изделия последовательно обрабатываются этими машинами. Время, необходимое для обработки каждого изделия задаётся таблицей. Нуль означает, что изделие машинами данного типа не обрабатывается.
Таблица 1 «Исходные данные»
Машины
Изделия
1
2
3
4
5
Рj
I
0.5
2
2
1
22
II
0.5
1
2
0.5
36
III
2.
1
1
0.5
1
28
t
9
12
12
8
16


Завод от реализации одного изделия вида j получает Pj прибыли. Числовые данные этих переменных задаются следующими значениями:
t1=9, t2=12, t=12, t=8, t=16. Р1=22, Р2=36, Р3=28.
Хi – количество выпускаемой продукции.
Составим математическую модель задачи.
Построим математическую модель этой задачи. Пусть Х1 число изделий вида I, Х2 — число изделий вида II, а Х3 — число изделий вида III. Так как машины каждого вида (1,2,3,4,5) могут обрабатывать продукцию не более 9, 12, 12, 8, 16 часов соответственно, то приходим к следующей системе ограничений:
/>0,5х1 + 0,5х2 +2х3£ 9
2х1 + х2 + х3£ 12
2 х1 + 0 + х3£ 12
х1 + 2 х2 +0,5х3£ 8
0 + 0,5х2+ х3£ 16
х1³ 0
х2³ 0
х3³ 0
F max = 22х1 + 36х2 + 28х3
Решаем задачу симплекс методом. Вводим дополнительные неопределенные данные – (Х4, Х5, Х6, Х7, Х8), тогда система ограничений имеет следующий вид.
/>0,5 х1 + 0,5 х2 + 2 х3 + х4£ 9
2х1 + х2 + х3 + х5£ 12
/>2х1 + х3 + х6£ 12
х1 + 2х2 + 0,5х3 + х7£ 8
0,5х2 + х3 + х8£ 16
Заметим, что :
ограничения системы имеют вид и неравенств, и уравнений;
требуется максимизировать значение целевой функции.
Правило прямоугольника:
Расчет значений табличных данных ведется по правилу прямоугольника.
Элементы разрешающей строки (строка в которой находится разрешающий элемент) получается из соответствующих элементов прежней строки на разрешающий элемент.
Все элементы разрешающего столбца преобразованной таблицы кроме разрешающего элемента равны нулю.
Все остальные элементы пересчитываются по правилу прямоугольника.
/>
Где:
aij – элемент находящийся в i строке, j столбце
akk – разрешающий элемент
aki — элемент находящийся в i строке, j столбце
aik — элемент находящийся в i строке, j столбце
После преобразований я получил следующую таблицу:
Решение задания по курсовому проекту вручную


X1
X2
X3
X4
X5
X6
X7
X8    продолжение
--PAGE_BREAK--
Св.член
X4
0,5
0,5
2
1
9
X5
2
1
1
1
12
X6
2
1
1
12
X7
1
2
0,5
1
8
X8
0,5
1
1
16
Fmin
22
36
28
X4
0,25
1,875
1
7
X5
1,5
0,75
1
8
X6
2
1
1
12
X2
0,5
1
0,25
0,5
4
X8
0,25
0,875
1
14
Fmin
4
19
-144
X3
0,133
1
0,533
3,733
X5
1,4
— 1,406
1
5,2
X6
1,866
— 0,533
1
8,266
X2
0,466
1
— 0,133
0,5
3,067
X8
0,383
— 0,466
1
10,733
Fmin
1.466
— 1064
— 214.933
Отсюда мы получаем: X1=0, X2=3.067, X3=3.733, X4=0, X5=5.2, X6 =8.266, X8 =10.733 P= — 214.933
Система уравнения примет вид:
/>
Целевая функция равна:
Fmax = — Fmin
Fmax = 22*х1 + 36*х2 + 28*х3
22*0 + 36* 3,066 + 28*3,733 = 214,933
Мы достигли оптимального решения.
Алгоритм программы
Вводим данные в таблицу
Находим разрешающий элемент:
Берем каждый элемент первой строки и делим на свободный член первой строки.
Находим среди всех деленных элементов минимальный.
Берем каждый элемент второй строки и делим на свободный член второй строки.    продолжение
--PAGE_BREAK--
Находим среди всех деленных элементов минимальный.
Берем каждый элемент третей строки и делим на свободный член третей строки.
Находим среди всех деленных элементов минимальный.
Берем минимальные элементы первой, второй и третей строки и среди них находим минимальный (это и будет разрешающий элемент).
Вычисляем всю таблицу методом прямоугольника относительно разрешающего элемента:
Умножаем разрешающий элемент на элемент решаемой строки.
Отнимаем произведение соответствующего элемента решаемой строки на элемент разрешающего столбца решаемой строки
И делим ответ на разрешающий элемент.
Делим разрешающую строку на разрешающий элемент.
Берем каждый элемент разрешающей строки и делим на разрешающий элемент.
Всем элементам, кроме разрешающего элемента, разрешающего столбца присвоить ( 0 )
Разрешающему элементу присвоить ( 1 ).
В индексе разрешающей строки присвоить индекс разрешающего столбца.
Если на F строке существуют отрицательные элементы то вернутся к пункту 2, если отрицательных нет то перейти к пункту 9.
Проверяем F на оптимальность.
Подставляем в целевую функцию значения из свободного члена с соответствующим индексом.
Складываем все элементы.
Сравниваем ответ целевой функции с элементом свободного члена F строки.
10. Получаем оптимальный план.
Текст программы для ЭВМ с операционной системой Win95/Win98
'описание рабочих переменных и констант
Const r = 5 ' строки
Const n = 7 ' столбцы
Private p, f, xn(r), fm
Private x(r, n)
Private Sub btnExit_Click()
'процедура выхода из пограммы
End
btnExit.Caption = «Готово»
End Sub
' присвоение значений переменным
i = 0
u = 1
' распределение данных по строкам и столбцам
1: While u
If f(u)
i = u
End If
If f(u) = 0 Then
tr = 0
For j = 1 To r
If u = p(j) Then
tr = 1
End If
Next j
If tr = 0 Then
MsgBox «Система имеет множество решений», vbOKOnly, " -Simplex- "
Exit Sub
End If
End If
u = u + 1
Wend
'обработка исходных данных
4: If i = 0 Then
lblTitle = «Оптимальная работа»
' вывод данных в текстовое поле проверки
txtControl.Text = "Проверка" & Chr(13) & Chr(10)
For i = 1 To n
jt = 0
For j = 1 To r
If p(j) = i Then jt = x(j, 0)
Next j
Next i
For k = 1 To r
For i = 1 To n
jt = 0
For j = 1 To r
If p(j) = i Then jt = x(j, 0)
Next j
s = s + xn(k)(i) * jt
txtControl.Text = txtControl.Text & Str(xn(k)(i)) & "*" & Str(jt)
If i
Next i
txtControl.Text = txtControl.Text & " = " & Str(xn(k)(0)) & Chr(13) & Chr(10)
Next k
btnNext.Caption = "Готово"
btnNext.Enabled = False
lblRes.Visible = True
Exit Sub
End If
jr = i
For j = i + 1 To n
If f(j)
Next j
i = 1
While i
If x(i, jr) > 0 Then GoTo 5
i = i + 1
Wend
MsgBox Str(jr) & " " & Chr(13) & Chr(10) & "Решениянет"
Exit Sub
' нахождение разрешающего элемента
5: ir = i
Min = x(i, 0) / x(i, jr)
For j = i + 1 To r
If x(j, jr) > 0 Then
d = x(j, 0) / x(j, jr)
If Min > d Then
Min = d    продолжение
--PAGE_BREAK--
ir = j
End If
End If
Next j
k = x(ir, jr)
For j = 0 To n
x(ir, j) = x(ir, j) / k
Next j
For i = 1 To r
If i ir Then
d = x(i, jr)
For j = 0 To n
x(i, j) = x(i, j) — x(ir, j) * d
Next j
End If
Next i
d = f(jr)
For j = 0 To n
f(j) = f(j) — x(ir, j) * d
Next j
p(ir) = jr
' вывод данных в таблицу
grdData.Row = r + 1
For i = 1 To n + 1
grdData.Col = i
grdData.Text = Str(f(i — 1))
Next i
For i = 1 To r
grdData.Row = i
For j = 0 To n + 1
grdData.Col = j
If j = 0 Then
grdData.Text = " = " & Str(p(i))
Else
grdData.Text = Str(x(i, j — 1))
End If
Next j
Next i
End Sub
Private Sub Form_Load()
'основная матрица
lblyr(0).Caption = " 9 = 0.5X1 + 0.5X2 + 2X3 + X4 + 0X5 + 0X6 + 0X7 + 0X8"
lblyr(1).Caption = " 12 = 2X1 + X2 + X3 + 0X4 + X5 + 0X6 + 0X7 + 0X8"
lblyr(2).Caption = " 12 = 2X1 + 0X2 + X3 + 0X4 + 0X5 + X6 + 0X7 + 0X8"
lblyr(3).Caption = " 8 = X1 + 2X2 + 0.5X3 + 0X4 + 0X5 + 0X6 + X7 + 0X8"
lblyr(4).Caption = " 16 = 0X1 + 0.5X2 + X3 + 0X4 + 0X5 + 0X6 + 0X7 + X8"
lblyr(5).Caption = " F = 22 + 36 + 28 + 0 + 0 + 0 + 0 + 0"
' Загрузка массива исходных данных
p = Array(pv(0), pv(1), pv(2), pv(3), pv(4), pv(5))
fm = Array(fmMin(0), fmMin(1), fmMin(2), fmMin(3), fmMin(4), fmMin(5), fmMin(6), fmMin(7))
f = fm
xn(1) = Array(Ar(1, 0), Ar(1, 1), Ar(1, 2), Ar(1, 3), Ar(1, 4), Ar(1, 5), Ar(1, 6), Ar(1, 7))
xn(2) = Array(Ar(2, 0), Ar(2, 1), Ar(2, 2), Ar(2, 3), Ar(2, 4), Ar(2, 5), Ar(2, 6), Ar(2, 7))
xn(3) = Array(Ar(3, 0), Ar(3, 1), Ar(3, 2), Ar(3, 3), Ar(3, 4), Ar(3, 5), Ar(3, 6), Ar(3, 7))
xn(4) = Array(Ar(4, 0), Ar(4, 1), Ar(4, 2), Ar(4, 3), Ar(4, 4), Ar(4, 5), Ar(4, 6), Ar(4, 7))
xn(5) = Array(Ar(5, 0), Ar(5, 1), Ar(5, 2), Ar(5, 3), Ar(5, 4), Ar(5, 5), Ar(5, 6), Ar(5, 7))
grdData.Row = r + 1
For i = 1 To n + 1
grdData.Col = i
'запись строки в таблицу
grdData.Text = Str(f(i — 1))
Next i
For i = 1 To r
grdData.Row = i
For j = 0 To n + 1
grdData.Col = j
If j = 0 Then
grdData.Text = " = " & Str(p(i — 1))
Else
x(i, j — 1) = xn(i)(j — 1)
grdData.Text = Str(x(i, j — 1))
End If
Next j
Next i
grdData.Cols = n + 2
grdData.Rows = r + 2
grdData.Col = 0
grdData.Row = 0
grdData.Text = "Св. член"
For i = 1 To n + 1
grdData.Col = i
grdData.Text = «X» & Str(i)
Next i
grdData.Col = 0
grdData.Row = r + 1
grdData.Text = «Fmin»
End Sub
'Private Sub grdData_KeyDown(KeyCode As Integer, Shift As Integer)
If (KeyCode = vbKeyDelete Or KeyCode = vbKeyBack) Or (Len(grdData.Text) = 2 And grdData.Col = 0) Then
grdData.Text = ""
End If
End Sub
Private Sub grdData_KeyPress(KeyAscii As Integer)
If (KeyAscii >= 48 And KeyAscii
If Chr(KeyAscii)
If grdData.Row
grdData.Text = " "
p(grdData.Col) = Chr(KeyAscii)
End If    продолжение
--PAGE_BREAK--
Else
Exit Sub
End If
End If
If (KeyAscii = 45) And (grdData.Col > 0) Then grdData.Text = Chr(KeyAscii)
If (((KeyAscii >= 48 And KeyAscii 0)) Or _
((KeyAscii >= 48 And KeyAscii
grdData.Text = grdData.Text & Chr(KeyAscii)
End If
End Sub
Private Sub cmdIn_Click()
frmFlash.Show
cmdIn.Visible = False
cmdIninf.Visible = True
End Sub
Private Sub cmdIninf_Click()
Dim i
For i = 0 To 4
If Text1(i).Text = "" Then Text1(i).Text = 0
pv(i) = CSng(Text1(i).Text)
Next
For i = 0 To 7
If Text2(i).Text = "" Then Text2(i).Text = 0
fmMin(i) = CSng(Text2(i).Text)
Next
For i = 0 To 7
If Text3(i).Text = "" Then Text3(i).Text = 0
Ar(1, i) = CSng(Text3(i).Text)
Next
For i = 0 To 7
If Text4(i).Text = "" Then Text4(i).Text = 0
Ar(2, i) = CSng(Text4(i).Text)
Next
For i = 0 To 7
If Text5(i).Text = "" Then Text5(i).Text = 0
Ar(3, i) = CSng(Text5(i).Text)
Next
For i = 0 To 7
If Text6(i).Text = "" Then Text6(i).Text = 0
Ar(4, i) = CSng(Text6(i).Text)
Next
For i = 0 To 7
If Text7(i).Text = "" Then Text7(i).Text = 0
Ar(5, i) = CSng(Text7(i).Text)
Next
Load frmSimpl
frmSimpl.Show
frmIn.Hide
EndSub
/>
/>
/>
/>
/>
/>
Список используемой литературы
Шыныбаев М.А. «Курсовая работа по моделированию производственных и экономических процессов.» — Талдыкорган. ТПТК 1999 г.
Солодовников А.С. «Введение в линейную алгебру и линейное программирование.» — М. Просвещение, 1966.
Банди Б. «Методы оптимизации» — М. Радио и связь, 1988.
Дебора Курата. «Использование объектов в среде Visual Basic». М. Институт освоения информационных систем1998г.
Скотт Б. «Программирование Visual Basic 5.0.» 1999г.
Рамакин Н.И «Элементы линейной алгебры и линейного программирования» Москва «Просвещение 1963г»
Солодовский А.С «Системы линейных неравенств» 2-е издание
Наука 1977г
Кузнецов Ю.Н «Математическое программирование» г Москва
Высшая школа 1980г


Не сдавайте скачаную работу преподавателю!
Данный реферат Вы можете использовать для подготовки курсовых проектов.

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем реферат самостоятельно:
! Как писать рефераты
Практические рекомендации по написанию студенческих рефератов.
! План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом.
! Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач.
! Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты.
! Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ.

Читайте также:
Виды рефератов Какими бывают рефераты по своему назначению и структуре.