Примеры решений Теория игр Решение интегралов Пределы онлайн Деление столбиком онлайн Транспортная задача Двойственная задача Графический метод онлайн Производная онлайн Симплекс-метод

Решение задачи линейного программирования графически в трехмерном пространстве

Если в задаче три переменные, то она тоже допускает графическое решение в трехмерном пространстве. При этом рисунок делается условный, не строго выдерживая масштаб. Однако взаимное расположение точек на осях должно быть верным и соответствующим их числовым значениям.
Решить задачу линейного программирования двумя методами: графически в трехмерном пространстве и симплекс-методом.
f = 2x + 5y + 2z → max
при условиях x+4y+4z ≤ 16, 3x+2y+4z ≤ 20, x,y,z ≥ 0

Находится линия пересечения этих треугольников. Точнее, находятся координаты двух точек, являющихся концами части этой линии пересечения, лежащей в первом октанте. Множество допустимых планов (как правило) является симплексом с конечным числом угловых точек. Все эти угловые точки указывают на рисунке и точно вычисляют их координаты.
x+4y+4z = 16
3x+2y+4z = 20
1) при z = 0
x+4y = 16
3x+2y = 20
-5x = -24, откуда x = 4,8; y = 2,8; z = 0
2) y = 0
x+4z = 16
3x+4z = 20
2x = 4, откуда x = 2, y = 0, z = 3
Потом вычисляют значение целевой функции во всех угловых точках и выбирают из них оптимальное.
F(4,8; 2,8; 0) = 2*4,8 + 5*2,8 + 2*0 = 23,6
F(2; 0; 3) = 2*2+ 5*0 + 2*3 = 10
Ответ: x = 4,8; y = 2,8; z = 0, fmax = 23,6

Пример №1. Решить задачу линейного программирования графически в трехмерном пространстве.
f(x) = 3x1 + 5x2 – x3
при ограничениях
x1 + x2 + 2x3 = 6
x2 + x3 – x4 = 4
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
Решение. Проведем анализ задачи. В задаче 4 переменные и 2 основных ограничения в виде равенств (не считая условия неотрицательности). Так как ограничения даны в виде равенств, то задача в канонической форме. В данном виде геометрически задачу не решить, так как много переменных.
Решим задачу графически, преобразовав каноническую форму задачи линейного программирования к стандартному виду. У нас два ограничения и есть две переменные, каждая из которых встречается только в одном уравнении. Эти переменные можно исключить из задачи, тем самым упростив её формулировку. Исключаемыми переменными объявим первую и последнюю.
Для этого из первого условия системы ограничений выразим x1 = 6- x2 - 2x3 , а из второго уравнения x4 = x2 + x3 - 4.
Подставим x1 = 6- x2 - 2x3 в целевую функцию и получим новую целевую функцию
F = 18 + 2x2 – 7x3 и новую систему ограничений без переменных x1, x4:
x2 + 2x3 ≤6
x2 + x3 ≥ 4
x2 ≥ 0, x3 ≥ 0
За счет неотрицательности исключаемых переменных получили неравенства в разные стороны.
Полученную задачу линейного программирования стандартного вида на плоскости решим графически. На плоскости x2Ox3 изобразим множество допустимых планов, которое удовлетворяет системе ограничений. Получим треугольник с вершинами в точках B(4,0), C(6,0), A(2,2).

Решение задачи линейного программирования графически в трехмерном пространстве

Вычислим значение новой целевой функции в этих угловых точках:
F(B) = F(4,0) = 18 + 8 = 26
F(C) = F(6,0) = 18 + 12 = 30
F(A)= F(2,2) = 18 + 4 – 14 = 8
Получили решение вспомогательной (новой) задачи: x2 = 6, x3 = 0, F = 30.
Отсюда вычисляем оптимальный план и максимум исходной задачи:
x1 = 6 – 6 - 0 = 0, x4 = 6 + 0 – 4 = 2, f = F = 30
Ответ. x1 = 0, x2 = 6, x3 = 0, x4 = 2, fmax = 30.

Для решения этой задачи также можно использовать калькулятор.

Пример №2. Найти графическим методом или симплекс-методом какое-нибудь решение системы.
x + y + z = 10
5x +2y +z ≥ 26
6x + 5y + 3z ≤ 57

Решение.

Здесь не задана целевая функция. Однако графическим методом можно найти область допустимых значений (ОДР). Для этого выразить z=10-x-y и подставить в другие уравнения:
5x+2y+10-x-y ≥ 26
6x+5y+30-3x-3y ≤ 57
или
4x+y ≥ 16
3x+2y ≤ 27
Таким образом, осталось две переменные.

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