Решение задач с помощью линейного программирования

Найдем область  допустимых решений.

Решение:

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

Общая прибыль от реализации Х₁ изделий А₁ и Х₂ изделий вида А₂ составит

F = 42х₁ +26х₂ .

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

Найдем решение сформулированной задачи, используя ее геометрическую интерпретацию. Сначала определим многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств и найдем соответствующие прямые:

Эти прямые изображены на рисунке 4. Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой — нет.

 

Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты данному неравенству. Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой принадлежит эта точка, в противном случае — другая полуплоскость.

Найдем, например, полуплоскость, определяемую неравенствами.

Рисунок 4

 

 

 

 

 

 

 

 

Построим область допустимых решений:

Для прямой 3х₁ + 4х₂ = 600

х1	0	200
х2	150	0

 

 

 

С(0;0) => 3·0+4·0=0, а 0≤600, значит прямая стремится к нулю (см. рисунок 4)

 

Для прямой 3х₁ + 1х₂ = 357

х1	0	119
х2	357	0

 

 

 

В(0;0) => 3·0+1·0=0, а 0≤357, значит прямая стремится к нулю (см. рисунок 4)

 

Для прямой 1х₁ +5х₂

х1	0	600
х2	120	0

 

 

 

А(0;0) => 1·0+5·0=0, а 0≤600, значит прямая стремится к нулю (см. рисунок 4).

Это и показано стрелками.

Пересечение полученных полуплоскостей и определяет многоугольник решений  данной задачи.

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

 

 

Чтобы найти указанную точку, построим вектор ñ =(42; 26) и прямую 42х₁+26х₂ = h, где h — некоторая постоянная такая, что прямая 42х₁+26х₂ = h имеет общие точки с многоугольником решений. Положим, например, h=510 и построим прямую 42х₁ + 26х₂ = 510 (см. рисунок 4).

Если теперь взять какую-нибудь точку, принадлежащую построенной  прямой и многоугольнику решений, то ее координаты определяют такой план производства изделий А₁ и А₂, при котором прибыль от их реализации равна 510 руб. Далее, полагая h равным некоторому числу, большему чем 510, мы будем получать различные параллельные прямые. Если они имеют общие точки с многоугольником решений, то эти точки определяют планы производства изделий А₁ и А₂, при которых прибыль от их реализации превзойдет 510 руб.

Перемещая построенную прямую 30х₁ + 49х₂ = 510 в направлении вектора ñ, видим, что последней общей точкой ее с многоугольником решений задачи служит точка С. Координаты этой точки и определяют план выпуска изделий А₁ и А₂, при котором прибыль от их реализации является максимальной.

Найдем координаты точки С как точки пересечения прямых 3х₁+4х₂=600 и 3х₁ + 1х₂ = 357. Следовательно, ее координаты удовлетворяют уравнениям этих прямых

Решим эту систему уравнений:

х₂ = 357 – 3х₁, подставим полученное в первое уравнение

3х₁+ 4∙(357 – 3х₁) = 600 => 3х₁ + 1428 – 12х₁ = 600 => -9х₁ = -828 =>

х₁ = 92, из этого решения следует, что Х₂ = 357 – 3·92 = 81 => х₂ = 81

Найдем максимальную прибыль:

F(max) = 42 92+26 81=5970

Следовательно, для достижения максимальной прибыли 5970 ден.ед. следует производить 92 ед. продукции вида А₁ и 81. продукции вида А₂.

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

 

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

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

3x₁+4x₂≤600

3x₁+x₂≤357

x₁+5x₂≤600

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

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

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

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

x₁ + 5x₂ + 0x₃ + 0x₄ + 1x₅ = 600

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

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

x₃, x₄, x₅,

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

х₁ = (0,0,600,357,600)

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

 

 

Таблица 2.2.1

Базис	В	x1	x2	x3	x4	x5
x3	600	3	4	1	0	0
x4	357	3	1	0	1	0
x5	600	1	5	0	0	1
F(X0)	0	-42	-26	0	0	0

 

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

Итерация №0.

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

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

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

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

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

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

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

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

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

Таблица 2.2.2

Базис	В	x1	x2	x3	x4	x5	min
x3	600	3	4	1	0	0	600
x4	357	3	1	0	1	0	119
x5	600	1	5	0	0	1	600
F(X1)	0	-42	-26	0	0	0	0

 

 

 

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

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

Вместо переменной x₄ в план 1 войдет переменная x_1. Строка, соответствующая переменной x₁ в плане 1, получена в результате деления всех элементов строки x₄ плана 0 на разрешающий элемент РЭ=3. На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x₁ плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x₁ и столбец x₁ . Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

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

Таблица 2.2.3

B	x1	x2	x3	x4	x5

 

После преобразований получаем новую таблицу:

Таблица 2.2.4

Базис	В	x1	x2	x3	x4	x5
x3	243	0	3	1	-1	0
X1	119	1	0,333	0	0,333	0
X5	481	0	4,33	0	-0,333	1
F(X1)	4998	0	-12	0	14	0

 

Итерация №1.

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

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

 

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

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

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

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

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

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

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

Таблица 2.2.5

Базис	В	x1	x2	x3	x4	x5	min
x3	243	0	3	1	-1	0	81
X1	119	1	0,333	0	0,333	0	357
X5	481	0	4,33	0	-0,333	1	103
F(X2)	4998	0	-12	0	14	0	0