Математические методы

Базис	B	x1	x2	x3	x4	x5	x6
x3	102/5	0	1/5	1	0	1/5	0
x1	22/5	1	-4/5	0	0	1/5	0
x4	11/5	0	-32/5	0	1	3/5	-1
F(X2)	12	0	-7	0	0	1	M

 

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

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

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

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

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

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

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

min (10²/₅ : ¹/₅ , - , - ) = 52

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

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

Базис	B	x1	x2	x3	x4	x5	x6	min
x3	102/5	0	1/5	1	0	1/5	0	52
x1	22/5	1	-4/5	0	0	1/5	0	-
x4	11/5	0	-32/5	0	1	3/5	-1	-
F(X3)	12	0	-7	0	0	1	M	0

 

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

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

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

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

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

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

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

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

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

Базис	B	x1	x2	x3	x4	x5	x6
x2	52	0	1	5	0	1	0
x1	44	1	0	4	0	1	0
x4	178	0	0	17	1	4	-1
F(X3)	376	0	0	35	0	8	M

 

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

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

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

Базис	B	x1	x2	x3	x4	x5	x6
x2	52	0	1	5	0	1	0
x1	44	1	0	4	0	1	0
x4	178	0	0	17	1	4	-1
F(X4)	376	0	0	35	0	8	M

 

Так как в оптимальном  решении отсутствуют искусственные  переменные (они равны нулю), то данное решение является допустимым.

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

x₂ = 52

x₁ = 44

F(X) = 3•52 + 5•44 = 376

Ответ: оптимальный план равен 376 у.е., при x₁ = 44 шт., x₂ = 52 шт.

Задача № 2.

На приобретение оборудования для нового производственного участка  имеются капиталовложения 21 тыс. у.е., а для его размещения выделена площадь 49 м². Можно приобрести оборудование двух видов. Единица оборудования первого вида занимает 7 м² и стоит 2 тыс. у.е. Для оборудования второго вида эти данные: 2 м² и 7 тыс. у.е. Прибыль от единицы нового оборудования составляет 4 тыс. у.е и 7 тыс.у.е соответственно. Сколько нужно приобрести нового оборудования каждого вида, чтобы получить наибольшую прибыль и при этом полностью израсходовать выделенные капиталовложения?

Решение:

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

Пусть х₁ – количество оборудования первого вида

 х₂ – количество оборудования второго вида

Система уравнений определяющая условия  размещения оборудования первого и второго вида по размещению и стоимости:

Необходимо максимизировать целевую  функцию:

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

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

7x₁ + 2x₂≤49

2x₁ + 7x₂≤21

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

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

7x₁ + 2x₂ + 1x₃ + 0x₄ = 49

2x₁ + 7x₂ + 0x₃ + 1x₄ = 21

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

 

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

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

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

x₃, x₄,

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

X1 = (0,0,49,21)

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

Базис	B	x1	x2	x3	x4
x3	49	7	2	1	0
x4	21	2	7	0	1
F(X0)	0	-4	-7	0	0

 

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

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

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

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

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

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

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

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

min (49 : 2 , 21 : 7 ) = 3

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

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

Базис	B	x1	x2	x3	x4	min
x3	49	7	2	1	0	241/2
x4	21	2	7	0	1	3
F(X1)	0	-4	-7	0	0	0

 

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

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

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

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

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

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

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

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

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

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

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

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

Базис	B	x1	x2	x3	x4
x3	43	63/7	0	1	-2/7
x2	3	2/7	1	0	1/7
F(X1)	21	-2	0	0	1

 

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

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

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

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

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

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

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

min (43 : 6³/₇ , 3 : ²/₇ ) = 6³¹/₄₅

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

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