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

,

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

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

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

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

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

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

; ; .

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

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

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

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

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

,

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

,

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

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

.