Составить математическую модель и решить задачу симплексным методом

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

От реализации одного изделия А фирма получает доход руб., изделие В - руб.

Определить максимальный доход от реализации всех изделий А и В.

Значение коэффициентов условия задачи

Значения	№ варианта

РЕШЕНИЕ:

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

10х₁ + 18 х₂ ≤ 1238

9х₁+ 15х₂ ≤ 1118

3х₁ + х₂ ≤ 523

Для постановки задачи на максимум целевую функцию запишем так:

11х₁ + 13 х₂→ max

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

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

10x₁ + 18x₂≤1238

9x₁ + 15x₂≤1118

3x₁ + x₂≤523

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x₃. В 2-м неравенстве смысла (≤) вводим базисную переменную x₄. В 3-м неравенстве смысла (≤) вводим базисную переменную x₅.

10x₁ + 18x₂ + 1x₃ + 0x₄ + 0x₅ = 1238

9x₁ + 15x₂ + 0x₃ + 1x₄ + 0x₅ = 1118

3x₁ + 1x₂ + 0x₃ + 0x₄ + 1x₅ = 523

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

Экономический смысл дополнительных переменных: дополнительные переменные задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

Решим систему уравнений относительно базисных переменных: x₃, x₄, x₅

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

X1 = (0,0,1238,1118,523)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5
x3
x4
x5
F(X0)		-11	-13

Переходим к основному алгоритму симплекс-метода.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

min (1238: 18, 1118: 15, 523: 1) = 68⁷/₉

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (18) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	min
x3							68^7/9
x4							74^8/15
x5
F(X1)		-11	-13

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₃ в план 1 войдет переменная x₂.

Строка, соответствующая переменной x₂ в плане 1, получена в результате деления всех элементов строки x₃ плана 0 на разрешающий элемент РЭ=18

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₂ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₂ и столбец x₂.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (18), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5
1238: 18	10: 18	18: 18	1: 18	0: 18	0: 18
1118-(1238 • 15):18	9-(10 • 15):18	15-(18 • 15):18	0-(1 • 15):18	1-(0 • 15):18	0-(0 • 15):18
523-(1238 • 1):18	3-(10 • 1):18	1-(18 • 1):18	0-(1 • 1):18	0-(0 • 1):18	1-(0 • 1):18
0-(1238 • -13):18	-11-(10 • -13):18	-13-(18 • -13):18	0-(1 • -13):18	0-(0 • -13):18	0-(0 • -13):18

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5
x2	^619/9	^5/9		^1/18
x4	^259/3	^2/3		^-5/6
x5	^4088/9	^22/9		^-1/18
F(X1)	^8047/9	^-34/9		^13/18

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

и из них выберем наименьшее:

min (68⁷/₉: ⁵/₉, 86¹/₃: ²/₃, 454²/₉: 2⁴/₉) = 123⁴/₅

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (⁵/₉) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	min
x2	68^7/9	^5/9		^1/18			123^4/5
x4	86^1/3	^2/3		^-5/6			129^1/2
x5	454^2/9	2^4/9		^-1/18			185^9/11
F(X2)	894^1/9	-3^7/9		^13/18

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₂ в план 2 войдет переменная x₁.

Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₂ плана 1 на разрешающий элемент РЭ=⁵/₉

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₁ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₁ и столбец x₁.

Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5
68^7/9: ^5/9	^5/9: ^5/9	1: ^5/9	^1/18: ^5/9	0: ^5/9	0: ^5/9
86^1/3-(68^7/9 • ^2/3):^5/9	^2/3-(^5/9 • ^2/3):^5/9	0-(1 • ^2/3):^5/9	^-5/6-(^1/18 • ^2/3):^5/9	1-(0 • ^2/3):^5/9	0-(0 • ^2/3):^5/9
454^2/9-(68^7/9 • 2^4/9):^5/9	2^4/9-(^5/9 • 2^4/9):^5/9	0-(1 • 2^4/9):^5/9	^-1/18-(^1/18 • 2^4/9):^5/9	0-(0 • 2^4/9):^5/9	1-(0 • 2^4/9):^5/9
894^1/9-(68^7/9 • -3^7/9):^5/9	-3^7/9-(^5/9 • -3^7/9):^5/9	0-(1 • -3^7/9):^5/9	^13/18-(^1/18 • -3^7/9):^5/9	0-(0 • -3^7/9):^5/9	0-(0 • -3^7/9):^5/9

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5
x1	^619/5		^9/5	^1/10
x4	^19/5		^-6/5	^-9/10
x5	^758/5		^-22/5	^-3/10
F(X2)	^6809/5		^34/5	^11/10

1. Проверка критерия оптимальности.

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

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5
x1	^619/5		^9/5	^1/10
x4	^19/5		^-6/5	^-9/10
x5	^758/5		^-22/5	^-3/10
F(X3)	^6809/5		^34/5	^11/10

Оптимальный план можно записать так:

x₁ = 123⁴/₅

F(X) = 11•123⁴/₅ = 1361⁴/₅

Анализ оптимального плана.

В оптимальный план вошла дополнительная переменная x₄. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 2-го вида в количестве 3⁴/₅

В оптимальный план вошла дополнительная переменная x₅. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 151³/₅

Значение 0 в столбце x₁ означает, что использование x₁ - выгодно.

Значение 6⁴/₅> 0 в столбце x₂ означает, что использование x₂ - не выгодно.

Значение 1¹/₁₀ в столбце x₃ означает, что теневая цена (двойственная оценка) равна 1¹/₁₀.

Дата добавления: 2014-12-16