Пример нахождения максимума функции симплексным методом

Здесь рассмотрен пример решения калькулятором в виде симплексной таблицы. Существуют и другие формы записи симплекс-метода

Пример №1. Предприятие выпускает 3 вида продукции А1, A2 и A3, для производства которых используется сырье трех видов. На изготовление единицы изделия А1 требуется затратить сырья каждого вида а11,а12,а13 кг соответственно, а для единицы изделия A2-a21,a22,a23 кг. Производство обеспечено сырьем каждого вида в количестве P1,P2,P3 кг. Стоимость единицы изделия А1 составляет С1 руб., А2 составляет С2 руб., а единицы изделия A3- С3 руб. Требуется составить план производства изделий А1, A2 и A3, обеспечивающий максимальную стоимость продукции. Решить:
А) геометрически;
В) симплекс-методом.
{a_1j}={0.1;0.2;0.4}
{a_2j}={0.05;0.02;0.02}
{a_3j}={3;1;2}
P1=1100,P2=120,P3=8000
C1=3,C2=5,C3=4

Решение.
Математическая модель задачи:
0.1x₁+0.2x₂+0.4x₃ ≤ 1100
0.05x₁+0.02x₂+0.02x₃ ≤ 120
3x₁+x₂+2x₃ ≤ 8000
3x₁+5x₂+4x₃ → max
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Решим систему уравнений относительно базисных переменных: x4,x5,x6
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (1100,120,8000)

План	Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	min
1	x4	1100	0.1	0.2	0.4	1	0	0	5500
	x5	120	0.05	0.02	0.02	0	1	0	6000
	x6	8000	3	1	2	0	0	1	8000
Индексная строка	F(X1)	0	-3	-5	-4	0	0	0	0
2	x2	5500	0.5	1	2	5	0	0	11000
	x5	10	0.04	0	-0.02	-0.1	1	0	250
	x6	2500	2.5	0	0	-5	0	1	1000
Индексная строка	F(X2)	27500	-0.5	0	6	25	0	0	0
3	x2	5375	0	1	2.25	6.25	-12.5	0	11000
	x1	250	1	0	-0.5	-2.5	25	0	250
	x6	1875	0	0	1.25	1.25	-62.5	1	1000
Индексная строка	F(X3)	27625	0	0	5.75	23.75	12.5	0	0

Итерация №0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x2, так как наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления:

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

Следовательно,1-ая строка является ведущей. Разрешающий элемент равен 0.2 и находится на пересечении ведущего столбца и ведущей строки. Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 1 войдет переменная x2. Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=0.2. На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x2 плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ

Итерация №1
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x₁, так как наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления и из них выберем наименьшее:

Следовательно,2-ая строка является ведущей
Разрешающий элемент равен 0.04 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x₅ в план 2 войдет переменная x₁.
Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₅ плана 1 на разрешающий элемент РЭ=0.04
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x₁ плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x₁ и столбец x₁.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Конец итераций: найден оптимальный план
Оптимальный план можно записать так: x₂ = 5375, x₁ = 250, x₆ = 1875. F(X) = 27625

Перейти к онлайн решению своей задачи

Пример №2. Наиболее эффективным для хозяйства является выращивание трех культур: озимой пшеницы, проса, гречихи. Ожидаемый уровень урожайности этих культур, себестоимость центнера продукции, нормы внесен6ия удобрений и затраты труда в расчете на единицу продукции, приведенные в соответствии с ожидаемым уровнем урожайности, заданы таблицей. Известны и наиболее вероятные цены фактической реализации центнера продукции.
Критерий оптимальности – максимум прибыли от реализации данных видов продукции.

Введем систему обозначений:
Х₁ – искомая площадь посева озимой пшеницы (га);
Х₂ – искомая площадь посева проса (га);
Х₃ – искомая площадь посева гречихи (га).

Ограничения:
1. Общая площадь посева культур (га)
Х₁+Х₂+Х₃≤2000
2. Затраты труда (чел.-дни)
Если за единицу измерения неизвестных принят 1 га, то соответственно необходимо рассчитать все нормативы на эту единицу. Затраты труда даны по условию задачи в расчете на 1 ц продукции , но, зная урожайность , легко пересчитать нормативы затрат труда в расчете на 1 га посева. Таким образом ограничение запишется так:
40x₁ + 50x₂ + 45x₃ ≤ 14600
3. Расход минеральных удобрений (ц д.в.)
0.8x₁ + 0.6x₂ + x₃ ≤ 1600

Целевая функция:
Поскольку в качестве критерия оптимальности выступает максимум прибыли, то необходимо рассчитать соответствующие коэффициенты данной целевой функции. В расчете на 1 га прибыль составит соответственно: (11.6-6)*30, (8-7)*18,(30-11)*15 рублей. Прибыль = выручка - себестоимость.
Целевая функция задач при этом будет выглядеть так:
(11.6-6)*30x₁ + (8-7)*18x₂ + (30-11)*15x₃ = max

Таким образом математическая модель задачи выглядит так:
Х₁+Х₂+Х₃≤2000
9,6Х₁+7Х₂+7,2Х₃≤14600
0,6Х₁+0,4Х₂+0,8Х₃≤1600
Z=168Х₁+18Х₂+285Х₃=max

Далее решается согласно алгоритму симплексного метода.

Поиск наибольшего значения

1. Для изготовления цемента двух видов используется сырье трех видов. Запасы сырья известны и равны соответственно: 264, 136 и 266 т. Количество сырья каждого вида, необходимое для производства единицы цемента первого вида соответственно равны: 12, 4 и 3. Для цемента второго вида: 3, 5 и 14. Прибыль от реализации цемента первого вида составляет 6 у.е., от цемента второго вида - 4 у.е. Составить план, обеспечивающий наибольшую прибыль производству:
а) записать математическую модель;
б) решить задачу графическим методом;
в) решить задачу симплекс-методом;
г) к исходной задаче записать двойственную и решить ее, используя соотношение двойственности и решение исходной.

Решение:
а) математическая модель;
x₁ – производство цемента первого вида;
x₂ – производство цемента второго вида;
12x₁ + 3x₂ ≤ 264
4x₁ + 5x₂ ≤ 136
3x₁ + 14x₂ ≤ 266
x₁ ≥ 0, x₂ ≥ 0
Целевая функция:
6x₁ + 4x₂ → max
б) решим задачу графическим методом;
Необходимо найти максимальное значение целевой функции F = 6X₁+4X₂ => max, при системе ограничений:
12x₁+3x₂≤264 (1)
4x₁+5x₂≤136 (2)
3x₁+14x₂≤266 (3)
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

Обозначим границы области многоугольника решений.

Рассмотрим целевую функцию задачи F = 6X₁+4X₂ => max.
Построим прямую, отвечающую значению функции F = 0: F = 6X₁+4X₂ = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых 1 и 2, то ее координаты удовлетворяют уравнениям этих прямых: 12x₁+3x₂≤264 4x₁+5x₂≤136
Решив систему уравнений, получим:
x₁= (264-3x₂)/12
4(264-3x₂)/12+5x₂ = 136
x₁ = 19, x₂ = 12
Откуда найдем максимальное значение целевой функции: F(X) = 6*19 + 4*12 = 162
Таким образом, чтобы получить максимальную прибыль необходимо выпускать 19 т. цемента 1-го вида, и 12 т. цемента 2-го вида.

в) решить задачу симплекс-методом;
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 6x₁+4x₂ при следующих условиях-ограничений.
12x₁+3x₂≤264
4x₁+5x₂≤136
3x₁+14x₂≤266
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
12x₁ + 3x₂ + 1x₃ + 0x₄ + 0x₅ = 264
4x₁ + 5x₂ + 0x₃ + 1x₄ + 0x₅ = 136
3x₁ + 14x₂ + 0x₃ + 0x₄ + 1x₅ = 266
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x₃, x₄, x₅,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,264,136,266)

План	Базис	В	x₁	x₂	x₃	x₄	x₅
0	x₃	264	12	3	1	0	0
	x₄	136	4	5	0	1	0
	x₅	266	3	14	0	0	1
Индексная строка	F(X0)	0	-6	-4	0	0	0

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

План	Базис	В	x₁	x₂	x₃	x₄	x₅	min
1	x₃	264	12	3	1	0	0	22
	x₄	136	4	5	0	1	0	34
	x₅	266	3	14	0	0	1	88.67
Индексная строка	F(X1)	0	-6	-4	0	0	0	0

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

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

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

План	Базис	В	x₁	x₂	x₃	x₄	x₅	min
2	x₁	22	1	0.25	0.0833	0	0	88
	x₄	48	0	4	-0.3333	1	0	12
	x₅	200	0	13.25	-0.25	0	1	15.09
Индексная строка	F(X2)	132	0	-2.5	0.5	0	0	0

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

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

Следовательно, 2-ая строка является ведущей
Разрешающий элемент равен 4 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x₄в план 2 войдет переменная x₂
Строка, соответствующая переменной x₂в плане 2, получена в результате деления всех элементов строки x₄плана 1 на разрешающий элемент РЭ=4
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x₂ плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x₂ и столбец x₂.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:

План	Базис	В	x₁	x₂	x₃	x₄	x₅
3	x₁	19	1	0	0.1042	-0.0625	0
	x₂	12	0	1	-0.0833	0.25	0
	x₅	41	0	0	0.8542	-3.31	1
Индексная строка	F(X3)	162	0	0	0.2917	0.625	0

Оптимальный план можно записать так: x₁ = 19, x₂ = 12, x₅ = 41; F(X) = 6*19 + 4*12 = 162
г) к исходной задаче записать двойственную и решить ее, используя соотношение двойственности и решение исходной.
Составим двойственную задачу к прямой задаче.
12y₁+4y₂+3y₃≥6
3y₁+5y₂+14y₃≥4
264y₁+136y₂+266y₃ => min
y₁ ≥ 0, y₂ ≥ 0, y₃ ≥ 0
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из первой теоремы двойственности следует, что Y = C*A^-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу А^-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных .
Тогда Y = C*A^-1 =

Оптимальный план двойственной задачи равен: y₁ = 0.29, y₂ = 0.62, y₃ = 0
Z(Y) = 264*0.29+136*0.62+266*0 = 162
2. На трех станциях отправления сосредоточен однородный груз, который следует перевезти в четыре пункта назначения, имеющих потребность в этом грузе. Стоимость перевозок единицы груза от каждой станции до каждого пункта назначения считается известной и содержится в таблице. Требуется составить такой план перевозок, при котором их общая стоимость окажется минимальной.
Решить транспортную задачу методом потенциалов.

Посмотреть решение

x	f₁(x)	f₂(x)	f₃(x)
1	6.3	4	5
2	5.2	6	7
3	4.3	4.6	7.8
4	5	6	3
5*	7	6.3	8.2

x	f₁(x)	f₂(x)	f₃(x)
1	6.3	4	5
2	5.2	6	7
3	4.3	4.6	7.8
4	5	6	3
5*	7	6.3	8.2

Пример нахождения максимума функции симплексным методом

Поиск наибольшего значения

Правила ввода данных

Поиск

Процесс

Сообщение