Главная страница

Мат моделирование. Способ подстановки Метод преобразования таблицы с разрешающим элементом


Скачать 44.79 Kb.
НазваниеСпособ подстановки Метод преобразования таблицы с разрешающим элементом
Дата16.01.2022
Размер44.79 Kb.
Формат файлаdocx
Имя файлаМат моделирование.docx
ТипДокументы
#332099

Задание 1



Способ подстановки





Метод преобразования таблицы с разрешающим элементом




x1

x2

x3

3

1

1

-3

0

1

2

3

2

3

0

1







3

x2

x3

x1

1

-1

3

0

1

1

6

2

3

-3

10







3

0

x3

x1

2

-1

9

x2

-1

1

-6

2

6

-3

28







3

0

x3

x1

2

-1

9

x2

-1

1

-6

2

6

-3

28







3

0

1/14

x1

1/14

-19/14

9

x2

2/7

19/14

-6

x3

-3/14

3/28

1



Метод ноль таблиц




x1

x2

x3

1

0

1

1

-3

-3

0

1

2

3

0

0

3

0

1

-2







0

x2

x3

1

x1

1

-1

3

3

0

1

1

6

3

0

3

-3

10

7







0

x3

1

x1

-1

9

6

0

1

-6

-3

0

-3

28

16







0

1

x1

9




x2

-6




0

1










x3

1

x1

3

24/28

x2

9

12/28

0

28

-16/28




1







x1

6/7







x2

3/7







0

-14/7








Метод Гаусса

Запишем систему в виде расширенной матрицы:
Умножим 2-ю строку на (-1). Добавим 2-ю строку к 1-й:
Умножим 2-ю строку на (3). Умножим 3-ю строку на (-1). Добавим 3-ю строку к 2-й:
Умножим 1-ю строку на (6). Добавим 2-ю строку к 1-й:
Теперь исходную систему можно записать так:

x3 = 16/(-28)

x2 = [-2 - (8x3)]/6

x1 = [2 - (x3)]/3


Задание 2

Чтобы обеспечить сбалансированное питание для собак в питомнике, корм готовится из смеси трех зерновых круп. Соответствующие данные приведены в таблице.

Крупа

Стоимость 1 кг. крупы в руб.

Белки

%, в 1 кг крупы

Углеводы

%, в 1 кг крупы

Жиры

%, в 1 кг крупы

В

34

40

8

6

С

42

38

16

4

D

52

32

32

2


Каждая собака должна употребляла ежедневно не менее 580 г. белков, 170 г. углеводов и не более 80 г. жиров. Сколько каждой крупы должна получать собака, чтобы минимизировать затраты?
Пусть х1, х2, х3 количество круп В, С, D.

Составим математическую модель задачи


Расширенная матрица системы ограничений-равенств данной задачи:
Приведем систему к единичной матрице методом жордановских преобразований.

1. В качестве базовой переменной можно выбрать x4.

Получаем новую матрицу:

-2/5

-0.38

-0.32

1

0

-580

2/25

0.16

0.32

0

0

170

3/50

1/25

1/50

0

1

80


2. В качестве базовой переменной можно выбрать x5.

3. В качестве базовой переменной можно выбрать x3.

Разрешающий элемент РЭ=0.32. Строка, соответствующая переменной x2, получена в результате деления всех элементов строки x3 на разрешающий элемент РЭ=0.32. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули.

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

Представим расчет каждого элемента в виде таблицы:

0

-0.38

-0.32

1

0

-580

0

0.16

0.32

0

0

170

0

0

0

0

1

80



Получаем новую матрицу:

-0.32

-0.22

0

1

0

-410

1/4

0.5

1

0

0

531.25

11/200

0.03

0

0

1

69.375


Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,3,5).

Соответствующие уравнения имеют вид:

-0.32x1-0.22x2+x4 = -410

1/4x1+0.5x2+x3 = 531.25

11/200x1+0.03x2+x5 = 69.375

Выразим базисные переменные через остальные:

x4 = 0.32x1+0.22x2-410

x3 = -1/4x1-0.5x2+531.25

x5 = -11/200x1-0.03x2+69.375

Подставим их в целевую функцию:

F(X) = 34x1+42x2+52(-1/4x1-0.5x2+531.25)

или

F(X) = 21x1+16x2+27625 → min

Система неравенств:

0.32x1+0.22x2-410 ≥ 0

-1/4x1-0.5x2+531.25 ≥ 0

-11/200x1-0.03x2+69.375 ≥ 0

Приводим систему неравенств к следующему виду:

-0.32x1-0.22x2 ≤ -410

1/4x1+0.5x2 ≤ 531.25

11/200x1+0.03x2 ≤ 69.375

F(X) = 21x1+16x2+27625 → min

Упростим систему.

-0.32x1-0.22x2 ≤ -410

x1+2x2 ≤ 2125

11x1+6x2 ≤ 13875

F(X) = 21x1+16x2+27625 → min

Если задача ЛП решается на поиск max-го значения, то стандартная форма будет иметь следующий вид:

0.32x1+0.22x2 ≤ 410

-x1-2x2 ≤ -2125

-11x1-6x2 ≤ -13875

F(X) = -21x1-16x2-27625 → max

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

Поскольку в правой части присутствуют отрицательные значения, умножим соответствующие строки на (-1).

Определим минимальное значение целевой функции F(X) = 21x1+16x2+27625 при следующих условиях-ограничений.

При вычислениях значение Fc = 27625 временно не учитываем.

0.32x1+0.22x2-x4-410=410

1/4x1+0.5x2+x3+531.25=531.25

11/200x1+0.03x2+x5+69.375=69.375

Расширенная матрица системы ограничений-равенств данной задачи:
Приведем систему к единичной матрице методом жордановских преобразований.

1. В качестве базовой переменной можно выбрать x4.

Получаем новую матрицу:

-0.32

-0.22

0

1

0

-410

1/4

0.5

1

0

0

531.25

11/200

0.03

0

0

1

69.375


2. В качестве базовой переменной можно выбрать x3.

3. В качестве базовой переменной можно выбрать x5.

Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,3,5).

Выразим базисные переменные через остальные:

x4 = 0.32x1+0.22x2-410

x3 = -1/4x1-0.5x2+531.25

x5 = -11/200x1-0.03x2+69.375

Подставим их в целевую функцию:

F(X) = 21x1+16x2

Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.

Вместо переменной x4 следует ввести переменную x2.

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис

B

x1

x2

x3

x4

x5

x2

1863.64

1.45

1

0

-4.55

0

x3

-400.57

-0.48

0

1

2.27

0

x5

13.47

0.011

0

0

0.14

1

F(X0)

-29818.18

-2.27

0

0

72.73

0


Представим расчет каждого элемента в виде таблицы:

B

x1

x2

x3

x4

x5

-410

-0.32

-0.22

0

1

0

531.25

0

0.5

1

0

0

69.375

0

0.03

0

0

1


Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.

Вместо переменной x3 следует ввести переменную x1.

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис

B

x1

x2

x3

x4

x5

x2

642.86

0

1

3.05

2.38

0

x1

839.29

1

0

-2.1

-4.76

0

x5

3.93

0

0

0.024

0.19

1

F(X1)

-27910.71

0

0

-4.76

61.9

0


Представим расчет каждого элемента в виде таблицы:

B

x1

x2

x3

x4

x5

1863.636

1.455

1

0

-4.545

0

-400.568

-0.477

0

1

2.273

0

13.466

0.011

0

0

0.136

1


Выразим базисные переменные через остальные:

x2 = -3.05x3-2.38x4+642.857

x1 = 2.1x3+4.76x4+839.286

x5 = -0.024x3-0.19x4+3.929

Подставим их в целевую функцию:

F(X) = 21(2.1x3+4.76x4+839.286)+16(-3.05x3-2.38x4+642.857)+27625

или

F(X) = -4.76x3+61.9x4+55535.714

x2+3.05x3+2.38x4=642.857

x1-2.1x3-4.76x4=839.286

0.024x3+0.19x4+x5=3.929

При вычислениях значение Fc = 55535.714 временно не учитываем.

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

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

X0 = (839.286,642.857,0,0,3.929)

Базис

B

x1

x2

x3

x4

x5

x2

642.86

0

1

3.05

2.38

0

x1

839.29

1

0

-2.1

-4.76

0

x5

3.93

0

0

0.024

0.19

1

F(X0)

0

0

0

4.76

-61.9

0


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

Итерация №0.

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

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

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

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

min (642.857 : 3.048 , - , 3.929 : 0.0238 ) = 165

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

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

Базис

B

x1

x2

x3

x4

x5

min

x2

642.86

0

1

3.05

2.38

0

210.94

x1

839.29

1

0

-2.1

-4.76

0

-

x5

3.93

0

0

0.024

0.19

1

165

F(X1)

0

0

0

4.76

-61.9

0

0


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

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

Базис

B

x1

x2

x3

x4

x5

x2

140

0

1

0

-22

-128

x1

1185

1

0

0

12

88

x3

165

0

0

1

8

42

F(X1)

-785.71

0

0

0

-100

-200


Конец итераций: индексная строка не содержит положительных элементов - найден оптимальный план

Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Базис

B

x1

x2

x3

x4

x5

x2

140

0

1

0

-22

-128

x1

1185

1

0

0

12

88

x3

165

0

0

1

8

42

F(X2)

-785.71

0

0

0

-100

-200


Оптимальный план можно записать так:

x1 = 1185, x2 = 140, x3 = 165, x4 = 0, x5 = 0

F(X) = 21*1185 + 16*140 + 52*165 = 54750

Так как масса была указана в граммах, то ответ нужно разделить на 1000

Ответ: x1=1,185кг; x2=0,14 кг; x3=0,165 кг; minF=55руб


написать администратору сайта