Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Упростить выражение
Примеры решений Метод Гомори Графический метод Теория игр
Симплекс-метод M-задача Теоремы двойственности
Одноканальные СМО Задача коммивояжера Транспортная задача

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

Здесь рассмотрен пример решения в виде симплексной таблицы с использованием калькулятора. Минимум функции также можно найти двойственным симплекс-методом
2x1+12x2 ≥ 20
4x1+6x2 ≥ 32
3x1 ≥ 14
18x2 ≥ 42
12x1+10x2 → min

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

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

План Базис В x1 x2 x3 x4 x5 x6 min
1x3-20-2-1210001.67
x4-32-4-601005.33
x5-14-300010-
x6-420-1800012.33
Индексная строкаF(X1)0121000000
2x21.670.171-0.08000-
x4-22-30-0.510044
x5-14-300010-
x6-1230-1.50018
Индексная строкаF(X2)-16.6710.3300.830000
3x22.3301000-0.06-
x4-18-40010-0.3354
x5-14-300010-
x38-2-01-0-018
Индексная строкаF(X3)-23.331200000.560
4x22.78-0.1110.06000-
x4-15.33-4.6700.331003.29
x5-14-3000104.67
x68-2-01-0-01-
Индексная строкаF(X4)-27.7813.110-0.560000
5x23.14-010.05-0.020066
x13.291-0-0.07-0.21-00-
x5-4.1400-0.21-0.641019.33
x614.570-00.86-0.43-0117
Индексная строкаF(X5)-70.86000.382.81000
6x22.33-010-00-0.06-
x14.51-00-0.25-00.08-
x5-0.5000-0.7510.250.67
x3170-01-0.5-01-
Индексная строкаF(X6)-77.3300030-0.440
7x22.33-0100-0-0.06-
x14.671-000-0.3304.67
x40.67-0-0-01-1.330.25-
x317.330-010-0.670.83-
Индексная строкаF(X7)-79.33000-040.560

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




























Итерация №1
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x3, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления и из них выберем наименьшее:
Следовательно,4-ая строка является ведущей
Разрешающий элемент равен -1.5 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x6 в план 2 войдет переменная x3
Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=-1.5
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x3 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №2
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x6, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления и из них выберем наименьшее:
Следовательно,4-ая строка является ведущей
Разрешающий элемент равен 1 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x3 в план 3 войдет переменная x6
Строка, соответствующая переменной x6 в плане 3, получена в результате деления всех элементов строки x3 плана 2 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 3 получаем 1.
В остальных клетках столбца x6 плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x6 и столбец x6.
Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №3
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления и из них выберем наименьшее:
Следовательно,2-ая строка является ведущей
Разрешающий элемент равен -4.67 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 4 войдет переменная x1
Строка, соответствующая переменной x1 в плане 4, получена в результате деления всех элементов строки x4 плана 3 на разрешающий элемент РЭ=-4.67
На месте разрешающего элемента в плане 4 получаем 1.
В остальных клетках столбца x1 плана 4 записываем нули.
Таким образом, в новом плане 4 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 4, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №4
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x3, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления и из них выберем наименьшее:
Следовательно,4-ая строка является ведущей
Разрешающий элемент равен 0.86 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x6 в план 5 войдет переменная x3
Строка, соответствующая переменной x3 в плане 5, получена в результате деления всех элементов строки x6 плана 4 на разрешающий элемент РЭ=0.86
На месте разрешающего элемента в плане 5 получаем 1.
В остальных клетках столбца x3 плана 5 записываем нули.
Таким образом, в новом плане 5 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 5, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №5
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x4, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления и из них выберем наименьшее:
Следовательно,3-ая строка является ведущей
Разрешающий элемент равен -0.75 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x5 в план 6 войдет переменная x4
Строка, соответствующая переменной x4 в плане 6, получена в результате деления всех элементов строки x5 плана 5 на разрешающий элемент РЭ=-0.75
На месте разрешающего элемента в плане 6 получаем 1.
В остальных клетках столбца x4 плана 6 записываем нули.
Таким образом, в новом плане 6 заполнены строка x4 и столбец x4.
Все остальные элементы нового плана 6, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №6
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления и из них выберем наименьшее:
Следовательно,2-ая строка является ведущей
Разрешающий элемент равен 1 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x1 в план 7 войдет переменная x1
Строка, соответствующая переменной x1 в плане 7, получена в результате деления всех элементов строки x1 плана 6 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 7 получаем 1.
В остальных клетках столбца x1 плана 7 записываем нули.
Таким образом, в новом плане 7 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 7, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Итерация №7
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления и из них выберем наименьшее:
Следовательно,2-ая строка является ведущей
Разрешающий элемент равен 1 и находится на пересечении ведущего столбца и ведущей строки
Оптимальный план можно записать так: x2 = 2.33, x1 = 4.67, x4 = 0.67, x3 = 17.33
F(X) = 79.33

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