Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Примеры решений Метод Гомори Графический метод Теория игр Симплекс-метод 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

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

Болит горло
Как быстро вылечить ангину, гланды, тонзиллит
Природные средства, проверенные временем и врачами
Подробнее
ЕГЭ по математике
Yandex.Просвещение представляет бесплатные видеокурсы по ЕГЭ с возможностью прохождения тестов
Подробнее
Транспортная задача
Используя метод минимального тарифа, представить первоначальный план для решения транспортной задачи. Проверить на оптимальность, используя метод потенциалов. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1234b
112436
243858
3276310
a4688 
Решить онлайн
Курсовые на заказ