F Б’ = - 2 , F Б’’ = - 3, 5 > - 2 > - 3 .
Задача решена.
Производственный
план
Составление плана
(программы) колхоза, цеха , завода, отрасли промышленности является одной из
важнейших задач экономики народного хозяйства. Решение таких задач осложняется
тем, что приходится находить значение не двух и не трех переменных величин -
число переменных может быть от нескольких десятков до нескольких сотен и даже
тысяч. Рассмотрим простейшую задачу составления производственного плана.
Некоторому заводу требуется составить
оптимальный по реализации производственный план выпуска трех видов изделий при
определенных возможностях пяти видов машин. План выпуска должен быть таким,
чтобы от реализации выпущенной по этому плану продукции завод получил бы
наибольшую прибыль.
Все данные, необходимые
для решения задачи, приведены в таблице ниже. В таблице указано все необходимое
для обработки каждого изделия, предложенными машинами. Все изделия
последовательно обрабатываются этими машинами. Время, необходимое для обработки
каждого изделия задаётся таблицей. Нуль означает, что изделие машинами данного
типа не обрабатывается.
Таблица
1 "Исходные данные"
|
Машины
Изделия
|
1
|
2
|
3
|
4
|
5
|
Рj
|
I
|
0.5
|
2
|
2
|
1
|
0
|
22
|
II
|
0.5
|
1
|
0
|
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
Заметим, что :
1) ограничения системы имеют вид и
неравенств, и уравнений;
2) требуется максимизировать значение
целевой функции.
Правило прямоугольника:
Расчет значений табличных
данных ведется по правилу прямоугольника.
Элементы разрешающей
строки (строка в которой находится разрешающий элемент) получается из
соответствующих элементов прежней строки на разрешающий элемент.
Все элементы разрешающего
столбца преобразованной таблицы кроме разрешающего элемента равны нулю.
Все остальные элементы
пересчитываются по правилу прямоугольника.
Где:
aij – элемент находящийся
в i строке, j столбце
akk – разрешающий элемент
aki - элемент находящийся
в i строке, j столбце
aik - элемент находящийся
в i строке, j столбце
После преобразований я
получил следующую таблицу:
Решение
задания по курсовому проекту вручную
|
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
X7
|
X8
|
Св.член
|
X4
|
0,5
|
0,5
|
2
|
1
|
0
|
0
|
0
|
0
|
9
|
X5
|
2
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
12
|
X6
|
2
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
12
|
X7
|
1
|
2
|
0,5
|
0
|
0
|
0
|
1
|
0
|
8
|
X8
|
0
|
0,5
|
1
|
0
|
0
|
0
|
0
|
1
|
16
|
Fmin
|
22
|
36
|
28
|
0
|
0
|
0
|
0
|
0
|
0
|
X4
|
0,25
|
0
|
1,875
|
1
|
0
|
0
|
0
|
0
|
7
|
X5
|
1,5
|
0
|
0,75
|
0
|
1
|
0
|
0
|
0
|
8
|
X6
|
2
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
12
|
X2
|
0,5
|
1
|
0,25
|
0
|
0
|
0
|
0,5
|
0
|
4
|
X8
|
0,25
|
0
|
0,875
|
0
|
0
|
0
|
0
|
1
|
14
|
Fmin
|
4
|
0
|
19
|
0
|
0
|
0
|
0
|
0
|
-144
|
X3
|
0,133
|
0
|
1
|
0,533
|
0
|
0
|
0
|
0
|
3,733
|
X5
|
1,4
|
0
|
0
|
- 1,406
|
1
|
0
|
0
|
0
|
5,2
|
X6
|
1,866
|
0
|
0
|
- 0,533
|
0
|
1
|
0
|
0
|
8,266
|
X2
|
0,466
|
1
|
0
|
- 0,133
|
0
|
0
|
0,5
|
0
|
3,067
|
X8
|
0,383
|
0
|
0
|
- 0,466
|
0
|
0
|
0
|
1
|
10,733
|
Fmin
|
1.466
|
0
|
0
|
- 1064
|
0
|
0
|
0
|
0
|
- 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
Мы достигли оптимального
решения.
Алгоритм программы
1. Вводим данные в таблицу
2. Находим разрешающий элемент:
2.1. Берем каждый элемент первой строки и
делим на свободный член первой строки.
2.2. Находим среди всех деленных элементов
минимальный.
2.3. Берем каждый элемент второй строки и
делим на свободный член второй строки.
2.4. Находим среди всех деленных элементов
минимальный.
2.5. Берем каждый элемент третей строки и
делим на свободный член третей строки.
2.6. Находим среди всех деленных элементов
минимальный.
2.7. Берем минимальные элементы первой,
второй и третей строки и среди них находим минимальный (это и будет разрешающий
элемент).
3. Вычисляем всю таблицу методом
прямоугольника относительно разрешающего элемента:
3.1. Умножаем разрешающий элемент на
элемент решаемой строки.
3.2. Отнимаем произведение
соответствующего элемента решаемой строки на элемент разрешающего столбца
решаемой строки
3.3. И делим ответ на разрешающий элемент.
4. Делим разрешающую строку на
разрешающий элемент.
4.1. Берем каждый элемент разрешающей
строки и делим на разрешающий элемент.
5. Всем элементам, кроме разрешающего
элемента, разрешающего столбца присвоить ( 0 )
6. Разрешающему элементу присвоить ( 1
).
7. В индексе разрешающей строки
присвоить индекс разрешающего столбца.
8. Если на F строке существуют
отрицательные элементы то вернутся к пункту 2, если отрицательных нет то
перейти к пункту 9.
9. Проверяем F на оптимальность.
9.1. Подставляем в целевую функцию
значения из свободного члена с соответствующим индексом.
9.2. Складываем все элементы.
9.3. Сравниваем ответ целевой функции с
элементом свободного члена F строки.
10. Получаем оптимальный
план.
Текст программы для ЭВМ с операционной
системой Win95/Win98
'описание рабочих переменных
и констант
Const r = 5 ' строки
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
<= n
If f(u) < 0
And i = 0 Then
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 < n
Then txtControl.Text = txtControl.Text & "+"
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) < 0
And f(jr) < f(j) Then jr = j
Next j
i = 1
While i <=
r
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
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 <= 57 And grdData.Col = 0) Then
If
Chr(KeyAscii) <= n Then
If grdData.Row
<= r Then
grdData.Text =
" "
p(grdData.Col)
= Chr(KeyAscii)
End If
Else
Exit Sub
End If
End If
If (KeyAscii =
45) And (grdData.Col > 0) Then grdData.Text = Chr(KeyAscii)
If (((KeyAscii
>= 48 And KeyAscii <= 57) Or (KeyAscii = 46)) And (grdData.Col > 0))
Or _
((KeyAscii
>= 48 And KeyAscii <= 57) And (grdData.Col = 0) And (grdData.Row <=
r)) Then
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
End Sub
Список используемой
литературы
1.
Шыныбаев М.А. "Курсовая
работа по моделированию производственных и экономических процессов." -
Талдыкорган. ТПТК 1999 г.
2.
Солодовников А.С.
"Введение в линейную алгебру и линейное программирование." - М.
Просвещение, 1966.
3.
Банди Б. "Методы
оптимизации" - М. Радио и связь, 1988.
4.
Дебора Курата. "Использование
объектов в среде Visual Basic". М. Институт освоения
информационных систем1998г.
5.
Скотт Б. "Программирование
Visual Basic 5.0." 1999г.
6.
Рамакин Н.И "Элементы
линейной алгебры и линейного программирования" Москва "Просвещение
1963г"
7.
Солодовский А.С "Системы
линейных неравенств" 2-е издание
8.
Наука 1977г
9.
Кузнецов Ю.Н "Математическое
программирование" г Москва
10.
Высшая школа
1980г