Решение. Найдём решение прямой задачи, приведя её к каноническому виду

Найдём решение прямой задачи, приведя её к каноническому виду. Там, где знак вводим дополнительную переменную со знаком плюс, а там где знак вводим дополнительную переменную со знаком минус, при этом ещё вводим искусственный базис. Запишем данную математическую модель в каноническом виде.

Решим данную задачу симплекс – методом.

В индексной строке выбираем наибольшую по модулю отрицательную оценку (-2), выделяем столбец. У нас это второй столбец. Находим оценочные отношения: делим столбец С на столбец Е и выбираем наименьшее отношение – у нас это 1,5. Выделяем первую строку. Выводим из базиса переменную , при этом в базис вводим переменную . Делим выделенную строку на ключевой элемент, т.е. на 4. Записываем пересчитывающие коэффициенты в последний столбец - делением генерального столбца на ключевой элемент, кроме строки с ключевым элементом. Все остальные элементы пересчитываем по методу Гаусса. В результате перейдём к следующей симплекс – таблице.

Так как в индексной строке есть отрицательная оценка, следовательно, требуется улучшение оптимального плана. Выделяем столбец с отрицательной оценкой – это первый столбец. Находим оценочные отношения, делением столбца В на столбец , выбираем наименьшее отношение – это третья строка с отношением 3,14, выделяем её. Из базиса выводим переменную , при этом в базис вводим переменную . Аналогично пересчитываем все невыделенные элементы. Получим новую симплекс – таблицу.

Снова требуется улучшение оптимального плана, так как не выведен искусственный базис. Выводим его, при этом в базис вводим переменную .

Так как в индексной строке все элементы положительные или равны нулю, получили оптимальный план.

Решим двойственную задачу прямой задачи.

Правило построения двойственной задачи состоит в следующем. Каждому равенству прямой задачи соответствует двойственная переменная

Стрелки показывают, что первому равенству соответствует переменная , второму – переменная , третьему .

Для определения целевой функции двойственной задачи двойственные переменные , и умножаются на правые части равенств и складываются:

.

Каждой переменной прямой задачи , соответствует ограничение двойственной задачи. Левые части этих ограничений для переменной записываются следующим образом. Двойственные переменные , и умножаются на коэффициенты перед переменной и складываются: .

Аналогично, записываются левые части ограничений для переменной . Двойственные переменные , и умножаются на коэффициенты перед переменной и складываются: .

Для переменной .

Левая часть ограничений для переменной равна , а для переменной , для переменной . Правые части ограничений равны коэффициентам 1, 2, -1 целевой функции .

Перед переменными , левые и правые части ограничений соединяются знаком .

В результате математическая модель двойственной задачи имеет вид:

найти двойственные переменные , , при которых целевая функция минимальна

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

Переменные , называются допустимым решением двойственной задачи, если они удовлетворяют всем ограничениям и оптимальными, если они допустимые и на них целевая функция достигает минимума.

Решим данную задачу симплекс – методом, для этого приведём математическую модель задачи к канонической форме. Введём дополнительные переменные .

Но коэффициенты при новых переменных отрицательны, так как знак , а решения симплекс-методом все коэффициенты при базисных переменных должны быть равны (+1), поэтому вводим три искусственные базиса .

Строим симплекс таблицу. Так как задача на нахождения минимального значения, то в индексной строке выбираем наибольшую по модулю отрицательную оценку – это первый столбец, выделяем его. Далее находим оценочные отношения, из них выбираем наименьшее, выделим эту строку – у нас это третья строка, а также вычислим коэффициенты в последнем столбце.

Итерации проводим до тех пор, пока в индексной строке не будут все отрицательные элементы либо равны нулю.

Так как в индексной строке все элементы меньше или равны нулю, получен оптимальный план.

Сравнивая прямую и двойственную задачи, видим, что целевые функции равны: , а это значит, что полученное решение верно.

Дата добавления: 2015-07-19