Приводим задачу к каноническому виду: если знак «≤», то добавляем xi, если знак «≥», то вычитаем xi. Если ищется максимум целевой функции, то коэффициенты при xi умножаем на (-1) и устремляем функцию к минимуму:
У нас получилось 5 переменных: х1, х2, х3, х4, х5. Разбиваем переменные на два вида: базисные и небазисные. Количество базисных переменных равно числу ограничении, т.е. равно трем. Остальные переменные - небазисные.
2. Составляем начальную симплекс таблицу, т. е. выражаем базисные переменные через небазисные, так чтобы свободные члены в уравнении были неотрицательные.
Выразим переменную х1 из (2.6) и подставим в (2.7) и (2.8). Тогда из (2.7) легко найти х4, из (2.8) найдем х5. Подставив x1 в целевую функцию, получим:
х1 = 1+2х2-х3; (2.9)
x4= 4 + 3x2-2x3; (2.10)
х5 = 3х3-7х2. (2.11)
q= 1+2x2 – х3 - х2 = 1 + х2 - х3 → тin;
Получили, что x1, x4 и x5 - базисные переменные, а х2 и х3 - небазисные. Затем небазисные переменные х2 и х3 приравниваем к нулю, подставляем в получившиеся уравнения и находим значения базисных переменных и целевой функции. Таким образом, получили симплекс-таблицу для первой базисной точки:
|
|
x1 | x2 | x3 | х4 | х5 | q |
Полученная базисная точка соответствует координатам точки С(1;0) (см. рис. 1.1). Так как в полученной целевой функции есть отрицательный коэффициент при х3, то оптимальное решение еще не найдено, поэтому переходим к новому базису.
3. В соответствии с правилом 1 в базис переводим переменную х3, так как она имеет отрицательный знак в целевой функции. В соответствии с правилом 2:
a13=1 b1=1 b1/a13=1-min,
a43=2 b4=4 b4/a43 =2,
а53=-3 b5=0 a53<0.
Из базиса исключаем x1, т. к. ему соответствует минимальное значение.
Выражаем переменную х3 из уравнения (2.9) и подставляем в остальные уравнения и целевую функцию.
q = х1-х2→тin;
Небазисные переменные x1 и х2 приравниваем к нулю, подставляем в получившиеся уравнения и находим значения базисных переменных и целевой функции. Таким образом, получили симплекс-таблицу для базисной точки:
х1 | x2 | x3 | х4 | х5 | q |
Полученная базисная точка соответствует координатам точки C(0; 0) (см. рис. 1.1). Так как в полученной целевой функции есть отрицательные коэффициент при х2, то оптимальное решение еще не найдено, поэтому переходим к новому базису.
4. В соответствии с правилом 1 в базис переводим переменную х2, так как она имеет отрицательный знак в целевой функции. В соответствии с правилом 2:
a32 = -2 b3 = 1 a32 < 0;
a42 = 1 b4 = 2 b3/a42 = 2 – min;
a52 = 1 b5 = 3 b5/a52 = 3.
Из базиса исключаем х4, т. к. ему соответствует минимальное значение.
Выражаем переменную х2 из уравнения (2.13) и подставляем в остальные уравнения и целевую функцию.
|
|
q = - 2 + х4 – х1 →min;
Небазисные переменные x1 и х4 приравниваем к нулю, подставляем в получившиеся уравнения и находим значения базисных переменных и целевой функции. Таким образом, получили симплекс таблицу для третьей базисной точки:
x1 | x2 | x3 | х4 | х5 | q |
-2 |
Полученная базисная точка соответствует координатам точки A(О; 2) (см. рис. 1.1). Так как в полученной целевой функции есть отрицательный коэффициент при x1, то оптимальное решение еще не найдено, поэтому переходим к новому базису.
5. В соответствии с правилом 1 в базис переводим переменную x1, так как она имеет отрицательный знак в целевой функции. В соответствии с правилом 2:
a31 =2 b3=5 b3/a31 =5/2,
a21 =1 b2=2 b2/a21 =2,
a51 =5 b5=1 b5/a51 =1/5 – min,
из базиса исключаем x5, т. к. ему соответствует минимальное значение.
Выражаем переменную x1 из уравнения (2.17) и подставляем в остальные уравнения и целевую функцию.
q = -2,2+0,8 х4+ 0,2 х5 → min;
Небазисные переменные х4 и х5 приравниваем к нулю, подставляем в получившиеся уравнения и находим значения базисных переменных и целевой функции. Таким образом, получили симплекс-таблицу для четвёртой базисной точки:
х1 | х2 | хЗ | х4 | х5 | q |
0,2 | 2,4 | 5,6 | -2, 2 |
Полученная базисная точка соответствует координатам точки B(0,2; 2,4) (см. рис. 1.1).
Так как полученная целевая функция не содержит отрицательных коэффициентов при х, то оптимальное решение найдено.
Ответ: х1=0,2; х2=2,4: q=-22.
Контрольные вопросы и задания
1. Как записывается каноническая форма задачи линейного программирования?
2. Какие переменные называются базисными?
3. В каком случае решение считается найденным?
4. Всегда ли существует решение задачи линейного программирования? В каком случае у задачи нет решения?
5. Какие значения принимают небазисные переменные в базисной точке?