шаг - выбор метода решения задачи

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

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

Неравенства (81) преобразуем в равенства введением дополнительных переменных y ₁, y ₂, y ₃, которые представляют собой неиспользуемые заводом средства

16 х₁ + 25 х₂ + y₁ = 3200,

0,2 х₁+0,15 х₂ + y₂ = 30,

75 х₁ + 80 х₂ + y₃ = 12025. (83)

Неотрицательность введенных переменных параметров можно установить из уравнений (83) при х₁ = 0, х₂ = 0

у₁ ≥ 0, у₂ ≥ 0, у₃ ≥ 0. (84)

В результате, ценой увеличения числа переменных, мы пришли к канонической задаче со стандартными условиями в виде уравнений (83), в которых

а₁₁=16; a₁₂=25, a₁₃=1, b₁=3200,

a₂₁=0,2, a₂₂=0,15 a₂₃=1, b₂ = 30,

a₃₁=75; a₃₂=80; a₃₃=1, b₃=12025.

Отметим, что дополнительные переменные y ₁, y ₂, y ₃ вошли в условие задачи, но не вошли в выражение для целевой функции (80). Она не изменила своего вида и осталась функцией двух переменных х ₁ и х ₂ (с ₁ = 3, с ₂ = 4,5 ).

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

- F(x₁, x₂) = - (3 x₁ + 4,5 x₂)

(85)

1 этап. Поиск опорного решения задачи начинается с построения первого опорного решения системы (83). Наиболее просто найти опорное решение, соответствующее нулевым значениям переменных

х₁⁽¹⁾ = 0, х₂⁽¹⁾ = 0, (86)

тогда из (75) получим базисные переменные

у ₁⁽¹⁾ = 3200, у ₂⁽¹⁾ = 30, у ₃⁽¹⁾ = 12025, (87)

Для первого опорного решения системы (83) переменные у⁽¹⁾ ₁, у⁽¹⁾ ₂,

у⁽¹⁾ ₃ являются базисными (84), а переменные х⁽¹⁾ ₁, х⁽¹⁾ ₂ – свободными (86).

Выразим из системы (83) базисные переменные через свободные переменные. Соответствующие формулы имеют вид

у⁽¹⁾₁= 3200 – 16 х⁽¹⁾₁ - 25 х⁽¹⁾₂ ,

у⁽¹⁾₂ = 30 - 0,2 х⁽¹⁾₁ - 0,15 х⁽¹⁾₂,

у⁽¹⁾₃ = 12025 – 75 х⁽¹⁾₁ - 80 х⁽¹⁾₂. (88)

Выбранному первому опорному решению соответствует нулевое значение целевой функции. После подстановки в уравнение (83) значения свободных переменных x⁽¹⁾₁, x⁽¹⁾₂ (86)

- F⁽¹⁾ = - (3 x⁽¹⁾₁ + 4,5 x⁽¹⁾₂) = - (3*0+4,5*0) = 0. (89)

Любое изменение переменных x⁽¹⁾₁ , x⁽¹⁾₂ в функции цели (89) приведет к уменьшению ее величины. Переходим ко второму опорному решению.

Составим симплекс-таблицу, которую построим следующим образом:

- в первые два столбца таблицы впишем значения коэффициентов при свободных переменных x⁽¹⁾ ₁, x⁽¹⁾ ₂ из системы уравнений (83); в третий столбец впишем значения базисных переменных у ₁⁽¹⁾ , у ₂⁽¹⁾ , у ₃⁽¹⁾ (87). В последнюю строку запишем значения коэффициентов при свободных переменных из уравнения целевой функции (89) и значение целевой функции (табл. 4).

Таблица 4

Симплекс – таблица первого опорного решения системы (89)

х(1) 1	х(1) 2	у(1) i
Коэфф. при свободных переменных	Значения базисных переменных
			у (1) 1 - т стали
0,2	0,15		у(1) 2 - т свар. мат-ла
			у(1) 3 - ч/час
	4,5		- F

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

1) центр находится в том столбце, последний элемент которого положителен;

2) центр не нулевой и положительный;

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

Так как в табл. 4 последние элементы в двух первых столбцах положительны, то центр может располагаться как в первом, так и во втором столбцах. Если учесть, что производство РВС-1000 дает больший доход, чем производство РВС-400, то будем считать, что центр расположен во втором столбце. За центр можно выбратьлюбое значение второго столбца: а=25>0, a=0,15>0, a=79,8>0. За центр принимаем а=25, так как

3200/25= 128 < 12025/80 = 150,31 < 30/0,15= 200.

В строке с центром а=25 (табл. 4),определяем свободные переменные второго опорного решения. Так как х⁽²⁾ ₂ ≠ 0, то свободными переменными будут х⁽²⁾₁, у⁽²⁾₁ :

х⁽²⁾₁ =0, у⁽²⁾₁ =0. (90)

Тогда базисныепеременные х⁽²⁾₂ , у⁽²⁾₂, у⁽²⁾₃ определяем из выражений (88):

х⁽²⁾₂ =128; у⁽²⁾₂ =30-0,15*128=10,8; у⁽²⁾₃ =12025-80*128=1785 (91)

Второму опорному решению соответствует следующее значение целевой функции

- F⁽²⁾ = - (3 x⁽²⁾₁ + 4,5 x⁽²⁾₂) = -(3*0 + 4,5*128) = -576 < - F⁽¹⁾ = 0. (92)

Мы видим, что решение (92) «лучше» (меньше) предыдущего решения (89). Выразим базисные переменные (91) и целевую функцию через свободные переменные (90)

х⁽²⁾₂= 128 - 0,64 х⁽²⁾₁ – 0,04 у⁽²⁾₁,

у⁽²⁾₂= 10,8 – 0,104 х⁽²⁾₁+0,006 у⁽²⁾₁,

у⁽²⁾₃= 1785 – 23,8 х⁽²⁾₁ + 3,2 у⁽²⁾₁ (93)

-F⁽²⁾=-(0,12 x⁽²⁾₁ - 0,18 у⁽²⁾₁) = -576 (94)

Выбранное второе опорное решение (93) не является оптимальным, так как увеличение переменной x⁽²⁾ ₁ уменьшает целевую функцию (94). Поэтому переходим к третьему опорному решению. Для этого перепишем выражения (93) в виде системы канонических уравнений, перенеся неизвестные в левую сторону:

0,64 х⁽²⁾₁ + х⁽²⁾₂ + 0,04 у⁽²⁾₁= 128,

0,104 х⁽²⁾₁ - 0,006 у⁽²⁾₁ + у⁽²⁾₂= 10,8,

23,8 х⁽²⁾₁ - 3,2 у⁽²⁾₁ + у⁽²⁾₃= 1785 (95)

Составим симплекс-таблицу (табл. 5), используя коэффициенты уравнений (95) и (94).

Таблица 5

Симплекс – таблица второго опорного решения системы (95)

х(2) 1	у(2) 1
Коэф. при свободные переменных	Значения базисные переменных
0,64	0,04		х(2) 2 – РВС-1000
0,104	-0,006	10,8	у(2) 2- т свар. мат-ла
23,8	-3,2		у(2) 3 - ч/час
0,12	-0,18	-576	- F

Центром для третьего опорного решения является а=23,8, так как (табл. 5):

1) последнее значение в первом столбце положительное;

2) значения во второй и третьей строках первого столбца не нулевые и положительные (значение в первой строке нельзя принимать за центр, так как при х₂=0 значение целевой функции увеличится, а не уменьшится);

3) 1785 / 23,8 = 75 < 10,8 / 0,104= 103,85.

В строке с центром а=23,8 определяем свободные переменные третьего опорного решения. Так как х⁽³⁾₁ ≠ 0, то свободными переменными будут у⁽³⁾₁ , у⁽³⁾₃:

у⁽³⁾₁= 0, у⁽³⁾₃ =0. (96)

Тогда базисные переменные х⁽³⁾₁ , х⁽³⁾₂, у⁽³⁾₂ определяем из выражений (95)

х⁽³⁾₁= 75; х⁽³⁾₂=80; у⁽³⁾₂=10,8-0,104*75=3; (97)

Третьему опорному решению соответствует следующее значение целевой функции

- F⁽³⁾ = -(3*75+4,5*80) = -585 < - F⁽²⁾ = -576 (98)

Мы видим, что решение (98) «лучше» (меньше) предыдущего решения (94). Выразим базисные переменные (97) и целевую функцию через свободные переменные (96)

х⁽³⁾₁= 75 + 0,134 у⁽³⁾₁ – 0,042 у⁽³⁾₃,

х⁽³⁾₂= 80 - 0,126 у⁽³⁾₁ + 0,027 у⁽³⁾₃,

у⁽³⁾₂= 3 + 0,0046 у⁽³⁾₁-0,0044 у⁽³⁾₃, (99)

- F⁽³⁾ = -3 (75 + 0,134 у⁽³⁾₁ – 0,042 у⁽³⁾₃)-4,5 (80 - 0,126 у⁽³⁾₁ + 0,02 7у⁽³⁾₃) =

= - 585 + 0,165 у⁽³⁾₁ + 0,0045 у⁽³⁾₃ (100)

В выражении целевой функции переменные у⁽³⁾ ₁ и у⁽³⁾ ₃ (100) имеют положительные коэффициенты. Поэтому их увеличение может только увеличить целевую функцию. В этом случае можно перейти ко второму этапу решения задачи.

2 этап - переход от опорного решения к оптимальному. Третье опорное решение является наименьшим, так как дает наименьшее значение целевой функции (100). Таким образом, третье опорное решение является оптимальным, а число - 585 наименьшим значением целевой функции на классе допустимых решений.

Это соответствует оптимальному плану завода, согласно которому нужно изготовить 75 резервуаров типа РВС-400 и 80 резервуаров типа РВС-1000 на общую сумму 585 тыс. руб.