Симплекс метод решения задачи линейного программирования калькулятор

Симплекс метод

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

	x1	+	x2	≤	4
	2	x1	+	x2	≤	6

x₁ ≥ 0 x₂ ≥ 0

	x1	+	x2	≤	4
	2	x1	+	x2	≤	6

	x1	+	x2	+	S1	=	4
	2	x1	+	x2	+	S2	=	6

3. Нахождение начального базиса и значения функции F, которое соответствует найденному начальному базису.

Что такое базис?
Переменная называется базисной для данного уравнения, если она входит в данное уравнение с коэффициентом один и не входит в оставшиеся уравнения системы (при условии, что в правой части уравнения стоит неотрицательное число).
Если в каждом уравнении присутствует базисная переменная, тогда говорят, что в системе присутствует базис.
Переменные, которые не являются базисными, называются свободными.

В чем заключается идея симплекс метода?
Каждому базису соответствует единственное значение функции. Одно из них является наибольшим значением функции F.
Мы будем переходить от одного базиса к другому.
Следующий базис будем выбирать таким образом, чтобы получить значение функции F не меньше имеющегося.
Очевидно, количество возможных базисов для любой задачи число не очень большое.
Следовательно, рано или поздно, ответ будет получен.

Как осуществляется переход от одного базиса к другому?
Запись решения удобнее вести в виде таблиц. Каждая строка таблицы эквивалентна уравнению системы. Выделенная строка состоит из коэффициентов функции (см. таблицу ниже). Это позволяет не переписывать переменные каждый раз, что существенно экономит время.
B выделенной строке выбираем наибольший положительный коэффициент (можно выбрать любой положительный).
Это необходимо для того, чтобы получить значение функции F не меньше имеющегося.
Выбран столбец.
Для положительных коэффициентов выбранного столбца считаем отношение Θ и выбираем наименьшее значение.
Это необходимо для того, чтобы после преобразования столбец свободных членов остался неотрицательным.
Выбрана строка.
Определен элемент, который будет базисным. Далее считаем.

В нашей системе есть базис?

Приравниваем свободные переменные нулю. Устно находим значения базисных переменных. (см. систему)
Функция F выражена через свободные переменные. Поэтому значение функции F, для данного базиса, можно найти мгновенно.

x1	x2	S1	S2	св. член	Θ
1	1	1	0	4	4 : 1 = 4
2	1	0	1	6	6 : 1 = 6
1	3	0	0	F — 0
1	1	1	0	4
1	0	-1	1	2
-2	0	-3	0	F — 12

Приравниваем свободные переменные нулю. Устно находим значения базисных переменных. (см. таблицу)
Функция F выражена через свободные переменные. Поэтому значение функции F, для данного базиса, можно найти мгновенно. (см. выделенную строку таблицы)

Среди коэффициентов выделенной строки нет положительных. Следовательно, найдено наибольшее значение функции F.

x₁ = 0 x₂ = 4

F_max = 12

Если у Вас есть замечания, пожалуйста, пишите siteReshmat@yandex.ru

Источник

Двойственный симплексный метод

Двойственный симплексный метод основан на теории двойственности (см. решение двойственной задачи) и используется для решения задач линейного программирования, свободные члены которых b_i могут принимать любые значения, а система ограничений задана неравенствами смысла «≤», «≥» или равенством «=».

Инструкция для решения задач двойственным симплекс-методом. Выберите количество переменных и количество строк (количество ограничений), нажмите Далее . Полученное решение сохраняется в файле Word . При этом ограничения типа x_i≥0 не учитывайте.

Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.

Экстремум функции двух переменных

Задачи динамического программирования
Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X) зависит от количества реализованных партий товара Х и представлен в таблице.

Объем товара Х (в партиях)	Доход G(X)
	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

1. Составление псевдоплана. Систему ограничений исходной задачи приводят к системе неравенств смысла «&#8804».
2. Проверка плана на оптимальность. Если в полученном опорном плане не выполняется условие оптимальности, то задача решается симплексным методом.
3. Выбор ведущих строки и столбца. Среди отрицательных значений базисных переменных выбираются наибольшие по абсолютной величине. Строка, соответствующая этому значению, является ведущей.
4. Расчет нового опорного плана. Новый план получается в результате пересчета симплексной таблицы методом Жордана-Гаусса. Далее переход к этапу 2.

Алгоритм двойственного симплекс-метода

Пример решения Р-методом

Условие задачи. Предприятию необходимо выпустить по плану продукции А₁– 500 единиц, А₂– 300 единиц, А₃– 450 единиц. Каждый вид изделия может производиться на двух машинах.
Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальны? Дана матрица затрат и ресурс времени каждой машины. Записать модель исследуемой операции в форме, допускающей использование P – метода.

Матрица затрат времени на производство видов продукции g – го вида A=(aig)
Машины	Виды продукции			Ресурс времени машин
	А1	А2	А3
1	2	3	3	1500
2	5	4	1	1000
План выпуска продукции	500	300	450

Составим математическую модель задачи.
2x₁₁+ 3x₁₂+3x₁₃≤ 1500
5x₂₁+ 4x₂₂+x₂₃≤ 1000
x₁₁+ x₂₁≥ 500
x₁₂+ x₂₂≥ 300
x₁₃+ x₂₃≥ 450
Целевая функция:
2x₁₁+ 3x₁₂+3x₁₃+ 5x₂₁+ 4x₂₂+x₂₃→ min
Запишем в виде, решаемом Р-методом.
2x₁₁+ 3x₁₂+3x₁₃≤ 1500
5x₂₁+ 4x₂₂+x₂₃≤ 1000
-x₁₁ -x₂₁≤ -500
-x₁₂-x₂₂≤ -300
-x₁₃-x₂₃≤ -450
Определим минимальное значение целевой функции F(X) = 2x₁+3x₂+3x₃+5x₄+4x₅+x₆при следующих условиях-ограничений.
2x₁+3x₂+3x₃≤1500
5x₄+4x₅+x₆≤1000
-x₁-x₄≤-500
-x₂-x₅≤-300
-x₃-x₆≤-450
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2x₁+ 3x₂+ 3x₃+ 0x₄+ 0x₅+ 0x₆+ 1x₇+ 0x₈+ 0x₉+ 0x₁₀+ 0x₁₁= 1500
0x₁+ 0x₂+ 0x₃+ 5x₄+ 4x₅+ 1x₆+ 0x₇+ 1x₈+ 0x₉+ 0x₁₀+ 0x₁₁= 1000
-1x₁+ 0x₂+ 0x₃-1x₄+ 0x₅+ 0x₆+ 0x₇+ 0x₈+ 1x₉+ 0x₁₀+ 0x₁₁= -500
0x₁-1x₂+ 0x₃+ 0x₄-1x₅+ 0x₆+ 0x₇+ 0x₈+ 0x₉+ 1x₁₀+ 0x₁₁= -300
0x₁+ 0x₂-1x₃+ 0x₄+ 0x₅-1x₆+ 0x₇+ 0x₈+ 0x₉+ 0x₁₀+ 1x₁₁= -450
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

2	3	3	0	0	0	1	0	0	0	0
0	0	0	5	4	1	0	1	0	0	0
-1	0	0	-1	0	0	0	0	1	0	0
0	-1	0	0	-1	0	0	0	0	1	0
0	0	-1	0	0	-1	0	0	0	0	1

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x₇, x₈, x₉, x₁₀, x₁₁,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,0,0,1500,1000,-500,-300,-450)

План	Базис	В	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	x11
0	x7	1500	2	3	3	0	0	0	1	0	0	0	0
	x8	1000	0	0	0	5	4	1	0	1	0	0	0
	x9	-500	-1	0	0	-1	0	0	0	0	1	0	0
	x10	-300	0	-1	0	0	-1	0	0	0	0	1	0
	x11	-450	0	0	-1	0	0	-1	0	0	0	0	1
Индексная строка	F(X0)	0	-2	-3	-3	-5	-4	-1	0	0	0	0	0
θ			2			5

Посмотреть все итерации Оптимальный план можно записать так: x₅ = 133.33, x₈ = 16.67, x₁ = 500, x₂ = 166.67, x₆ = 450
F(X) = 2*500 + 3*166.67 + 4*133.33 + 1*450 = 2483.33 Пример №1 . Предприятию необходимо выпустить по плану продукции, не менее, чем: А 1 — 500 единиц, А2 – 300 единиц, А 3 – 450 единиц. Каждый вид изделия может производиться на двух машинах. Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальными, если задана матрица затрат. Ресурс времени каждой машины приведен справа от таблицы. Записать модель исследуемой операции в форме, допускающей использование Р-метода. Решить задачу Р-методом. Пример №2 . Из 4 видов кормов необходимо составить рацион, в состав которого должно входить не менее в1 ед. вещества А, в 2 ед. вещества В и в 3 ед. вещества С. Количество единиц вещества, содержащегося в 1 кг корма каждого вида, указано в соответствующей таблице. В ней же приведена цена 1 кг корма каждого вида.
Составить рацион, содержащий не менее нужного количества указанных питательных веществ и имеющий минимальную стоимость.

Источник