Контрольная работа по "Программированию и компьютерам"

Автор работы: Пользователь скрыл имя, 13 Марта 2013 в 07:49, контрольная работа

Описание работы

Задание № 1
Решить задачу линейного программирования с помощью симплекс-метода, построить двойственную задачу и определить ее решение:
F = 11x1+8x2+9x3+10x4 ® max
x1+2x2+3x3+2x4 £ 98
6x1+3x2+2x3+5x4 £ 500
3x1+4x2+5x3+2x4 £ 180
xj ³ 0, i=1,2,3,4.

Скачать архив (57.46 Кб) Сколько стоит заказать работу?

Файлы: 1 файл

ОТЧЕТ.docx

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

Задание № 1

Решить задачу линейного программирования с помощью симплекс-метода, построить двойственную задачу и определить ее решение:

F = 11x₁+8x₂+9x₃+10x₄ ® max

x₁+2x₂+3x₃+2x₄ £ 98

6x₁+3x₂+2x₃+5x₄ £ 500

3x₁+4x₂+5x₃+2x₄ £ 180

x_j ³ 0, i=1,2,3,4.

Составим симплекс таблицу:

Базисные переменные	Свободные члены	x ₁	x ₂	x ₃	x ₄	x ₅	x ₆	x ₇
X₅	98	1	2	3	2	1	0	0
X₆	500	6	3	2	5	0	1	0
X₇	180	3	4	5	2	0	0	1
F	0	-11	-8	-9	-10	0	0	0

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-11). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.

Пересчитаем таблицу

Базис	Свободн.	x ₁	x ₂	x ₃	x ₄	x ₅	x ₆	x ₇
x5	38	0	2/3	4/3	4/3	1	0	-1/3
x6	140	0	-5	-8	1	0	1	-2
x1	60	1	4/3	5/3	2/3	0	0	1/3
F	660	0	20/3	28/3	-8/3	0	0	11/3

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение нjе оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-2.66666666667). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.

Пересчитаем таблицу

Базис	Свободн.	x ₁	x ₂	x ₃	x ₄	x ₅	x ₆	x ₇
x4	57/2	0	1/2	1	1	3/4	0	-1/4
x6	223/2	0	-11/2	-9	0	-3/4	1	-7/4
x1	41	1	1	1	0	-1/2	0	1/2
F	736	0	8	12	0	2	0	3

Найдено оптимальное решение.

Результаты вычислений находятся на странице «Задание 1».

Оптимальным будет решение (41 ,0 ,0 , 57/2)

Задание № 2

Решить транспортную задачу:

Для строительства четырех объектов используется кирпич, изготовляемый
на трех заводах. Ежедневно каждый из заводов может изготовлять 100, 150 и 115 условных единиц кирпича. Ежедневные потребности в кирпиче на каждом из строящихся объектов соответственно равны 75, 80, 90 и 85 условных единиц. Известны также тарифы перевозок 1 усл. е. кирпича с каждого завода к каждому из строящихся объектов:

6 7 3 5

С=1 2 5 6

8 10 20 1

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

найти оптимальный план поставки кирпича.

Транспортная задача— задача об оптимальном плане перевозок продукта(-ов) из пунктов отправления в пункты потребления. Разработка и применение оптимальных схем грузовых потоков позволяют снизить затраты на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной или входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной.

Классическая транспортная задача ЛП формулируется следующим образом.

Имеется m пунктов производства (поставщиков) и n пунктов

потребления (потребителей) однородного продукта. Заданы величины:

- объем производства (запас) i-го поставщика, i=1, m ;
- объем потребления (спрос) j-го потребителя, i=1, n ;
- стоимость перевозки (транспортные затраты) единицы продукта от i-го поставщика к j-му потребителю.

Требуется составить такой план перевозок, при котором спрос всех потребителей был бы выполнен и при этом общая стоимость всех перевозок была бы минимальна.

Математическая модель транспортной задачи имеет вид

Транспортная задача, в которой суммарные запасы и суммарные потребности совпадают, называется закрытой моделью; в противном случае - открытой. Открытая модель решается приведением к закрытой.

Составим модель закрытой транспортной задачи методом «Юго-западного угла»

	объект 1	объект 2	объект 3	объект 4	Объем поставщика
Пост 1	75	25	0	0	100
Пост 2	0	55	90	5	150
Пост 3	0	0	0	80	115
Потребн. Объекта	75	80	90	85	=

Создадим при помощи встроенного в MS Excel редактора VBA подпрограмму для расчета необходимых значений. Код программы находится в Приложении 1.

Результаты вычислений находятся на странице «Задание 4».

После оптимизации получим следующее решение

	объект 1	объект 2	объект 3	объект 4
Пост 1	0	5	90	0
Пост 2	75	75	0	0
Пост 3	0	0	0	85

Задание № 3

Решить задачу безусловной оптимизации методом наискорейшего спуска:

Z = -X₁²- 4*X₂²+ 6*X₁ + 32*X₂®min

X₀=(7, 4)

7- номер варианта

Метод градиентного (наискорейшего) спуска.

В этом методе функция минимизируется по направлению, в котором она быстрее всего убывает, т.е. в направлении, обратном градиенту функции. доль этого направления функция зависит от одной параметрической переменной t, для нахождения минимума которой можно воспользоваться любым известным методом поиска минимума функции одной переменной. Спуск из точки начального приближения против градиента до минимума t определяет новую точку r₁ , в которой вновь определяется градиент и делается следующий спуск. Условием окончания процесса, как и в случае координатного спуска, будет .

Алгоритм

Задаются: xº — начальное приближение, ε1 > 0, ε2> 0, M – предельное число итераций;
Количество итераций n = 0 ;
Вычисляется: gradf(xⁿ);
Вычисляется || gradf(xⁿ) || ;

4.1) если || gradf(xⁿ) || < ε1 , то

x*= xⁿ ;

4.2) если || gradf(xⁿ) || > ε1 , то к 5);

n < M

5.1) если выполняется, то к 6) ;

5.2) если нет, то x*= xⁿ ;

найти минимум функции φ(tn) = f( xⁿ — tn * gradf(xⁿ));
xⁿ ¹ = xⁿ — tn * gradf(xⁿ);
Проверяется условие f(xⁿ ¹ ) — f(xⁿ) < 0

8.1) если выполняется, то к 9) ;

8.2) если нет, то tn= tn / 2 и к 7) ;

Проверяется условие ||xⁿ ¹ – xⁿ ||< ε2 и f(xⁿ ¹ ) — f(xⁿ) < ε2

9.1) если оба условия выполняются, то x*= xⁿ ¹ ;

9.2) если хотя бы одно не выполняется , то n = n+1 и к 3).

Создадим при помощи встроенного в MS Excel редактора VBA подпрограмму для расчета необходимых значений. Код программы находится в Приложении 2.

Результаты вычислений находятся на странице «Задание 3».

Задание № 4

Z = X₁²+ X₂²- Х₁ *X₂ - 3/4*X₂®min

-Х₁- Х₂ + 1 £ 0

Х₁- 2*Х₂ £ 0

-2*Х₁+ Х₂ £ 0

Решим систему неравенств ограничивающую область определения функции

Рассмотрим 2 крайних состояния

Т.о. область определения функции лежит на интервалах

Х₁=[1/3,2/3]

Х₂=[1/3,2/3]

Для этой области, методом координатного спуска определим минимум функции.

Создадим при помощи встроенного в MS Excel редактора VBA подпрограмму для расчета необходимых значений. Код программы находится в Приложении 3.

Результаты вычислений находятся на странице «Задание 4».

Литература

1. Карманов В.Г. Математическое программирование. – М.: ФИЗМАТЛИТ, 2004. – 264 с

2. Коробов П.Н. Математическое программирование и моделирование экономических процессов. – СПб.: ДНК, 2006. – 376 с.

3. Антонов А.В. Системный анализ. – М.: Высшая школа, 2004. – 454 с.

4. Окулов С.М. Основы программирования. – М.: БИНОМ, 2004. – 424 с.: ил.

Приложение 1

Sub resh()

Dim a(3, 4) As Double, b(3, 4) As Double

Dim excluded(3, 4) As Boolean

Dim MinCost As Double

Dim zav

Dim ob

Dim tmpi As Integer, tmpj As Integer

zav = Array(100, 150, 115)

ob = Array(75, 80, 90, 85)

Range("B4").Select

For i = 1 To 3

For j = 1 To 4

excluded(i, j) = False

a(i, j) = CDbl(ActiveCell.Cells(i, j).FormulaR1C1)

Next j

Next i

markcicl:

MinCost = 100

For i = 1 To 3

For j = 1 To 4

If (a(i, j) < MinCost) And Not excluded(i, j) Then

MinCost = a(i, j)

tmpi = i

tmpj = j

End If

Next j

Next i

excluded(tmpi, tmpj) = True

'Удовлетворяем спрос

If zav(tmpi - 1) > 0 Then

If zav(tmpi - 1) > ob(tmpj - 1) Then

zav(tmpi - 1) = zav(tmpi - 1) - ob(tmpj - 1)

b(tmpi, tmpj) = ob(tmpj - 1)

ob(tmpj - 1) = 0

Else

ob(tmpj - 1) = ob(tmpj - 1) - zav(tmpi - 1)

b(tmpi, tmpj) = zav(tmpi - 1)

zav(tmpi - 1) = 0

End If

For i = 0 To 3

If ob(i) <> 0 Then GoTo markcicl

Next i

Макрос1

Range("B10").Select

For i = 1 To 3

For j = 1 To 4

ActiveCell.Cells(i, j).FormulaR1C1 = b(i, j)

Next j

Next i

Макрос3

End Sub

Приложение 2

Function f(x1 As Double, x2 As Double) As Double

f = CDbl(-x1 * x1 - 4 * x2 * x2 + 6 * x1 + 32 * x2)

End Function

Function grad(x1 As Double, x2 As Double, i As Integer) As Double

Dim lx(2) As Double

Dim ly As Double

h = 0.00000001

lx(0) = x1

lx(1) = x2

ly = f(x1, x2)

lx(i) = lx(i) - h

ly = (ly - f(lx(0), lx(1))) / h

grad = ly

End Function

Function opt(pk1 As Double, pk2 As Double, x1 As Double, x2 As Double) As Double

Dim a As Double, b As Double, xp As Double, ll As Double, delta As Double, xk As Double, yk As Double

e = 0.00001

l = 0.0001

t = 1

tk = 0

kk = 1

p = 0

If ((f(x1 - (tk - t) * pk1, x2 - (tk - t) * pk2) >= f(x1 - (tk) * pk1, x2 - (tk) * pk2)) And (f(x1 - (tk + t) * pk1, x2 - (tk + t) * pk2) >= f(x1 - (tk) * pk1, x2 - (tk) * pk2))) Then

a = tk - t

b = tk + t

p = 1

End If

If ((f(x1 - (tk - t) * pk1, x2 - (tk - t) * pk2) <= f(x1 - (tk) * pk1, x2 - (tk) * pk2)) And (f(x1 - (tk + t) * pk1, x2 - (tk + t) * pk2) <= f(x1 - (tk) * pk1, x2 - (tk) * pk2))) Then

Информация о работе Контрольная работа по "Программированию и компьютерам"