Контрольная работа по "Методам оптимальных решений"

Автор работы: Пользователь скрыл имя, 28 Ноября 2013 в 22:03, контрольная работа

Краткое описание

Задача № 1. Решить задачу графически и симплекс-методом.
Задача № 2. Цех выпускает три вида столярных изделий с использованием трёх видов сырья, расход которого на единицу каждого вида изделий приведён в таблице. Запасы сырья каждого вида на планируемый период составляют 200, 320 и 400 единиц соответственно. План выпуска изделий каждого вида за этот период составляет 10, 20, 15 единиц. Сколько единиц изделий каждого вида необходимо выпускать для получения максимальной прибыли и выполнения плана, если прибыль, получаемая от реализации одного изделия каждого вида, составляет 6 у.е., 12 у.е. и 15 у.е.

Прикрепленные файлы: 1 файл

математика методы оптимизации вариант 9.doc

— 465.00 Кб (Скачать документ)

Из уравнений выражаем искусственные переменные:

x10 = 10-x1+x7

x11 = 20-x2+x8

x12 = 15-x3+x9

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

F(X) = 6x1 + 12x2 + 15x3 - M(10-x1+x7) - M(20-x2+x8) - M(15-x3+x9) → max

или

F(X) = (6+M)x1+(12+M)x2+(15+M)x3+(-M)x7+(-M)x8+(-M)x9+(-45M) → max

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

5

2

3

1

0

0

0

0

0

0

0

0

1

6

8

0

1

0

0

0

0

0

0

0

4

5

10

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

-1

0

0

1

0

0

0

1

0

0

0

0

0

-1

0

0

1

0

0

0

1

0

0

0

0

0

-1

0

0

1


 

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений  и притом с единичным коэффициентом.

Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

Решим систему уравнений относительно базисных переменных:

x4, x5, x6, x10, x11, x12,

Полагая, что свободные  переменные равны 0, получим первый опорный план:

X1 = (0,0,0,200,320,400,0,0,0,10,20,15)

Базисное решение называется допустимым, если оно неотрицательно.

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

x12

x4

200

5

2

3

1

0

0

0

0

0

0

0

0

x5

320

1

6

8

0

1

0

0

0

0

0

0

0

x6

400

4

5

10

0

0

1

0

0

0

0

0

0

x10

10

1

0

0

0

0

0

-1

0

0

1

0

0

x11

20

0

1

0

0

0

0

0

-1

0

0

1

0

x12

15

0

0

1

0

0

0

0

0

-1

0

0

1

F(X0)

-45M

-6-M

-12-M

-15-M

0

0

0

M

M

M

0

0

0


 

Переходим к основному  алгоритму симплекс-метода.

1. Проверка критерия  оптимальности.

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

2. Определение новой  базисной переменной.

В качестве ведущего выберем  столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.

3. Определение новой  свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai3

и из них выберем наименьшее:

min (200 : 3 , 320 : 8 , 400 : 10 , - , - , 15 : 1 ) = 15

Следовательно, 6-ая строка является ведущей.

Разрешающий элемент  равен (1) и находится на пересечении  ведущего столбца и ведущей строки.

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

x12

min

x4

200

5

2

3

1

0

0

0

0

0

0

0

0

662/3

x5

320

1

6

8

0

1

0

0

0

0

0

0

0

40

x6

400

4

5

10

0

0

1

0

0

0

0

0

0

40

x10

10

1

0

0

0

0

0

-1

0

0

1

0

0

-

x11

20

0

1

0

0

0

0

0

-1

0

0

1

0

-

x12

15

0

0

1

0

0

0

0

0

-1

0

0

1

15

F(X1)

-45M

-6-M

-12-M

-15-M

0

0

0

M

M

M

0

0

0

0


 

4. Пересчет симплекс-таблицы.

Формируем следующую  часть симплексной таблицы.

Вместо переменной x12 в план 1 войдет переменная x3.

Строка, соответствующая  переменной x3 в плане 1, получена в результате деления всех элементов строки x12 плана 0 на разрешающий элемент РЭ=1

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках  столбца x3 плана 1 записываем нули.

Таким образом, в новом  плане 1 заполнены строка x3 и столбец x3.

Все остальные элементы нового плана 1, включая элементы индексной  строки, определяются по правилу прямоугольника.

Получаем новую симплекс-таблицу:

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

x12

x4

155

5

2

0

1

0

0

0

0

3

0

0

-3

x5

200

1

6

0

0

1

0

0

0

8

0

0

-8

x6

250

4

5

0

0

0

1

0

0

10

0

0

-10

x10

10

1

0

0

0

0

0

-1

0

0

1

0

0

x11

20

0

1

0

0

0

0

0

-1

0

0

1

0

x3

15

0

0

1

0

0

0

0

0

-1

0

0

1

F(X1)

225-30M

-6-M

-12-M

0

0

0

0

M

M

-15

0

0

15+M


 

1. Проверка критерия  оптимальности.

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

2. Определение новой базисной  переменной.

В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.

3. Определение новой свободной  переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai2

и из них выберем наименьшее:

min (155 : 2 , 200 : 6 , 250 : 5 , - , 20 : 1 , - ) = 20

Следовательно, 5-ая строка является ведущей.

Разрешающий элемент  равен (1) и находится на пересечении  ведущего столбца и ведущей строки.

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

x12

min

x4

155

5

2

0

1

0

0

0

0

3

0

0

-3

771/2

x5

200

1

6

0

0

1

0

0

0

8

0

0

-8

331/3

x6

250

4

5

0

0

0

1

0

0

10

0

0

-10

50

x10

10

1

0

0

0

0

0

-1

0

0

1

0

0

-

x11

20

0

1

0

0

0

0

0

-1

0

0

1

0

20

x3

15

0

0

1

0

0

0

0

0

-1

0

0

1

-

F(X2)

225-30M

-6-M

-12-M

0

0

0

0

M

M

-15

0

0

15+M

0

Информация о работе Контрольная работа по "Методам оптимальных решений"