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

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

Дана следующая задача линейного программирования (ЗЛП).

,

1.1. Все ограничения задачи .

1.2. Переменная  ограниченна в знаке, поэтому . Переменная  не ограничена в знаке, поэтому вводим замену , где .

Область допустимых решений будет ограничиваться I и IV квадрантом.

1.3. Построение ограничений и градиента целевой функции :

1.4. Область допустимых решений – отрезок AB.

1.5. Точка А – оптимальная. Координаты т. А:

; ; .

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

Прямая задача.

Задачу линейного программирования для любой вершины в компактной форме можно представить в виде:

Для получения используем алгоритм, приведённый в теоретической части.

1. Переход от неравенств к равенствам по правилам введения дополнительных переменных. Исходную задачу необходимо привести к стандартной форме: введем замену по переменной , и дополнительные переменные:

,

Полученный вид ЗЛП не позволяет сформировать начальный допустимый базис, т. к. нельзя выделить единичные орты во втором и третьем равенствах. Для получения начального допустимого базиса введём искусственные переменные. В результате получим:

,

2. Общее число переменных определим по формуле: =3+2+2=7, где  - число искусственных переменных. Число базисных переменных определяется числом ограничений, т. к. , то система имеет три базисные переменные  и  небазисные переменные .

3. Получение - строки для СТ (0). Приведём целевую функцию к виду

.

Получим из (2): , из (3):

4. Формирование симплекс – таблицы на первом шаге:

Начальный базис

СТ (0) РС

5. Определение разрешающего столбца.

При решении задачи максимизации выбираем в  - строке максимально отрицательный коэффициент:  - включаемая переменная.

6. Определение разрешающей строки:  – исключаемая переменная.

7. Разрешающий элемент РЭ = 1.

8. Получение матрицы перехода

, где В(0) - матрица перехода

9. Определение элементов таблицы СТ(1) = В(0) СТ(0);

10. Исследование z-строки СТ(1) на условие оптимальности:

СТ(1)

СТ(2)

СТ(2) – оптимальная, т. к. коэффициенты при НБП.

, , .

Похожие работы

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

Скачать

36149

6

0

... положит в такой симплекс-таблице текущие базисные переменные равными Ai,0, а свободные - нулю, то будет получено оптимальное решение. Практика применения симплекс метода показала, что число итераций, требуемых для решения задачи линейного программирования обычно колеблется от 2m до 3m, хотя для некоторых специально построенных задач вычисления по правилам симплекс метода превращаются в прямой ...

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

Скачать

15921

4

2

... и подставляя её во всех остальных равенствах и неравенствах (а также в функции f).Такую задачу называют «основной» или «стандартной» в линейном программировании.   1.2 Решение задач линейного программирования симплекс-методом   Задача ЛП в общем виде может быть записана так: (c, x) − max Ax = b, где c =(c1,c2,...,cn)T – мерный вектор-столбец коэффициентов; x =(x1,x2,...,xn)T – ...

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

Скачать

82416

8

19

... 0 505/103 0 792/103 669/103 500/103 Анализ Таблицы 6 позволяет сделать вывод о допустимости и оптимальности базиса XБ4=(x5, x7, x1, x2, x4)T. 3.4 Результат решения задачи планирования производства В результате решения поставленной задачи симплекс-методом получили набор производимой продукции x=(x1, x2, x3, x4, x5)=( 15145/103, 8910/103, 0, 1250/103, 3255/103), который удовлетворяет всем ...

Решение задач линейного программирования

Скачать

7936

3

0

...  - формула (1.2), ограничений не отрицательности переменных (есть, нет) - формула (1.3) (1.1)    i = 1,… m  (1.2) (1.3) Алгоритм решения задач линейного программирования требует приведения их постановки в канонический вид, когда целевая функция ...