Большая База Рефератов - Решение задач симплекс-методом - бесплатно рефераты, скачать рефераты, рефераты на тему

Рефераты. Решение задач симплекс-методом

Преобразуем неравенства в эквивалентные равенства с помощью дополнительных неизвестных. Симплексные уравнения будут следующими:

-50 = -1х1 - 1х2 - 0х3 + 1х4 + 0х5 + 0х6 + 0х7

-140 = -4х1 - 1х2 - 3х3 + 0х4 + 1х5 + 0х6 + 0х7

-127 = -1х1 - 4х2 - 1х3 + 0х4 + 0х5 + 1х6 + 0х7

-80 = 0х1 - 3х2 - 2х3 + 0х4 + 0х5 + 0х6 + 1х7

F = 8х1 + 12х2 + 10х3 + 0х4 + 0х5 + 0х6 + 0х7 = min

Записанные уравнения отличаются от тех, которые нами рассматривались выше, тем, что коэффициенты при основных неизвестных и свободные члены имеют отрицательные знаки.

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

cj	p0	x0	8	12	10	0	0	0	0
cj	p0	x0	x1	х2	х3	х4	х5	х6	х7
0	х4	-50	-1	-1	0	1	0	0	0
0	х5	-140	-4	-1	-3	0	1	0	0
0	х6	-127	-1	-4	-1	0	0	1	0
0	х7	-80	0	-3	-2	0	0	0	1
Zj - Cj		0	-8	-12	-10	0	0	0	0

Элементы целевой строки рассчитывают по обычным правилам и получают отрицательные знаки.

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

В итоговом столбце свободные числа имеют отрицательные знаки. Это является свидетельством того, что данный план нельзя считать допустимым, так как он противоречит экономическому смыслу. План можно считать допустимым только тогда, когда в итоговом столбце не будет отрицательных чисел.

Ликвидация отрицательных чисел в итоговом столбце начинается с наибольшего по абсолютной величине. В нашем примере таким числом является (-140). Строка х5, в которой находится это число, принимается за ключевую и соответственно выделяется.

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

Столбцы х1, х2, х3 будут иметь следующие отношения:

Наименьшее отношение имеет столбец х1, он и будет являться ключевым.

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

1-я итерация

х2

х3

х4

х5

х6

х7

х4

-15

-0.75

0.75

-0.25

х1

0.25

0.75

-0.25

х6

-92

-3.75

-0.25

х7

-80

-3

-2

Zj - Cj

280

-10

-4

-2

После преобразования элементов в итоговом столбце осталось еще три отрицательных числа в строке х4, х6 и х7. Наибольшим по абсолютной величине является число в строке х6. Эта строка будет принята за ключевую для последующего расчета. Ключевой столбец определяется по наименьшему отношению элементов целевой строки к элементам ключевой строки. Им будет столбец х2. Вводим этот вид сырья в программу вместо неизвестного х6. По общим правилам преобразуем элементы матрицы.

2-я итерация

х2

х3

х4

х5

х6

х7

х4

3.4

0.8

-0.2

х1

28.9

1.0

0.0

0.7

0.0

-0.3

0.1

0.0

х2

24.5

0.0

1.0

0.1

0.0

0.1

-0.3

0.0

х7

-6.4

0.0

-1.8

0.0

0.2

-0.8

1.0

Zj - Cj

525.3

0.0

-3.3

0.0

-1.3

-2.7

0.0

После преобразования элементов в итоговом столбце осталось еще одно отрицательное число в строке х7. Эта строка будет принята за ключевую для последующего расчета. Ключевой столбец определяется по наименьшему отношению элементов целевой строки к элементам ключевой строки. Им будет столбец х3. Вводим этот вид сырья в программу вместо неизвестного х7. По общим правилам преобразуем элементы матрицы.

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

3-я итерация

х2

х3

х4

х5

х6

х7

х4

0.6

0.0

1.0

-0.1

-0.6

0.4

х1

26.3

1.0

0.0

-0.2

-0.3

0.4

х2

24.3

0.0

1.0

0.0

0.1

-0.3

0.0

х3

3.6

0.0

1.0

0.0

-0.1

0.4

-0.6

Zj - Cj

537.2

0.0

-1.7

-1.2

-1.9

Подставив значения неизвестных в исходные неравенства, получаем:

1 * 26,3 + 1 * 24,3 + 0 * 3,6 ≥ 50

4 * 26,3 + 1 * 24,3 + 3 * 3,6 ≥ 140

1 * 26,3 + 4 * 24,3 + 1 * 3,6 ≥ 127

0 * 26,3 + 3 * 24,3 + 2 * 3,6 ≥ 80

Стоимость сырья при этом будет минимальной и составит:

F = 8 * 26,3 + 12 * 24,3 + 12 * 3,6 = 537,2

ЗАДАЧА 3

Составить оптимальный план перевозок пищевых продуктов от 4-х поставщиков к 6-ти потребителям. Поставщики (П), потребители (М), объемы вывоза и завоза, кратчайшие расстояния между пунктами вывоза и завоз приведены в таблице.

Поставщики	Потребители						Объемы вывоза, т
Поставщики	М1	М2	М3	М4	М5	М6	Объемы вывоза, т
П1	24	30	42	15	39	21	144
П2	9	24	30	33	27	29	148
П3	24	22	20	45	21	23	76
П4	11	36	27	40	30	8	132
Объемы завоза, т	92	84	80	112	96	36

Страницы: 1, 2, 3, 4, 5