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

Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).

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

-16x1-6x2+32x3≤-48

-8x1+3x2+16x3=96

-8x1+5x2+8x3≤16

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.

-16x1-6x2 + 32x3 + 1x4 + 0x5 = -48

-8x1 + 3x2 + 16x3 + 0x4 + 0x5 = 96

-8x1 + 5x2 + 8x3 + 0x4 + 1x5 = 16

Введем искусственные переменные x: в 2-м равенстве вводим переменную x6;

-16x1-6x2 + 32x3 + 1x4 + 0x5 + 0x6 = -48

-8x1 + 3x2 + 16x3 + 0x4 + 0x5 + 1x6 = 96

-8x1 + 5x2 + 8x3 + 0x4 + 1x5 + 0x6 = 16

Для постановки задачи на минимум целевую функцию запишем так:

F(X) = x1+48x2+16x3+Mx6 => min

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

x6 = 96+8x1-3x2-16x3

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

F(X) = (1+8M)x1+(48-3M)x2+(16-16M)x3+(96M) => min

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

EQ A = \b\bc\| (\a \al \co6 \hs3 (-16;-6;32;1;0;0;-8;3;16;0;0;1;-8;5;8;0;1;0))

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

x4, x6, x5,

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

X1 = (0,0,0,-48,16,96)


Базис

В

x1

x2

x3

x4

x5

x6

x4

-48

-16

-6

32

1

0

0

x6

96

-8

3

16

0

0

1

x5

16

-8

5

8

0

1

0

F(X0)

96M

-1-8M

-48+3M

-16+16M

0

0

0

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-6).


Базис

В

x1

x2

x3

x4

x5

x6

x4

-48

-16

-6

32

1

0

0

x6

96

-8

3

16

0

0

1

x5

16

-8

5

8

0

1

0

F(X0)

96M

-1-8M

-48+3M

-16+16M

0

0

0

θ

0







-

-

-

-

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




Базис

В

x1

x2

x3

x4

x5

x6

x2

8

2.67

1

-5.33

-0.17

0

0

x6

72

-16

0

32

0.5

0

1

x5

-24

-21.33

0

34.67

0.83

1

0

F(X0)

384+72M

127-16M

0

-272+32M

-8+0.5M

0

0

План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-21.33).


Базис

В

x1

x2

x3

x4

x5

x6

x2

8

2.67

1

-5.33

-0.17

0

0

x6

72

-16

0

32

0.5

0

1

x5

-24

-21.33

0

34.67

0.83

1

0

F(X1)

384+72M

127-16M

0

-272+32M

-8+0.5M

0

0

θ

0




-

-

-

-

-

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




Базис

В

x1

x2

x3

x4

x5

x6

x2

5

0

1

-1

-0.0625

0.12

0

x6

90

0

0

6

-0.12

-0.75

1

x1

1.13

1

0

-1.62

-0.0391

-0.0469

0

F(X1)

241.12+90M

0

0

-65.63+6M

-3.04-0.12M

5.95-0.75M

0

В базисном столбце все элементы положительные.

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

Итерация №0.

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

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

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

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

EQ min\b\bc\[ (- , \f(90;6) , - ) = 15

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

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




Базис

В

x1

x2

x3

x4

x5

x6

min

x2

5

0

1

-1

-0.0625

0.12

0

0

x6

90

0

0

6

-0.12

-0.75

1

15

x1

1.13

1

0

-1.62

-0.0391

-0.0469

0

0

F(X1)

241.12+90M

0

0

-65.63+6M

-3.04-0.12M

5.95-0.75M

0

0

После преобразований получаем новую таблицу:




Базис

В

x1

x2

x3

x4

x5

x6

x2

20

0

1

0

-0.0833

0

0.17

x3

15

0

0

1

-0.0208

-0.12

0.17

x1

25.5

1

0

0

-0.0729

-0.25

0.27

F(X1)

1225.5

0

0

0

-4.41

-2.25

10.94-1M

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

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


Базис

В

x1

x2

x3

x4

x5

x6

x2

20

0

1

0

-0.0833

0

0.17

x3

15

0

0

1

-0.0208

-0.12

0.17

x1

25.5

1

0

0

-0.0729

-0.25

0.27

F(X2)

1225.5

0

0

0

-4.41

-2.25

10.94-1M

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

x2 = 20

x3 = 15

x1 = 25.5

F(X) = 1*25.5 + 48*20 + 16*15 = 1225.5


Решение было получено и оформлено с помощью сервиса:

Двойственный симплекс-метод

Вместе с этой задачей решают также:



Графический метод решения задач линейного программирования

Симплекс-метод

Двойственная задача линейного программирования

Метод Гомори

Транспортная задач
скачать файл



Смотрите также:
Решим прямую задачу линейного программирования двойственным симплексным методом, с использованием симплексной таблицы
116.57kb.
1. Графический метод решения задач линейного программирования
35.2kb.
«Основы программирования» учащимися 7-х классов в течение 34 часов (1 час в неделю). Учащиеся приобретают знания и умения по составлению программ, используя современные профессиональные языки программирования
71.86kb.
Расчет размерных цепей
103.16kb.
Практика вычисления составляющих уклонений отвеса методом численного интегрирования
15.48kb.
Что такое язык программирования
166.01kb.
Класс: 9 класс Формируемая компетентность: компетентность разрешения проблем
28.02kb.
Основы системного программирования
67.32kb.
Лекция 3 Инструментальное по
89.7kb.
Задача Составить математическую модель, решить задачу симплекс-методом
20.34kb.
4. Требования к абитуриенту. Абитуриент должен иметь документ государственного образца о высшем профессиональном образовании
33.97kb.
Электронные таблицы могут содержать большие группы данных, требующие некоторого обобщения и анализа
56.78kb.