Решение задачи лп симплексным методом
В качестве проверки представлено графическое решение задачи по нахождению (оптимальное решение находится путем параллельного переноса целевой функции на графике). Все элементы разрешающего столбца j делятся на разрешающий элемент и меняют знак на противоположный. В таблице выделяется разрешающий элемент на пересечении i-й строки и j-го столбца (aij). Преобразования осуществляются в симплексной… Читать ещё >
Решение задачи лп симплексным методом (реферат, курсовая, диплом, контрольная)
Симплексный метод основан на идее перехода от одного базисного решения в вершине многоугольника допустимых решений к другому базисному решению, более близкому к оптимальному.
Выразим базисные переменные через свободные:
y1 = 20 +5×1 — 4×2;
y2 = 24 -2×1 — 3×2;
y3 = 3 — 1×1 + 3×2;
y4 = 8 — 1×1 — 0×2;
y5 = 6 — 0×1 — 1×2;
Каждая строка симплекс-таблицы соответствует базисной переменной, а каждому столбцу соответствует свободная переменная xj и выделен столбец свободных членов (правых частей ограничений) bi. Внизу помещена строка целевой функции F.
Преобразования осуществляются в симплексной таблице по следующему алгоритму:
В таблице выделяется разрешающий элемент на пересечении i-й строки и j-го столбца (aij).
Разрешающий элемент заменяется на обратную величину.
Все остальные элементы разрешающей строки i делятся на разрешающий элемент.
Все элементы разрешающего столбца j делятся на разрешающий элемент и меняют знак на противоположный.
Все остальные элементы, не принадлежащие разрешающим столбцу и строке, вычисляются по правилу «прямоугольника». Мысленно выделяется прямоугольник, в котором подлежащий пересчету элемент и разрешающий элемент образуют одну из диагоналей. Из произведения этих элементов вычитается произведение элементов, образующих другую диагональ прямоугольника, а результат делится на разрешающий элемент.
В качестве разрешающего берется тот элемент выбранного столбца, который имеет одинаковый знак со свободным членом, и для которого симплексное соотношение минимально. После преобразований просматривается строка целевой функции F, и если среди ее коэффициентов, не считая свободного члена c0, все элементы положительны, то оптимальное решение достигнуто.
Решение задачи симплексным методом:
— x1. | — x2. | B. | ||
y1. | — 5. | |||
y2. | ||||
y3. | — 3. | |||
y4. | ||||
y5. | ||||
Fmax. | — 3. | — 2. | ||
Разрешающий элемент — А (3;1);
— y3. | — x2. | B. | ||
y1. | 4−15. | 20+15. | ||
y2. | — 2. | 3+6. | 24−6. | |
x1. | — 3. | |||
y4. | — 1. | 8−3. | ||
y5. | ||||
Fmax. | — 2−9. | |||
— y3. | — x2. | B. | ||
y1. | — 11. | |||
y2. | — 2. | |||
x1. | — 3. | |||
y4. | — 1. | |||
y5. | ||||
Fmax. | — 11. | |||
Разрешающий элемент — А (4;2);
— y3. | — y4. | B. | ||
y1. | 4/3. | 11/3. | 160/3. | |
y2. | — 9/3. | 9/3. | ||
x1. | 3/3. | 24/3. | ||
x2. | — 1/3. | 1/3. | 5/3. | |
y5. | 1/3. | — 1/3. | 13/3. | |
Fmax. | — 2/3. | 11/3. | 82/3. | |
— y3. | — y4. | B. | ||
y1. | 1.3. | 3.7. | 53.3. | |
y2. | — 3. | |||
x1. | ||||
x2. | — 0.33. | 0.33. | 1.7. | |
y5. | 0.33. | — 0.33. | 4.3. | |
Fmax. | — 0.67. | 3.7. | 27.3. | |
Разрешающий элемент — А (2;1);
— y2. | — y4. | B. | ||
y1. | — 1.3. | 4+3.7. | 148/3. | |
y3. | — 3. | |||
x1. | ||||
x2. | 0.33. | 1/3−1. | 8/3. | |
y5. | — 0.33. | — 1/3+1. | 10/3. | |
Fmax. | 0.67. | 5/3. | 88/3. | |
— y2. | — y4. | B. | ||
y1. | — 1.3. | 7.7. | 49.3. | |
y3. | — 3. | |||
x1. | ||||
x2. | 0.33. | — 0.67. | 2.7. | |
y5. | — 0.33. | 0.67. | 3.3. | |
Fmax. | 0.67. | 1.7. | 29.3. | |
В качестве проверки представлено графическое решение задачи по нахождению (оптимальное решение находится путем параллельного переноса целевой функции на графике).
Функция максимальна в точке (8.0,2.7). Fmax (8.0,2.7)=29.33.