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

/>/>Оглавление

Введение

Метод решения задачи

Производственный план

Заданиепо курсовому проекту

Решение задания по курсовомупроекту вручную

Алгоритм программы

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

Списокиспользуемой литературы 
Введение

Каждый человек время отвремени оказывается в ситуации, когда достижение некоторого результата можетбыть осуществлено не единственным способом. В таких случаях приходитсяотыскивать наилучший способ. Однако в различных ситуациях наилучшим могут бытьсовершенно различные решения. Все зависит от выбранного или заданного критерия.Пусть, например, ученик живет далеко от школы и может добраться до школы натрамвае за 30 минут или же часть пути проехать на трамвае, а потом пересесть натроллейбус и затратить при этом всего 20 минут. Оценим оба решения. Очевидно,второе решение будит лучшим, если требуется попасть в школу за минимальноевремя, т.е. оно лучше по критерию минимизации времени. Подругому критерию (например, минимизации стоимости или минимизации числапересадок) лучшим является первое решение. На практике оказывается, чтобольшинство случаев понятие «наилучший» может быть выраженоколичественными критериями — минимум затрат, минимум отклонений от нормы,максимум скорости, прибыли и т.д. Поэтому возможна постановка математическихзадач отыскания оптимального (optimum — наилучший) результат, так как принципиальныхразличий в отыскании наименьшего или наибольшего значения нет. Задачи наотыскание оптимального решения называются оптимизационными задачами.Оптимальный результат, как правило, находиться не сразу, а в результатепроцесса, называемого процессом оптимизации. Применяемые в процессе оптимизацииметоды получили название методов оптимизации. В простейшихслучаях мы сразу переводим условие задачи на математический язык и получаем еетак называемую математическую формулировку. Однако на практикепроцесс формализации задачи достаточно сложен. Пусть, например, требуетсяраспределить различные виды обрабатываемые в данном цехе изделий междуразличными типами оборудования таким образом, чтобы обеспечить выполнениезаданного плана выпуска изделий каждого вида с минимальными затратами. Весьпроцесс решения задачи представляется в виде следующих этапов:

1.  Изучение объекта. При этом требуется понять происходящий процесс,определить необходимые параметры (например, число различных и взаимозаменяемыхтипов оборудования, его производительность по обработке каждого вида изделий ит.д.).

2.  Описательное моделирование — установление и словесная фиксация основных связей изависимостей между характеристиками процесса с точки зрения оптимизируемогокритерия.

3.  Математическое моделирование — перевод описательной модели наформальный математический язык. Все условия записываются в виде соответствующейсистемы ограничений (уравнения и неравенства). Любое решение этой системыназывается допустимымрешением. Критерий записывается ввиде функции, которую обычно называют целевой. Решение задачиоптимизации состоит в отыскании на множестве решений системы ограничениймаксимального или максимального значения целевой функции.

4.  Выбор(или создание) метода решения задачи.Так как задача уже записана в математической форме, ее конкретное содержаниенас не интересует. Дело в том, что совершенно разные по содержанию задачи частоприводятся к одной и той же формальной записи. Поэтому при выборе методарешения главное внимание обращается не на содержание задачи, а на полученнуюматематическую структуру. Иногда специфика задачи может потребовать какой — либомодификации уже известного метода или даже разработки нового.

5.  Выбор или написание программы длярешения задачи на ЭВМ.Подавляющая часть задач, возникающих на практике, из-за большого числапеременных и зависимости между ними могут быть решены в разумные строки толькос помощью ЭВМ. Для решения задачи на ЭВМ прежде всего следует составить (илииспользовать уже готовую, если аналогичная задача уже решалась на ЭВМ)программу, реализующую выбранный метод решения.

6.  Решение задачи на ЭВМ. Вся необходимая информация длярешения задачи на ЭВМ вводится в память машины вместе с программой. Всоответствии с программой решения ЭВМ производит необходимую обработку введенной числовой информации, получает соответствующие результаты, которыевыдает человеку в удобной для него форме.

7.  Анализ полученного решения. Анализ решения бывает двух видов: формальный(математический), когда проверяется соответствие полученного решенияпостроенной математической модели (в случае несоответствия проверяютсяпрограмма, исходные данные, работа ЭВМ и т.д.), и содержательный(экономический, технологический и т.п.), когда проверяется соответствиеполученного решения тому объекту, который моделировался. В результате такогоанализа в модель могут быть внесены изменения или уточнения, после чего весьразобранный процесс повторяется. Модель считается построенной и завершенной,если она с достаточной точностью характеризует деятельность объекта повыбранному критерию. Только после этого модель может быть использована длярасчета.

Методрешения задачи

Симплексный метод былразработан известным американским математиком Дж. Данцигом и в настоящее времястал универсальным методом решения задач линейного программирования. Алгоритмметода состоит из ряда шагов.

1.  При решении задачи симплекс методомнеобходимо систему уравнений привести к виду, когда какие-либо r переменные (базисные) выражены черезостальные (небазисные), причем свободные члены этих выражений должны бытьнеотрицательными.

Пусть для определенности X1, X2, X3… Xr выражены через остальные переменные Xr+1, Xr+2, Xr+3,… Xn.

Система ограниченийпринимает вид:

 

/> ( 1 )

где />

Базис (X1, X2, X3… Xr) обозначим через Б. Пусть все небазисные переменные равны нулю:

/>.

Найдем из системы ( 1 )значение базисных переменных :

/>

В результате получаембазисное решение/> соответствующеебазису Б .

Целевая функция F ( X1, ...., Xn) также выражается через небазисные переменные :

/>/>

Замечаем, что значениецелевой функции, соответствующее базисному решению, равно :/> C0: FБ = C0.

2.  Следующим шагом алгоритма являетсяпроверка достижения оптимума. Если оптимум не достигнут, то из базиса Будаляется одна из переменных в небазисные, а вместо нее из числа прежнихнебазисных переменных вводится новая. Получаем новый базис Б’ .

С новым базисом поступаемтак же в соответствии с содержанием шагов 1 и 2. Если в результате этогооптимум не достигнут, то все шаги повторяем снова, причем каждый новый шагзаключается в переходе от базиса Б к новому базису Б’, такому, чтозначение Fб уменьшается или, по крайней мере, не увеличивается:Fb’< 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 переменные X3 X4 X5 могут уменьшатся, и необходимоследить за тем, чтобы ни одна из них не стала отрицательной. Так как увеличениеX1ведет к увеличению X3, то для этой переменной такой опасности не существует. Изанализа других базисных переменных получаем, что значение X1 может быть увеличено до 2. Такое увеличение даст X4=0, X3=6, X5=3. Этот результат нас устраивает, так как числоположительных переменных такое же, как и решение. Новый базис Б’состоит из X1, X3, X5. Чтобы приступить к выполнению следующего шага, выразим этипеременные и целевую функцию Fчерез небазисные переменные X2 и X4. Это легко сделать, если решить второе уравнениеотносительно новой базисной переменной X1, а подстановка этого выражения в остальные уравнения ицелевую функцию F дает:

/>

Коэффициент при X2 функции F отрицателен. Поэтому можно и дальше уменьшать целевую функцию F, увеличивая X2.однако X2 можно увеличивать не более, чем до1: это следует из уравнения X5=3-3 X2+ X4 ( если X2>1, X4=0, то X5<0 ). Подстановка X2=1 в другие уравнения дает X1=4 и X3 =9. Еще раз выразим базисныепеременные и F через небазисные:

/>

Базис Б’’состоит из переменных 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

Заметим, что :

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 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

Мы достигли оптимальногорешения./>

Алгоритм программы

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 ' строки

Const n = 7 ' столбцы

Private p, f,xn(r), fm

Private x(r,n)

Private SubbtnExit_Click()

'процедура выхода изпограммы

End

btnExit.Caption =«Готово»

End Sub

' присвоение значенийпеременным

i = 0

u = 1

' распределение данных построкам и столбцам

1: While u<= n

If f(u) < 0And i = 0 Then

i = u

End If

If f(u) = 0Then

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) = iThen 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) = iThen jt = x(j, 0)

Next j

s = s +xn(k)(i) * jt

txtControl.Text= txtControl.Text & Str(xn(k)(i)) & "*" & Str(jt)

If i < nThen 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 + 1To n

If f(j) < 0And 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 + 1To r

If x(j, jr)> 0 Then

d = x(j, 0) /x(j, jr)

If Min > dThen

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 SubForm_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 SubgrdData_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 SubgrdData_KeyPress(KeyAscii As Integer)

If (KeyAscii>= 48 And KeyAscii <= 57 And grdData.Col = 0) Then

IfChr(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 SubcmdIn_Click()

frmFlash.Show

cmdIn.Visible= False

cmdIninf.Visible= True

End Sub

Private SubcmdIninf_Click()

Dim i

For i = 0 To 4

IfText1(i).Text = "" Then Text1(i).Text = 0

pv(i) = CSng(Text1(i).Text)

Next

For i = 0 To 7

IfText2(i).Text = "" Then Text2(i).Text = 0

fmMin(i) =CSng(Text2(i).Text)

Next

For i = 0 To 7

IfText3(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

IfText5(i).Text = "" Then Text5(i).Text = 0

Ar(3, i) =CSng(Text5(i).Text)

Next

For i = 0 To 7

IfText6(i).Text = "" Then Text6(i).Text = 0

Ar(4, i) =CSng(Text6(i).Text)

Next

For i = 0 To 7

IfText7(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г