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

Математическая модель задачи имеет вид:

 

W ’ = 9* х₁ + 8* х₂ + 10* х₃ → max

251 – 0,22* х₁ - 0,21*х₂ - 0,31*х₃ ≥ 0

301 - 0,17* х₁ - 0,15*х₂ - 0,12*х₃ ≥ 0

321 - 0,25*х₁ - 0,20*х₂ - 0,15* х₃ ≥ 0

 

Для упрощения расчетов ограничения (1.1) заменяем условием неотрицательных переменных: х₁ ≥ 0; х₂ ≥ 0; х₃ ≥ 0.

Перейдем к минимизации целевой функции W ’, изменив знаки всех ее коэффициентов на противоположные, и к ограничениям в виде равенств, введя дополнительные переменные:

 

W = -9* х₁ - 8* х₂ - 10* х₃ → min

y₁ = 251 - 0,22* х₁ - 0,21*х₂ - 0,31*х₃;

y₂ = 301 - 0,17* х₁ - 0,15*х₂ - 0,12*х₃;

y₃ = 321 – 0,25*х₁ - 0,20*х₂ - 0,15* х₃;

 

где х_1, х_2, х_3, y_1, y_2, y₃ – неотрицательны.

 

Сведем к задаче линейного программирования:

 

W = 0 - (9* х₁ + 8* х₂ + 10* х₃); (1.7)

y₁ = 251 – (0,22* х₁ + 0,21*х₂ + 0,31*х₃);

y₂ = 301 – (0,17* х₁ + 0,15*х₂ + 0,12*х₃); (1.8)

y₃ = 321– (0,25*х₁ + 0,20*х₂ + 0,15* х₃);

Составим таблицу, состоящую из коэффициентов целевой функции (1.7) и системы ограничений (1.8).

 

Таблица 2

 

Базисная переменная	Свободный член	Свободные переменные
х1	х2	х3
y1		0,22	0,21	0,31
y2		0,17	0,15	0,12
y3		0,25	0,20	0,15
W

 

В качестве разрешающего столбца выбираем х₂. В столбце найдем разрешающий элемент путем сравнения соотношений 251/0,21; 301/0,15; 321/0,20.

 

Наименьшее из соотношений (251/0,21 = 1195) будет определять разрешающий элемент. Им будет элемент 0,21 находящийся на пересечении столбца х₂ и строки y₁. Этот элемент обводится.

 

Затем вычисляем обратную величину разрешающего элемента λ = 1/0,21 = 4,76 и записывают её в нижней части той же ячейки, в которой находится разрешающий элемент. Все элементы разрешающей строки умножаем на λ. Затем все элементы разрешающей графы умножают на (-λ), результаты записываются в нижней части соответствующих ячеек.

 

Подчеркивают в разрешающей строке все верхние числа (251, 0,22, 0,31), а в разрешающей графе – все нижние числа (-0,72, -0.95, -38.10) за исключением λ. Для каждого из элементов, не принадлежащих ни к разрешающей строке, ни к разрешающей графе, записывают в нижней части соответствующей ячейки произведения подчеркнутых чисел, стоящих в той же строке и в той же графе, что и данный элемент.

 

Таблица 3

 

Базисная переменная	Свободный член	Свободные переменные
х1	x2	х3
Y1	251	0,22   1,05	0,21   4,76	0,31   1,48
Y2	-180,72	0,17   -0,16	0,15   -0,72	0,12   -0,22
Y3	-238,45	0,25   -0,21	0,20   -0,95	0,15   -0,30
W	-9563,1	-8,38	-38,10	-11,81

 

Переписываем таблицу, поменяв местами свободную переменную х₂ и базисную Y₁, а элементы разрешающей строки и разрешающей графы меняют на числа, стоящие в нижних частях соответствующих ячеек, каждый из остальных элементов – на сумму чисел, стоящих в верхней и нижних частях той же ячейки.

Так как в строке W есть положительный элемент 0,619, то оптимальное решение еще не получено и решение продолжается в вышеизложенной последовательности, начиная с отыскания разрешающего элемента, разрешающим элементом будет 1,05, обмениваемые переменные x1 и x2. Промежуточные расчеты приведены в таблице 4.

 

Таблица 4

 

Базисная переменная	Свободный член	Свободные переменные
x1	y1	х3
X2	1195	1,05 0.95	4,76 4.52	1,48 1.41
Y2	120,28   -10.75	0,01   -0.009	-0.72   -0.043	-0.1   -0,013
Y3	82,55   -45.41	0,04   -0.038	-0.95   -0,18	-0.15   -0,056
W	-9563,1   -705	0,62   -0.59	-38.10   -2.80	-1.81   -0.873

 

Заключительная таблица имеет вид:

Таблица 5

 

Базисная переменная	Свободный член	Свободные переменные
Х2	Y1	х3
X1		0,95	4,52	1,41
y2	109,53	-0,009	-0,76	-0,11
y3	37,14	-0,038	-1,13	-0,206
W	-10268	-0,59	-40,9	-2,68

 

Так как в строке W все элементы отрицательны, то оптимальное решение получено и имеет вид: x₂ = y₁ = х₃ = 0, х₁ = 1135

Значение целевой функции определим подстановкой найденных значений переменных в выражение (1.6):

W’ = 9* 1135 + 8*0 + 10* 0 = 10215 рублей.

 

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

 

Решение задачи с использованием ПК

 

Для решения задачи используем программу «Excel».

В качестве управляемых переменных принимаем объем выпуска продукции каждым предприятием - х₁(А1); х₂(В1); х₃(С1).

В пустые ячейки (А1, В1, С1) заносим три нуля.

В пустую ячейку (Е4) записываем целевую функцию W=9* х₁ + 8*х₂ + 10*х_3.

Ряд ограничений: (E1) 0,22* х₁ + 0,21*х₂ + 0,31*х3,

(E2) 0,17* х₁ + 0,15*х₂ + 0,12*х₃,

(E3) 0,25*х₁ + 0,20*х₂ + 0,15* х₃ .

 

	A	B	C	D	E
	Управляемые переменные
	х1	х2	х3
					=0,22* А1 + 0,21*В1 + 0,31*С1
					=0,17* А1 + 0,15*В1 + 0,12*С1
					=0,25*А1 + 0,20*В1 + 0,15*С1
					=9* А1 + 8*В1+ 10*С1

 

Далее поиск решения.

Устанавливаем целевую ячейку: E4 и приравниваем её к максимальному значению.

Изменяемые ячейки: A1, B1, C1.

Ограничения: E1 ≥ 0; E2 ≥ 0; E3 ≥ 0;

E1 ≤ 251; E2 ≤ 301; E3 ≤ 321.

А1 ≥ 151; B2 ≥ 201; C3 ≥ 401.

 

Вывод данных:

 

	A	B	C	D	E
	Управляемые переменные
	х1	х2	х3
					143.55
					196.35

 

Получаем х₁ = 384; х₂ = 201; х₃ = 401. Прибыль составила W = 9074

 

Вывод: Полученные значения прибыли в обоих случаях различаются. Решение задачи на ПК позволяет не только облегчить задачу, но и получить более точные результаты.

 

 

ОПТИМИЗАЦИЯ ПЕРЕВОЗОК

 

Исходные данные

Имеется 3 пункта, производящих некоторую продукцию. Затраты на производство единицы продукции в i -ом пункте равна ai, а максимально возможный объем её выпуска составляет bi единиц в год, i = 1,2,3. Изготовляемая продукция должна быть распределена между потребителями. Доставка единицы продукции от i -го пункта производства к j -му потребителю обходится в cij руб., j = 1,2..n. Потребитель в продукции для i -го потребителя составляет dj единиц в год. Требуется составить схему перевозок так, чтобы годовые затраты на производство и перевозку были минимальны.

 

с₁₁ = 4, с₁₂ =10, с₁₃ =8,

с₂₁ = 5, с₂₂ =4, с₂₃ =4,

с₃₁ = 5, с₃₂ =10, с₃₃ =7,

а₁ = 11, а₂ = 11, а₃ = 3,