Количество ограничений:
------
Количество переменных:
------
Введите значения целевой функции:
F(x)
=
 x1 +
 x2 +
 x3 +
 x4 →
Введите значения системы ограничений:
bracket
 x1 +
 x2 +
 x3 +
 x4
 x1 +
 x2 +
 x3 +
 x4
 x1 +
 x2 +
 x3 +
 x4
 x1 +
 x2 +
 x3 +
 x4

Пример решения

F(x) = 3x1 + 4x2 → max

0002x1 + x2 ≤ 600
0x1 + 0x2 ≤ 225
5x1 +4x2 ≤ 1000
2x2 ≥ 150
0x1 + 0x2 ≥ 0
arrow transition
F(x) = 3x1 + 4x2 + 0x3 + 0x4 + 0x5 + 0x6 + 0x7 - Mx8 - Mx9 → max

0002x1 + x2 + x3 = 600
+ x4 = 225
5x1 + 4x2 + x5 = 1000
2x2 - x6 + x8 = 150
- x7 + x9 = 0

Предварительный этап:arrow down description
Предварительный этап начинается с того что необходимо избавиться от отрицательных значений(если таковые имеются) в правой части ограничений. Для чего соответствующие ограничения умножаем на -1. После данной манипуляции знак неравенства меняем на противоположный.

Далее необходимо избавиться от неравенств, для чего в левую часть неравенств вводим компенсирующие переменные. Если неравенство вида ≤, то компенсирующая переменная имеет знак +, если неравенство вида ≥, то компенсирующая переменная имеет знак -. Компенсирующие переменные входят в целевую функцию задачи с нулевым коэффициентом.

Теперь в системе ограничений необходимо найти достаточное количество базисных переменных. В каждом ограничении должна быть одна базисная переменная. Базисной является переменная, которая имеет при себе коэффициент 1 и встречается только в одном ограничении. Если в каком-то ограничении нет базисных переменных, то добавляем их искусственно, причем искусственные переменные входят в целевую функцию с коэффициентом -M, если целевая функция стремится к мах и с М, если целевая функция стремится к min.

Итерация: 1

BCbPx1x2↓x3x4x5x6x7x8x9Q
3400000-M-M
x30600211000000600
x40225000100000∞
x501000540010000250
x8
←		-M15002000-101075
x9-M0000000-101∞
max-150M-3-2M-4000MM00

Вычисление элементов таблицы:arrow down description
Элементы колонки базис(B)

Переносим в таблицу базовые элементы, которые мы определили на предварительном этапе:

B1 = x3;

B2 = x4;

B3 = x5;

B4 = x8;

B5 = x9;

Элементы колонки Cb

Каждая ячейка этого столбца равна коэффициенту, который соответствует базовой переменной в соответствующей строке.

Cb1 = 0;

Cb2 = 0;

Cb3 = 0;

Cb4 = -M;

Cb5 = -M;

Значения упрявляемых переменных и колонки P

На данном этапе никаких вычислений не нужно, просто переносим значения из предварительного этапа в соответствующие ячейки таблицы:

P1 = 600;

P2 = 225;

P3 = 1000;

P4 = 150;

P5 = 0;

x1,1 = 2;

x1,2 = 1;

x1,3 = 1;

x1,4 = 0;

x1,5 = 0;

x1,6 = 0;

x1,7 = 0;

x1,8 = 0;

x1,9 = 0;

x2,1 = 0;

x2,2 = 0;

x2,3 = 0;

x2,4 = 1;

x2,5 = 0;

x2,6 = 0;

x2,7 = 0;

x2,8 = 0;

x2,9 = 0;

x3,1 = 5;

x3,2 = 4;

x3,3 = 0;

x3,4 = 0;

x3,5 = 1;

x3,6 = 0;

x3,7 = 0;

x3,8 = 0;

x3,9 = 0;

x4,1 = 0;

x4,2 = 2;

x4,3 = 0;

x4,4 = 0;

x4,5 = 0;

x4,6 = -1;

x4,7 = 0;

x4,8 = 1;

x4,9 = 0;

x5,1 = 0;

x5,2 = 0;

x5,3 = 0;

x5,4 = 0;

x5,5 = 0;

x5,6 = 0;

x5,7 = -1;

x5,8 = 0;

x5,9 = 1;

Значение целевой функции

Рассчитываем значение целевой функции, поэлементно умножая столбик Cb на столбик P, сложив результаты произведений.

MaxP = (Cb1 * P1) + (Cb11 * P2 + (Cb21 * P3 + (Cb31 * P4 + (Cb41 * P5 = (0 * 600) + (0 * 225) + (0 * 1000) + (-M * 150) + (-M * 0) = -150M;

Оценки управляемых переменных

Рассчитываем оценки для каждой управляемой переменной, поэлементно умножив значение с колонки переменной, на значение с колонки Cb, суммируем результаты произведений, и с их суммы вычитаем коэффициент целевой функции, при этой переменной.

Maxx1 = ((Cb1 * x1,1) + (Cb2 * x2,1) + (Cb3 * x3,1) + (Cb4 * x4,1) + (Cb5 * x5,1) ) - kx1 = ((0 * 2) + (0 * 0) + (0 * 5) + (-M * 0) + (-M * 0) ) - 3 = -3;

Maxx2 = ((Cb1 * x1,2) + (Cb2 * x2,2) + (Cb3 * x3,2) + (Cb4 * x4,2) + (Cb5 * x5,2) ) - kx2 = ((0 * 1) + (0 * 0) + (0 * 4) + (-M * 2) + (-M * 0) ) - 4 = -2M-4;

Maxx3 = ((Cb1 * x1,3) + (Cb2 * x2,3) + (Cb3 * x3,3) + (Cb4 * x4,3) + (Cb5 * x5,3) ) - kx3 = ((0 * 1) + (0 * 0) + (0 * 0) + (-M * 0) + (-M * 0) ) - 0 = 0;

Maxx4 = ((Cb1 * x1,4) + (Cb2 * x2,4) + (Cb3 * x3,4) + (Cb4 * x4,4) + (Cb5 * x5,4) ) - kx4 = ((0 * 0) + (0 * 1) + (0 * 0) + (-M * 0) + (-M * 0) ) - 0 = 0;

Maxx5 = ((Cb1 * x1,5) + (Cb2 * x2,5) + (Cb3 * x3,5) + (Cb4 * x4,5) + (Cb5 * x5,5) ) - kx5 = ((0 * 0) + (0 * 0) + (0 * 1) + (-M * 0) + (-M * 0) ) - 0 = 0;

Maxx6 = ((Cb1 * x1,6) + (Cb2 * x2,6) + (Cb3 * x3,6) + (Cb4 * x4,6) + (Cb5 * x5,6) ) - kx6 = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * -1) + (-M * 0) ) - 0 = M;

Maxx7 = ((Cb1 * x1,7) + (Cb2 * x2,7) + (Cb3 * x3,7) + (Cb4 * x4,7) + (Cb5 * x5,7) ) - kx7 = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * 0) + (-M * -1) ) - 0 = M;

Maxx8 = ((Cb1 * x1,8) + (Cb2 * x2,8) + (Cb3 * x3,8) + (Cb4 * x4,8) + (Cb5 * x5,8) ) - kx8 = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * 1) + (-M * 0) ) - -M = 0;

Maxx9 = ((Cb1 * x1,9) + (Cb2 * x2,9) + (Cb3 * x3,9) + (Cb4 * x4,9) + (Cb5 * x5,9) ) - kx9 = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * 0) + (-M * 1) ) - -M = 0;

Элементы колонки Q

Поскольку среди оценок управляемых переменных есть отрицательные значения, текущая таблица еще не имеет оптимального решения. Поэтому в базис введем переменную с наименьшей отрицательной оценкой.

Количество переменных в базисе всегда постоянно, поэтому необходимо выбрать, какую переменную вывести из базиса, для чего мы рассчитываем Q.

Элементы столбика Q рассчитываем поделив значения из колонки P на значение с колонки, соответствующие переменной которая вводится в базис:

Q1 = P1 / x1,2 = 600 / 1 = 600;

Q2 = P2 / x2,2 = 225 / 0 = ∞;

Q3 = P3 / x3,2 = 1000 / 4 = 250;

Q4 = P4 / x4,2 = 150 / 2 = 75;

Q5 = P5 / x5,2 = 0 / 0 = ∞;

Выводим из базиса переменную с наименьшим положительным значением Q.

На пересечении строки, которая соответствует переменной что выводится из базиса, и столбца который соответствует переменной что вводится в базис, расположен разрешающий элемент.

Данный элемент позволит нам рассчитать элементы таблицы следующей итерации.

Итерация: 2

BCbPx1↓x2x3x4x5x6x7x8x9Q
3400000-M-M
x30525201000.50-0.50262.5
x40225000100000∞
x5
←		07005000120-20140
x247501000-0.500.50∞
x9-M0000000-101∞
max300-30000-2MM+20

Вычисление элементов таблицы:arrow down description
Элементы колонки базис(B)

За результатами вычислений предыдущей итерации убираем с базиса переменную x8 и ставим на ее место x2. Все остальные ячейки остаются без изменений.

Элементы колонки Cb

Каждая ячейка этого столбца равна коэффициенту, который соответствует базовой переменной в соответствующей строке.

Cb1 = 0;

Cb2 = 0;

Cb3 = 0;

Cb4 = 4;

Cb5 = -M;

Значения упрявляемых переменных и колонки P(В качестве исходных данных берутся данные из предыдущей итерации)

Заполняем нулями все ячейки, соответствующие переменной, которая только что была введена в базис:(Разрешающий элемент остается без изменений)

x1,2 = 0;

x2,2 = 0;

x3,2 = 0;

x5,2 = 0;

Переносим в текущую таблицу строку с разрешающим элементом с предыдущей таблицы, поэлементно поделив ее значения на разрешающий элемент:

P4 = P4 / x4,2 = 150 / 2 = 75;

x4,1 = x4,1 / x4,2 = 0 / 2 = 0;

x4,2 = x4,2 / x4,2 = 2 / 2 = 1;

x4,3 = x4,3 / x4,2 = 0 / 2 = 0;

x4,4 = x4,4 / x4,2 = 0 / 2 = 0;

x4,5 = x4,5 / x4,2 = 0 / 2 = 0;

x4,6 = x4,6 / x4,2 = -1 / 2 = -0.5;

x4,7 = x4,7 / x4,2 = 0 / 2 = 0;

x4,8 = x4,8 / x4,2 = 1 / 2 = 0.5;

x4,9 = x4,9 / x4,2 = 0 / 2 = 0;

Остальные пустые ячейки, за исключением строки оценок и колонки Q, рассчитываем методом прямоугольника, относительно разрешающего элемента:

P1 = (P1 * x4,2) - (x1,2 * P4) / x4,2 = ((600 * 2) - (1 * 150)) / 2 = 525;

P2 = (P2 * x4,2) - (x2,2 * P4) / x4,2 = ((225 * 2) - (0 * 150)) / 2 = 225;

P3 = (P3 * x4,2) - (x3,2 * P4) / x4,2 = ((1000 * 2) - (4 * 150)) / 2 = 700;

P5 = (P5 * x4,2) - (x5,2 * P4) / x4,2 = ((0 * 2) - (0 * 150)) / 2 = 0;

x1,1 = ((x1,1 * x4,2) - (x1,2 * x4,1)) / x4,2 = ((2 * 2) - (1 * 0)) / 2 = 2;

x1,2 = ((x1,2 * x4,2) - (x1,2 * x4,2)) / x4,2 = ((1 * 2) - (1 * 2)) / 2 = 0;

x1,4 = ((x1,4 * x4,2) - (x1,2 * x4,4)) / x4,2 = ((0 * 2) - (1 * 0)) / 2 = 0;

x1,5 = ((x1,5 * x4,2) - (x1,2 * x4,5)) / x4,2 = ((0 * 2) - (1 * 0)) / 2 = 0;

x1,6 = ((x1,6 * x4,2) - (x1,2 * x4,6)) / x4,2 = ((0 * 2) - (1 * -1)) / 2 = 0.5;

x1,7 = ((x1,7 * x4,2) - (x1,2 * x4,7)) / x4,2 = ((0 * 2) - (1 * 0)) / 2 = 0;

x1,8 = ((x1,8 * x4,2) - (x1,2 * x4,8)) / x4,2 = ((0 * 2) - (1 * 1)) / 2 = -0.5;

x1,9 = ((x1,9 * x4,2) - (x1,2 * x4,9)) / x4,2 = ((0 * 2) - (1 * 0)) / 2 = 0;

x2,1 = ((x2,1 * x4,2) - (x2,2 * x4,1)) / x4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x2,2 = ((x2,2 * x4,2) - (x2,2 * x4,2)) / x4,2 = ((0 * 2) - (0 * 2)) / 2 = 0;

x2,4 = ((x2,4 * x4,2) - (x2,2 * x4,4)) / x4,2 = ((1 * 2) - (0 * 0)) / 2 = 1;

x2,5 = ((x2,5 * x4,2) - (x2,2 * x4,5)) / x4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x2,6 = ((x2,6 * x4,2) - (x2,2 * x4,6)) / x4,2 = ((0 * 2) - (0 * -1)) / 2 = 0;

x2,7 = ((x2,7 * x4,2) - (x2,2 * x4,7)) / x4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x2,8 = ((x2,8 * x4,2) - (x2,2 * x4,8)) / x4,2 = ((0 * 2) - (0 * 1)) / 2 = 0;

x2,9 = ((x2,9 * x4,2) - (x2,2 * x4,9)) / x4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x3,1 = ((x3,1 * x4,2) - (x3,2 * x4,1)) / x4,2 = ((5 * 2) - (4 * 0)) / 2 = 5;

x3,2 = ((x3,2 * x4,2) - (x3,2 * x4,2)) / x4,2 = ((4 * 2) - (4 * 2)) / 2 = 0;

x3,4 = ((x3,4 * x4,2) - (x3,2 * x4,4)) / x4,2 = ((0 * 2) - (4 * 0)) / 2 = 0;

x3,5 = ((x3,5 * x4,2) - (x3,2 * x4,5)) / x4,2 = ((1 * 2) - (4 * 0)) / 2 = 1;

x3,6 = ((x3,6 * x4,2) - (x3,2 * x4,6)) / x4,2 = ((0 * 2) - (4 * -1)) / 2 = 2;

x3,7 = ((x3,7 * x4,2) - (x3,2 * x4,7)) / x4,2 = ((0 * 2) - (4 * 0)) / 2 = 0;

x3,8 = ((x3,8 * x4,2) - (x3,2 * x4,8)) / x4,2 = ((0 * 2) - (4 * 1)) / 2 = -2;

x3,9 = ((x3,9 * x4,2) - (x3,2 * x4,9)) / x4,2 = ((0 * 2) - (4 * 0)) / 2 = 0;

x5,1 = ((x5,1 * x4,2) - (x5,2 * x4,1)) / x4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x5,2 = ((x5,2 * x4,2) - (x5,2 * x4,2)) / x4,2 = ((0 * 2) - (0 * 2)) / 2 = 0;

x5,4 = ((x5,4 * x4,2) - (x5,2 * x4,4)) / x4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x5,5 = ((x5,5 * x4,2) - (x5,2 * x4,5)) / x4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x5,6 = ((x5,6 * x4,2) - (x5,2 * x4,6)) / x4,2 = ((0 * 2) - (0 * -1)) / 2 = 0;

x5,7 = ((x5,7 * x4,2) - (x5,2 * x4,7)) / x4,2 = ((-1 * 2) - (0 * 0)) / 2 = -1;

x5,8 = ((x5,8 * x4,2) - (x5,2 * x4,8)) / x4,2 = ((0 * 2) - (0 * 1)) / 2 = 0;

x5,9 = ((x5,9 * x4,2) - (x5,2 * x4,9)) / x4,2 = ((1 * 2) - (0 * 0)) / 2 = 1;

Значение целевой функции

Рассчитываем значение целевой функции, поэлементно умножая столбик Cb на столбик P, сложив результаты произведений.

MaxP = (Cb1 * P1) + (Cb11 * P2 + (Cb21 * P3 + (Cb31 * P4 + (Cb41 * P5 = (0 * 525) + (0 * 225) + (0 * 700) + (4 * 75) + (-M * 0) = 300;

Оценки управляемых переменных

Рассчитываем оценки для каждой управляемой переменной, поэлементно умножив значение с колонки переменной, на значение с колонки Cb, суммируем результаты произведений, и с их суммы вычитаем коэффициент целевой функции, при этой переменной.

Maxx1 = ((Cb1 * x1,1) + (Cb2 * x2,1) + (Cb3 * x3,1) + (Cb4 * x4,1) + (Cb5 * x5,1) ) - kx1 = ((0 * 2) + (0 * 0) + (0 * 5) + (4 * 0) + (-M * 0) ) - 3 = -3;

Maxx2 = ((Cb1 * x1,2) + (Cb2 * x2,2) + (Cb3 * x3,2) + (Cb4 * x4,2) + (Cb5 * x5,2) ) - kx2 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 1) + (-M * 0) ) - 4 = 0;

Maxx3 = ((Cb1 * x1,3) + (Cb2 * x2,3) + (Cb3 * x3,3) + (Cb4 * x4,3) + (Cb5 * x5,3) ) - kx3 = ((0 * 1) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx4 = ((Cb1 * x1,4) + (Cb2 * x2,4) + (Cb3 * x3,4) + (Cb4 * x4,4) + (Cb5 * x5,4) ) - kx4 = ((0 * 0) + (0 * 1) + (0 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx5 = ((Cb1 * x1,5) + (Cb2 * x2,5) + (Cb3 * x3,5) + (Cb4 * x4,5) + (Cb5 * x5,5) ) - kx5 = ((0 * 0) + (0 * 0) + (0 * 1) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx6 = ((Cb1 * x1,6) + (Cb2 * x2,6) + (Cb3 * x3,6) + (Cb4 * x4,6) + (Cb5 * x5,6) ) - kx6 = ((0 * 0.5) + (0 * 0) + (0 * 2) + (4 * -0.5) + (-M * 0) ) - 0 = -2;

Maxx7 = ((Cb1 * x1,7) + (Cb2 * x2,7) + (Cb3 * x3,7) + (Cb4 * x4,7) + (Cb5 * x5,7) ) - kx7 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * -1) ) - 0 = M;

Maxx8 = ((Cb1 * x1,8) + (Cb2 * x2,8) + (Cb3 * x3,8) + (Cb4 * x4,8) + (Cb5 * x5,8) ) - kx8 = ((0 * -0.5) + (0 * 0) + (0 * -2) + (4 * 0.5) + (-M * 0) ) - -M = M+2;

Maxx9 = ((Cb1 * x1,9) + (Cb2 * x2,9) + (Cb3 * x3,9) + (Cb4 * x4,9) + (Cb5 * x5,9) ) - kx9 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 1) ) - -M = 0;

Элементы колонки Q

Поскольку среди оценок управляемых переменных есть отрицательные значения, текущая таблица еще не имеет оптимального решения. Поэтому в базис введем переменную с наименьшей отрицательной оценкой.

Количество переменных в базисе всегда постоянно, поэтому необходимо выбрать, какую переменную вывести из базиса, для чего мы рассчитываем Q.

Элементы столбика Q рассчитываем поделив значения из колонки P на значение с колонки, соответствующие переменной которая вводится в базис:

Q1 = P1 / x1,1 = 525 / 2 = 262.5;

Q2 = P2 / x2,1 = 225 / 0 = ∞;

Q3 = P3 / x3,1 = 700 / 5 = 140;

Q4 = P4 / x4,1 = 75 / 0 = ∞;

Q5 = P5 / x5,1 = 0 / 0 = ∞;

Выводим из базиса переменную с наименьшим положительным значением Q.

На пересечении строки, которая соответствует переменной что выводится из базиса, и столбца который соответствует переменной что вводится в базис, расположен разрешающий элемент.

Данный элемент позволит нам рассчитать элементы таблицы следующей итерации.

Итерация: 3

BCbPx1x2x3x4x5x6↓x7x8x9Q
3400000-M-M
x302450010-0.4-0.300.30-816.67
x40225000100000∞
x1
←		314010000.20.40-0.40350
x247501000-0.500.50-150
x9-M0000000-101∞
max72000000.6-0.8MM+0.80

Вычисление элементов таблицы:arrow down description
Элементы колонки базис(B)

За результатами вычислений предыдущей итерации убираем с базиса переменную x5 и ставим на ее место x1. Все остальные ячейки остаются без изменений.

Элементы колонки Cb

Каждая ячейка этого столбца равна коэффициенту, который соответствует базовой переменной в соответствующей строке.

Cb1 = 0;

Cb2 = 0;

Cb3 = 3;

Cb4 = 4;

Cb5 = -M;

Значения упрявляемых переменных и колонки P(В качестве исходных данных берутся данные из предыдущей итерации)

Заполняем нулями все ячейки, соответствующие переменной, которая только что была введена в базис:(Разрешающий элемент остается без изменений)

x1,1 = 0;

x2,1 = 0;

x4,1 = 0;

x5,1 = 0;

Переносим в текущую таблицу строку с разрешающим элементом с предыдущей таблицы, поэлементно поделив ее значения на разрешающий элемент:

P3 = P3 / x3,1 = 700 / 5 = 140;

x3,1 = x3,1 / x3,1 = 5 / 5 = 1;

x3,2 = x3,2 / x3,1 = 0 / 5 = 0;

x3,3 = x3,3 / x3,1 = 0 / 5 = 0;

x3,4 = x3,4 / x3,1 = 0 / 5 = 0;

x3,5 = x3,5 / x3,1 = 1 / 5 = 0.2;

x3,6 = x3,6 / x3,1 = 2 / 5 = 0.4;

x3,7 = x3,7 / x3,1 = 0 / 5 = 0;

x3,8 = x3,8 / x3,1 = -2 / 5 = -0.4;

x3,9 = x3,9 / x3,1 = 0 / 5 = 0;

Остальные пустые ячейки, за исключением строки оценок и колонки Q, рассчитываем методом прямоугольника, относительно разрешающего элемента:

P1 = (P1 * x3,1) - (x1,1 * P3) / x3,1 = ((525 * 5) - (2 * 700)) / 5 = 245;

P2 = (P2 * x3,1) - (x2,1 * P3) / x3,1 = ((225 * 5) - (0 * 700)) / 5 = 225;

P4 = (P4 * x3,1) - (x4,1 * P3) / x3,1 = ((75 * 5) - (0 * 700)) / 5 = 75;

P5 = (P5 * x3,1) - (x5,1 * P3) / x3,1 = ((0 * 5) - (0 * 700)) / 5 = 0;

x1,1 = ((x1,1 * x3,1) - (x1,1 * x3,1)) / x3,1 = ((2 * 5) - (2 * 5)) / 5 = 0;

x1,3 = ((x1,3 * x3,1) - (x1,1 * x3,3)) / x3,1 = ((1 * 5) - (2 * 0)) / 5 = 1;

x1,4 = ((x1,4 * x3,1) - (x1,1 * x3,4)) / x3,1 = ((0 * 5) - (2 * 0)) / 5 = 0;

x1,5 = ((x1,5 * x3,1) - (x1,1 * x3,5)) / x3,1 = ((0 * 5) - (2 * 1)) / 5 = -0.4;

x1,6 = ((x1,6 * x3,1) - (x1,1 * x3,6)) / x3,1 = ((0.5 * 5) - (2 * 2)) / 5 = -0.3;

x1,7 = ((x1,7 * x3,1) - (x1,1 * x3,7)) / x3,1 = ((0 * 5) - (2 * 0)) / 5 = 0;

x1,8 = ((x1,8 * x3,1) - (x1,1 * x3,8)) / x3,1 = ((-0.5 * 5) - (2 * -2)) / 5 = 0.3;

x1,9 = ((x1,9 * x3,1) - (x1,1 * x3,9)) / x3,1 = ((0 * 5) - (2 * 0)) / 5 = 0;

x2,1 = ((x2,1 * x3,1) - (x2,1 * x3,1)) / x3,1 = ((0 * 5) - (0 * 5)) / 5 = 0;

x2,3 = ((x2,3 * x3,1) - (x2,1 * x3,3)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x2,4 = ((x2,4 * x3,1) - (x2,1 * x3,4)) / x3,1 = ((1 * 5) - (0 * 0)) / 5 = 1;

x2,5 = ((x2,5 * x3,1) - (x2,1 * x3,5)) / x3,1 = ((0 * 5) - (0 * 1)) / 5 = 0;

x2,6 = ((x2,6 * x3,1) - (x2,1 * x3,6)) / x3,1 = ((0 * 5) - (0 * 2)) / 5 = 0;

x2,7 = ((x2,7 * x3,1) - (x2,1 * x3,7)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x2,8 = ((x2,8 * x3,1) - (x2,1 * x3,8)) / x3,1 = ((0 * 5) - (0 * -2)) / 5 = 0;

x2,9 = ((x2,9 * x3,1) - (x2,1 * x3,9)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x4,1 = ((x4,1 * x3,1) - (x4,1 * x3,1)) / x3,1 = ((0 * 5) - (0 * 5)) / 5 = 0;

x4,3 = ((x4,3 * x3,1) - (x4,1 * x3,3)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x4,4 = ((x4,4 * x3,1) - (x4,1 * x3,4)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x4,5 = ((x4,5 * x3,1) - (x4,1 * x3,5)) / x3,1 = ((0 * 5) - (0 * 1)) / 5 = 0;

x4,6 = ((x4,6 * x3,1) - (x4,1 * x3,6)) / x3,1 = ((-0.5 * 5) - (0 * 2)) / 5 = -0.5;

x4,7 = ((x4,7 * x3,1) - (x4,1 * x3,7)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x4,8 = ((x4,8 * x3,1) - (x4,1 * x3,8)) / x3,1 = ((0.5 * 5) - (0 * -2)) / 5 = 0.5;

x4,9 = ((x4,9 * x3,1) - (x4,1 * x3,9)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x5,1 = ((x5,1 * x3,1) - (x5,1 * x3,1)) / x3,1 = ((0 * 5) - (0 * 5)) / 5 = 0;

x5,3 = ((x5,3 * x3,1) - (x5,1 * x3,3)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x5,4 = ((x5,4 * x3,1) - (x5,1 * x3,4)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x5,5 = ((x5,5 * x3,1) - (x5,1 * x3,5)) / x3,1 = ((0 * 5) - (0 * 1)) / 5 = 0;

x5,6 = ((x5,6 * x3,1) - (x5,1 * x3,6)) / x3,1 = ((0 * 5) - (0 * 2)) / 5 = 0;

x5,7 = ((x5,7 * x3,1) - (x5,1 * x3,7)) / x3,1 = ((-1 * 5) - (0 * 0)) / 5 = -1;

x5,8 = ((x5,8 * x3,1) - (x5,1 * x3,8)) / x3,1 = ((0 * 5) - (0 * -2)) / 5 = 0;

x5,9 = ((x5,9 * x3,1) - (x5,1 * x3,9)) / x3,1 = ((1 * 5) - (0 * 0)) / 5 = 1;

Значение целевой функции

Рассчитываем значение целевой функции, поэлементно умножая столбик Cb на столбик P, сложив результаты произведений.

MaxP = (Cb1 * P1) + (Cb11 * P2 + (Cb21 * P3 + (Cb31 * P4 + (Cb41 * P5) = (0 * 245) + (0 * 225) + (3 * 140) + (4 * 75) + (-M * 0) = 720;

Оценки управляемых переменных

Рассчитываем оценки для каждой управляемой переменной, поэлементно умножив значение с колонки переменной, на значение с колонки Cb, суммируем результаты произведений, и с их суммы вычитаем коэффициент целевой функции, при этой переменной.

Maxx1 = ((Cb1 * x1,1) + (Cb2 * x2,1) + (Cb3 * x3,1) + (Cb4 * x4,1) + (Cb5 * x5,1) ) - kx1 = ((0 * 0) + (0 * 0) + (3 * 1) + (4 * 0) + (-M * 0) ) - 3 = 0;

Maxx2 = ((Cb1 * x1,2) + (Cb2 * x2,2) + (Cb3 * x3,2) + (Cb4 * x4,2) + (Cb5 * x5,2) ) - kx2 = ((0 * 0) + (0 * 0) + (3 * 0) + (4 * 1) + (-M * 0) ) - 4 = 0;

Maxx3 = ((Cb1 * x1,3) + (Cb2 * x2,3) + (Cb3 * x3,3) + (Cb4 * x4,3) + (Cb5 * x5,3) ) - kx3 = ((0 * 1) + (0 * 0) + (3 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx4 = ((Cb1 * x1,4) + (Cb2 * x2,4) + (Cb3 * x3,4) + (Cb4 * x4,4) + (Cb5 * x5,4) ) - kx4 = ((0 * 0) + (0 * 1) + (3 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx5 = ((Cb1 * x1,5) + (Cb2 * x2,5) + (Cb3 * x3,5) + (Cb4 * x4,5) + (Cb5 * x5,5) ) - kx5 = ((0 * -0.4) + (0 * 0) + (3 * 0.2) + (4 * 0) + (-M * 0) ) - 0 = 0.6;

Maxx6 = ((Cb1 * x1,6) + (Cb2 * x2,6) + (Cb3 * x3,6) + (Cb4 * x4,6) + (Cb5 * x5,6) ) - kx6 = ((0 * -0.3) + (0 * 0) + (3 * 0.4) + (4 * -0.5) + (-M * 0) ) - 0 = -0.8;

Maxx7 = ((Cb1 * x1,7) + (Cb2 * x2,7) + (Cb3 * x3,7) + (Cb4 * x4,7) + (Cb5 * x5,7) ) - kx7 = ((0 * 0) + (0 * 0) + (3 * 0) + (4 * 0) + (-M * -1) ) - 0 = M;

Maxx8 = ((Cb1 * x1,8) + (Cb2 * x2,8) + (Cb3 * x3,8) + (Cb4 * x4,8) + (Cb5 * x5,8) ) - kx8 = ((0 * 0.3) + (0 * 0) + (3 * -0.4) + (4 * 0.5) + (-M * 0) ) - -M = M+0.8;

Maxx9 = ((Cb1 * x1,9) + (Cb2 * x2,9) + (Cb3 * x3,9) + (Cb4 * x4,9) + (Cb5 * x5,9) ) - kx9 = ((0 * 0) + (0 * 0) + (3 * 0) + (4 * 0) + (-M * 1) ) - -M = 0;

Элементы колонки Q

Поскольку среди оценок управляемых переменных есть отрицательные значения, текущая таблица еще не имеет оптимального решения. Поэтому в базис введем переменную с наименьшей отрицательной оценкой.

Количество переменных в базисе всегда постоянно, поэтому необходимо выбрать, какую переменную вывести из базиса, для чего мы рассчитываем Q.

Элементы столбика Q рассчитываем поделив значения из колонки P на значение с колонки, соответствующие переменной которая вводится в базис:

Q1 = P1 / x1,6 = 245 / -0.3 = -816.67;

Q2 = P2 / x2,6 = 225 / 0 = ∞;

Q3 = P3 / x3,6 = 140 / 0.4 = 350;

Q4 = P4 / x4,6 = 75 / -0.5 = -150;

Q5 = P5 / x5,6 = 0 / 0 = ∞;

Выводим из базиса переменную с наименьшим положительным значением Q.

На пересечении строки, которая соответствует переменной что выводится из базиса, и столбца который соответствует переменной что вводится в базис, расположен разрешающий элемент.

Данный элемент позволит нам рассчитать элементы таблицы следующей итерации.

Итерация: 4

BCbPx1x2x3x4x5x6x7x8x9Q
3400000-M-M
x303500.75010-0.250000
x40225000100000
x603502.50000.510-10
x242501.251000.250000
x9-M0000000-101
max1000200010MM0

Вычисление элементов таблицы:arrow down description
Элементы колонки базис(B)

За результатами вычислений предыдущей итерации убираем с базиса переменную x1 и ставим на ее место x6. Все остальные ячейки остаются без изменений.

Элементы колонки Cb

Каждая ячейка этого столбца равна коэффициенту, который соответствует базовой переменной в соответствующей строке.

Cb1 = 0;

Cb2 = 0;

Cb3 = 0;

Cb4 = 4;

Cb5 = -M;

Значения упрявляемых переменных и колонки P(В качестве исходных данных берутся данные из предыдущей итерации)

Заполняем нулями все ячейки, соответствующие переменной, которая только что была введена в базис:(Разрешающий элемент остается без изменений)

x1,6 = 0;

x2,6 = 0;

x4,6 = 0;

x5,6 = 0;

Переносим в текущую таблицу строку с разрешающим элементом с предыдущей таблицы, поэлементно поделив ее значения на разрешающий элемент:

P3 = P3 / x3,6 = 140 / 0.4 = 350;

x3,1 = x3,1 / x3,6 = 1 / 0.4 = 2.5;

x3,2 = x3,2 / x3,6 = 0 / 0.4 = 0;

x3,3 = x3,3 / x3,6 = 0 / 0.4 = 0;

x3,4 = x3,4 / x3,6 = 0 / 0.4 = 0;

x3,5 = x3,5 / x3,6 = 0.2 / 0.4 = 0.5;

x3,6 = x3,6 / x3,6 = 0.4 / 0.4 = 1;

x3,7 = x3,7 / x3,6 = 0 / 0.4 = 0;

x3,8 = x3,8 / x3,6 = -0.4 / 0.4 = -1;

x3,9 = x3,9 / x3,6 = 0 / 0.4 = 0;

Остальные пустые ячейки, за исключением строки оценок и колонки Q, рассчитываем методом прямоугольника, относительно разрешающего элемента:

P1 = (P1 * x3,6) - (x1,6 * P3) / x3,6 = ((245 * 0.4) - (-0.3 * 140)) / 0.4 = 350;

P2 = (P2 * x3,6) - (x2,6 * P3) / x3,6 = ((225 * 0.4) - (0 * 140)) / 0.4 = 225;

P4 = (P4 * x3,6) - (x4,6 * P3) / x3,6 = ((75 * 0.4) - (-0.5 * 140)) / 0.4 = 250;

P5 = (P5 * x3,6) - (x5,6 * P3) / x3,6 = ((0 * 0.4) - (0 * 140)) / 0.4 = 0;

x1,1 = ((x1,1 * x3,6) - (x1,6 * x3,1)) / x3,6 = ((0 * 0.4) - (-0.3 * 1)) / 0.4 = 0.75;

x1,2 = ((x1,2 * x3,6) - (x1,6 * x3,2)) / x3,6 = ((0 * 0.4) - (-0.3 * 0)) / 0.4 = 0;

x1,3 = ((x1,3 * x3,6) - (x1,6 * x3,3)) / x3,6 = ((1 * 0.4) - (-0.3 * 0)) / 0.4 = 1;

x1,4 = ((x1,4 * x3,6) - (x1,6 * x3,4)) / x3,6 = ((0 * 0.4) - (-0.3 * 0)) / 0.4 = 0;

x1,5 = ((x1,5 * x3,6) - (x1,6 * x3,5)) / x3,6 = ((-0.4 * 0.4) - (-0.3 * 0.2)) / 0.4 = -0.25;

x1,6 = ((x1,6 * x3,6) - (x1,6 * x3,6)) / x3,6 = ((-0.3 * 0.4) - (-0.3 * 0.4)) / 0.4 = 0;

x1,8 = ((x1,8 * x3,6) - (x1,6 * x3,8)) / x3,6 = ((0.3 * 0.4) - (-0.3 * -0.4)) / 0.4 = 0;

x1,9 = ((x1,9 * x3,6) - (x1,6 * x3,9)) / x3,6 = ((0 * 0.4) - (-0.3 * 0)) / 0.4 = 0;

x2,1 = ((x2,1 * x3,6) - (x2,6 * x3,1)) / x3,6 = ((0 * 0.4) - (0 * 1)) / 0.4 = 0;

x2,2 = ((x2,2 * x3,6) - (x2,6 * x3,2)) / x3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x2,3 = ((x2,3 * x3,6) - (x2,6 * x3,3)) / x3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x2,4 = ((x2,4 * x3,6) - (x2,6 * x3,4)) / x3,6 = ((1 * 0.4) - (0 * 0)) / 0.4 = 1;

x2,5 = ((x2,5 * x3,6) - (x2,6 * x3,5)) / x3,6 = ((0 * 0.4) - (0 * 0.2)) / 0.4 = 0;

x2,6 = ((x2,6 * x3,6) - (x2,6 * x3,6)) / x3,6 = ((0 * 0.4) - (0 * 0.4)) / 0.4 = 0;

x2,8 = ((x2,8 * x3,6) - (x2,6 * x3,8)) / x3,6 = ((0 * 0.4) - (0 * -0.4)) / 0.4 = 0;

x2,9 = ((x2,9 * x3,6) - (x2,6 * x3,9)) / x3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x4,1 = ((x4,1 * x3,6) - (x4,6 * x3,1)) / x3,6 = ((0 * 0.4) - (-0.5 * 1)) / 0.4 = 1.25;

x4,2 = ((x4,2 * x3,6) - (x4,6 * x3,2)) / x3,6 = ((1 * 0.4) - (-0.5 * 0)) / 0.4 = 1;

x4,3 = ((x4,3 * x3,6) - (x4,6 * x3,3)) / x3,6 = ((0 * 0.4) - (-0.5 * 0)) / 0.4 = 0;

x4,4 = ((x4,4 * x3,6) - (x4,6 * x3,4)) / x3,6 = ((0 * 0.4) - (-0.5 * 0)) / 0.4 = 0;

x4,5 = ((x4,5 * x3,6) - (x4,6 * x3,5)) / x3,6 = ((0 * 0.4) - (-0.5 * 0.2)) / 0.4 = 0.25;

x4,6 = ((x4,6 * x3,6) - (x4,6 * x3,6)) / x3,6 = ((-0.5 * 0.4) - (-0.5 * 0.4)) / 0.4 = 0;

x4,8 = ((x4,8 * x3,6) - (x4,6 * x3,8)) / x3,6 = ((0.5 * 0.4) - (-0.5 * -0.4)) / 0.4 = 0;

x4,9 = ((x4,9 * x3,6) - (x4,6 * x3,9)) / x3,6 = ((0 * 0.4) - (-0.5 * 0)) / 0.4 = 0;

x5,1 = ((x5,1 * x3,6) - (x5,6 * x3,1)) / x3,6 = ((0 * 0.4) - (0 * 1)) / 0.4 = 0;

x5,2 = ((x5,2 * x3,6) - (x5,6 * x3,2)) / x3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x5,3 = ((x5,3 * x3,6) - (x5,6 * x3,3)) / x3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x5,4 = ((x5,4 * x3,6) - (x5,6 * x3,4)) / x3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x5,5 = ((x5,5 * x3,6) - (x5,6 * x3,5)) / x3,6 = ((0 * 0.4) - (0 * 0.2)) / 0.4 = 0;

x5,6 = ((x5,6 * x3,6) - (x5,6 * x3,6)) / x3,6 = ((0 * 0.4) - (0 * 0.4)) / 0.4 = 0;

x5,8 = ((x5,8 * x3,6) - (x5,6 * x3,8)) / x3,6 = ((0 * 0.4) - (0 * -0.4)) / 0.4 = 0;

x5,9 = ((x5,9 * x3,6) - (x5,6 * x3,9)) / x3,6 = ((1 * 0.4) - (0 * 0)) / 0.4 = 1;

Значение целевой функции

Рассчитываем значение целевой функции, поэлементно умножая столбик Cb на столбик P, сложив результаты произведений.

MaxP = (Cb1 * P1) + (Cb11 * P2 + (Cb21 * P3 + (Cb31 * P4 + (Cb41 * P5 = (0 * 350) + (0 * 225) + (0 * 350) + (4 * 250) + (-M * 0) = 1000;

Оценки управляемых переменных

Рассчитываем оценки для каждой управляемой переменной, поэлементно умножив значение с колонки переменной, на значение с колонки Cb, суммируем результаты произведений, и с их суммы вычитаем коэффициент целевой функции, при этой переменной.

Maxx1 = ((Cb1 * x1,1) + (Cb2 * x2,1) + (Cb3 * x3,1) + (Cb4 * x4,1) + (Cb5 * x5,1) ) - kx1 = ((0 * 0.75) + (0 * 0) + (0 * 2.5) + (4 * 1.25) + (-M * 0) ) - 3 = 2;

Maxx2 = ((Cb1 * x1,2) + (Cb2 * x2,2) + (Cb3 * x3,2) + (Cb4 * x4,2) + (Cb5 * x5,2) ) - kx2 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 1) + (-M * 0) ) - 4 = 0;

Maxx3 = ((Cb1 * x1,3) + (Cb2 * x2,3) + (Cb3 * x3,3) + (Cb4 * x4,3) + (Cb5 * x5,3) ) - kx3 = ((0 * 1) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx4 = ((Cb1 * x1,4) + (Cb2 * x2,4) + (Cb3 * x3,4) + (Cb4 * x4,4) + (Cb5 * x5,4) ) - kx4 = ((0 * 0) + (0 * 1) + (0 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx5 = ((Cb1 * x1,5) + (Cb2 * x2,5) + (Cb3 * x3,5) + (Cb4 * x4,5) + (Cb5 * x5,5) ) - kx5 = ((0 * -0.25) + (0 * 0) + (0 * 0.5) + (4 * 0.25) + (-M * 0) ) - 0 = 1;

Maxx6 = ((Cb1 * x1,6) + (Cb2 * x2,6) + (Cb3 * x3,6) + (Cb4 * x4,6) + (Cb5 * x5,6) ) - kx6 = ((0 * 0) + (0 * 0) + (0 * 1) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx7 = ((Cb1 * x1,7) + (Cb2 * x2,7) + (Cb3 * x3,7) + (Cb4 * x4,7) + (Cb5 * x5,7) ) - kx7 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * -1) ) - 0 = M;

Maxx8 = ((Cb1 * x1,8) + (Cb2 * x2,8) + (Cb3 * x3,8) + (Cb4 * x4,8) + (Cb5 * x5,8) ) - kx8 = ((0 * 0) + (0 * 0) + (0 * -1) + (4 * 0) + (-M * 0) ) - -M = M;

Maxx9 = ((Cb1 * x1,9) + (Cb2 * x2,9) + (Cb3 * x3,9) + (Cb4 * x4,9) + (Cb5 * x5,9) ) - kx9 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 1) ) - -M = 0;

Ответ:

Поскольку среди оценок управляемых переменных нет отрицательных значений, текущая таблица имеет оптимальное решение.

Значение целевой функции:

F* = 1000

Переменные которые присутствуют в базисе, равны соответствующим ячейкам колонки P, все остальные переменные равны нулю:

x1 = 0;

x2 = 250;

Ответ:

F* = 1000

X* = (0; 250)

Условные обозначения:arrow down description
xi↓ - вводим переменную в базис;
xi
←		 - выводим переменную с базиса;
xi - разрешительный елемент;
xi - базисной елемент;
B - базис;
Cb - коэффициент при базисной переменной;
P - план;

Мобильное приложение:

Симплекс Метод
Simplex Method

Решай задачи линейного программирования в режиме offline - без доступа к интернету!

Google Play Icon1App Store Icon