Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Лабораторки / PM_Praktika_2013 / ПМ Практика 2013 / Методические указания / Лабораторная работа 2 -СимплТабл

.doc
Скачиваний:
17
Добавлен:
01.04.2015
Размер:
400.38 Кб
Скачать

Лабораторная работа 2

Симплексный метод решения задач линейного программированияс помощью симплекс- таблиц

Постановка задачи

Найти симплексным методом минимум целевой функции

F = x1+ x2®min

при ограничениях

Решение с помощью симплекс-таблиц.

Записываем постановку задачи в канонической форме:

Знак “-” перед новой переменной учитывается, если исходное неравенство ≥. Знак “+” перед новой переменной, если исходное неравенство ≤.

На листе Excel следует записать условие задачи своего варианта в общем виде и в канонической форме. Составляем симплекс-таблицу 1:

Полагая переменные х1 = 0 и х2 = 0, находим базисное решение:

Х1 = (0; 0; 4; 0; -4).

Базисное решение не допустимое (x5< 0).

Выбираем ведущей строкой х5, так как x5< 0.

В качестве ведущего столбца выбираем х1 .

Найдем оценочные отношения.

Из оценочных отношений следует выбирать положительную и минимальную. В данном случае положительные оценочные отношения одинаковы (равны 4), можно выбрать любую. Например, в строке х3 . Строка х3 становится ведущей.

Ведущий элемент равен 1.

Строим симплекс-таблицу 2.

В базисе меняем х3 на х1 .

Столбец х1 заполняем нулями и 1 на месте ведущего элемента.

Ведущую строку делим на ведущий элемент (на 1).

В ведущей строке содержатся нули. Соответствующие столбцы можно переписать.

Остальные элементы рассчитываем по правилу прямоугольника в соответствии с методом Гаусса.

Полагая переменные х2 = 0 и х3 = 0, находим базисное решение:

Х2 = (4; 0; 0; 12; 0;).

Замечание: в базисном решении х4 = (-12) / (-1) = 12.

Базисное решение допустимое .

В качестве ведущего столбца выбираем х3 .

Найдем оценочные отношения.

Из оценочных отношений следует выбирать положительное и минимальное.

В данном случае положительные оценочные отношения одинаковы (равны 4), можно выбрать любую. Например, в строке х4 . Строка х4 становится ведущей.

Ведущий элемент равен - 3.

Симплекс-таблицу 3 строим по тому же алгоритму.

Полагая переменные х2 = 0 и х4 = 0, находим базисное решение:

Х3 = (0; 0; 4; 0; -4).

Базисное решение не допустимое (x5< 0).

Замечание: в базисном решении х5 = 4 / (-1) = - 4.

В качестве ведущей строки выберем х5 , а в качестве ведущего столбца х2, так как только при таком выборе получим минимальное положительное оценочное отношение.

Симплекс-таблицу 4 строим по тому же алгоритму.

Полагая переменные х4 = 0 и х5 = 0, находим базисное решение:

Х4 = (1; 3; 15; 0; 0).

Базисное решение допустимое.

Все коэффициенты последней строки неположительны. с5= -1 и остальные равны нулю. Следовательно, критерий оптимальности выполнен.

Ответ: Fmin = 4 при х1 = 1 и х2 = 3.

Базисное решение Х* = (1; 3; 15; 0; 0) следует запомнить для решения двойственной задачи.

Замечание: ответ можно было получить уже в 3-ей симплекс-таблице, если в симплекс-таблице 1 выбрать в качестве ведущей строки х5 вместо х3 .

9