Контрольная работа: Решение задач симплекс-методом

Виды используемого сырья условно обозначены через М1, М2, М3; содер­жание питательных веществ в сырье и готовом продукте обозначены П1, П2, П3, П3.

Исходные условия задачи выражаются неравенствами:

1х1 + 1х2 + 0х3 ≥ 50

4х1 + 1х2 + 3х3 ≥ 140

1х1 + 4х2 + 1х3 ≥ 127

0х1 + 3х2 + 2х3 ≥ 80

F = 8х1 + 12х2 + 10х3 = min

Умножив обе части неравенств на -1, получим систему с другим направле­нием знака неравенств:

-1х1 - 1х2 - 0х3 ≥ -50

-4х1 - 1х2 - 3х3 ≥ -140

-1х1 - 4х2 - 1х3 ≥ -127

0х1 - 3х2 - 2х3 ≥ -80

F = 8х1 + 12х2 + 10х3 = min

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

-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
			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-я итерация

cj	p0	x0	18	15	24	0	0	0	0
			x1	х2	х3	х4	х5	х6	х7
0	х4	-15	0	-0.75	0.75	1	-0.25	0	0
8	х1	35	1	0.25	0.75	0	-0.25	0	0
0	х6	-92	0	-3.75	-0.25	0	-0.25	1	0
0	х7	-80	0	-3	-2	0	0	0	1
Zj - Cj		280	0	-10	-4	0	-2	0	0

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

2-я итерация

cj	p0	x0	x1	х2	х3	х4	х5	х6	х7
0	х4	3.4	0	0	0.8	1	-0.2	-0.2	0
8	х1	28.9	1.0	0.0	0.7	0.0	-0.3	0.1	0.0
15	х2	24.5	0.0	1.0	0.1	0.0	0.1	-0.3	0.0
0	х7	-6.4	0.0	0.0	-1.8	0.0	0.2	-0.8	1.0
Zj - Cj		525.3	0.0	0.0	-3.3	0.0	-1.3	-2.7	0.0

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

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

3-я итерация

cj	p0	x0	x1	х2	х3	х4	х5	х6	х7
0	х4	0.6	0.0	0.0	0.0	1.0	-0.1	-0.6	0.4
8	х1	26.3	1.0	0.0	0.0	0.0	-0.2	-0.3	0.4
15	х2	24.3	0.0	1.0	0.0	0.0	0.1	-0.3	0.0
10	х3	3.6	0.0	0.0	1.0	0.0	-0.1	0.4	-0.6
Zj - Cj		537.2	0.0	0.0	0.0	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