Файл: Содержание Теоретический раздел 4.doc

Цикл приведен в таблице (2,5; 2,2; 1,2; 1,5; ).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	7	4[65]	15	9	14[55]	120
2	11	2	7[75]	2[60]	10[15]	150
3	4[85]	5	12[15]	8	17	100
Потребности	85	65	90	60	70

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=3	v2=4	v3=11	v4=6	v5=14
u1=0	7	4[65]	15	9	14[55]
u2=-4	11	2	7[75]	2[60]	10[15]
u3=1	4[85]	5	12[15]	8	17

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

Минимальные затраты составят:

F(x) = 4*65 + 14*55 + 7*75 + 2*60 + 10*15 + 4*85 + 12*15 = 2345

---

2.2 Решение производственной задачи

Вариант 1.

Предприятие предполагает выпускать два вида продукции А и В, для производства которых используется сырьё трех видов. Производство обеспечено сырьем каждого вида в количествах: 432, 424, 532 кг. На изготовление единицы изделия А требуется затратить сырья каждого вида 2, 3, 5 кг, соответственно, а для единицы изделия В – 5, 4, 3 кг. Прибыль от реализации единицы изделия А составляет 34 ден.ед., для единицы изделия В – 50 ден.ед.

Требуется составить план производства изделий А1 и А2 обеспечивающий максимальную прибыль предприятия от реализации готовой продукции.

Вид сырья	Продукция		Ограничения по сырью
	А	В
1-й	2	5	432
2-й	3	4	424
3-й	5	3	532
прибыль	34	50

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

Решение.

Обозначим через х₁ и х₂ количество единиц продукции соответственно А и В, запланированных к производству. Для их изготовления потребуется (2х₁ +5 х₂) единиц ресурса I, (3х₁ +4х₂) единиц ресурса II, (5х₁ +3х₂) единиц ресурса III. Так как потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

2 х₁ +5х₂ ≤ 432;

3х₁ +4х₂ ≤ 424; (6)

5х₁ +3х₂ ≤ 532.
По смыслу задачи переменные:

х₁ ≥ 0, х₂ ≥ 0. (7)

Суммарная прибыль составит 34х₁ от реализации продукции А и 50х ₂ от реализации продукции В, то есть :

F = 34х₁ +50х ₂ max (8)

Далее будем решать задачу двумя методами:

1способ – симплексный метод

С помощью дополнительных неотрицательных переменных перейдём к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком « + », так как все неравенства имеют вид « ≤ ».

---

Получим систему ограничений в виде :
2 х ₁ +5х₂ + х₃ ≤ 432;

3х₁ +4х₂ + х₄ ≤ 424; (9)

5х₁ + 3х₂ + х₅ ≤ 532.
Для нахождения первоначального базисного решения разобьём переменные на две группы – основные и не основные. Так как определитель, составленный из коэффициентов при дополнительных переменных х₃, х₄, х₅ отличен от нуля, то эти переменные можно взять в качестве основных на первом шаге решения задачи.

I шаг.

Основные переменные: х₃, х₄, х_5.

Не основные переменные: х₁, х_{2. .}

Выразим основные переменные через не основные :
х ₃ = 432 - 2х₁ - 5х₂ ;

х₄ = 424-3х₁ - 4х₂; (10)

х₅ = 532 - 5х₁ - 3х_2.
Положив основные переменные равными нулю, то есть х₁ = 0, х₂ = 0, получим базисное решение Х₁ = (0, 0, 432, 424, 532), которое является допустимым. Поскольку это решение допустимо, то нельзя отбросить возможность того, что оно оптимально. Выразим линейную функцию через не основные переменные:
F = 34х₁ + 50х_{2 .} max
При решении Х₁ значение функции равно F(Х₁). Легко понять, что функцию F можно увеличить за счёт увеличения любой из не основных переменных, входящих в выражение F с положительным коэффициентом. Это можно осуществить, перейдя к новому базисному решению, в котором эта переменная будет не основной, то есть принимать не нулевое, а положительное значение. При таком переходе одна из основных переменных перейдёт в не основные. В данном примере для увеличения F можно переводить в основные любую переменную, так как и х₁ и х₂ входят в выражение для F со знаком «+». Для определённости будем выбирать переменную, имеющую больший коэффициент, то есть х₂. Система (10) накладывает ограничения на рост переменной х₂ . Поскольку необходимо сохранять допустимость решений, то есть все переменные должны оставаться неотрицательными, то должны выполняться следующие неравенства (при этом х₁ = 0 как не основная переменная):
х

---

₃ = 432 - 5х₂ ≥ 0; х₂ ≤ 432;

х₄ = 424 - 4х₂ ≥ 0; откуда х₂ ≤ 424;

х₅ = 532- 3х₂ ≥ 0; х₂ ≤ 532.

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

Очевидно, что сохранение неотрицательности всех переменных возможно, если не нарушается ни одна из полученных границ. В данном примере наибольшее возможное значение для переменной х₂ определяется как х₂ = min {432/5, 106, 532/3} = 86. При х₂ = 86 переменная х = 0 и переходит в не основные.

Уравнение, где достигается наибольшее возможное значение переменной, переводимой в основные (то есть, где оценка минимальна), называется разрешающим. В данном случае – это третье уравнение.

II шаг.

Основные переменные: х₂, х₄, х_5.

Не основные переменные: х₁, х_{.3 .}

Выразим основные переменные через новые не основные, начиная с разрешающего уравнения(его используем для записи выражения для х₂ ) :
х ₂ =86- 0,4 х₁ - 0,2х₃;

х4 =78 –1,4х₁ + 0,8х₃;

х ₅=273 – 3,8х₁ + 0,6х₃.
Второе базисное решение Х₂ = (0, 86, 0, 78, 273 ) является допустимым.

Выразив линейную функцию через не основные переменные на этом шаге, получаем:
F = 4320  + 14 x₁-10 x₃
Значение линейной функции F₂ = F(X₂) =  4320

Поскольку необходимо сохранять допустимость решений, то должны выполняться следующие неравенства(при этом х₁ = 0 как не основная переменная):
х₂ =86 - 0,2х₃ ≥ 0; х₃ ≤ 430;

х ₄ =78 + 0,8х₃ ≥ 0; откуда х₃ ≤ -98; (11)

х₅ =273 + 0,6х₃ ≥ 0. х₃ ≤ -455.
Обнаруживаем возможность дальнейшего увеличения линейной функции за счёт переменной х_1, входящей в выражение для F с положительным коэффициентом. Система уравнений (11) определяет наибольшее возможное значение для х₅ :
Х₃ = min {430,-98,-455} = -98 .
При х₃ = -98 х₄ = 0 переходит в неосновные переменные.

---

Разрешающим будет третье уравнение.

III шаг.

Основные переменные: х₁, х₂, х_5.

Неосновные переменные: х₄, х_3.

Выразим основные переменные через неосновные:
х ₁= 56 – 3/7х₃ -2/7х₄;

х₂ = 64 + 4/7х₃ - 5/7х₄;

х₅ = 60 - 11/7х₃ + 19/7х_4.
Третье базисное решение Х₃ = (56, 64,0, 0, 60) является допустимым.

Выразим линейную функцию через неосновные переменные:
F = 5104  -2 x₃-10 x_4.

Значение линейной функции F₃ = F(X₃) = 5104.

Учитывая, что все x _i 0, по условию задачи, наибольшее значение функции F равно свободному члену 5104, т.е. мы получили оптимальное решение.

Теперь можем записать ответ.
Ответ: максимальная прибыль от реализации продукции равна 5104 ден. ед. X _опт = (56 , 64 , 0 , 0 , 60).
2 способ:симплекс-метод табличный
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.

Определим максимальное значение целевой функции F(X) = 34x₁+50x₂ при следующих условиях-ограничений.

2x₁+5x₂≤432

3x₁+4x₂≤424

5x₁+3x₂≤532

2x₁ + 5x₂ + 1x₃ + 0x₄ + 0x₅ = 432

3x₁ + 4x₂ + 0x₃ + 1x₄ + 0x₅ = 424

5x₁ + 3x₂ + 0x₃ + 0x₄ + 1x₅ = 532

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Решим систему уравнений относительно базисных переменных:

x₃, x₄, x₅,

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

X1 = (0,0,432,424,532)

Базис	В	x1	x2	x3	x4	x5
x3	432	2	5	1	0	0
x4	424	3	4	0	1	0
x5	532	5	3	0	0	1
F(X0)	0	-34	-50	0	0	0

---