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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ЭКОНОМИКИ И ПРЕДПРИНИМАТЕЛЬСТВА

Кафедра «Информационной безопасности»

ОТЧЕТ

по лабораторной работе:

«Решение линейной задачи оптимизации производства симплексным методом»

Выполнил: Лазарев А.А.

группа ЭиП-520

Проверил: Баландин А.В.

Челябинск 2008

Задание:

Задана линейная модель задачи оптимизации проектного решения в виде:

,

при условиях

;

    

Необходимо найти оптимальное решение данной задачи линейного программирования.

Прежде всего, перейдём от системы неравенств к системе уравнений. Для этого введём добавочные переменные x₅, x₆, x₇, x₈ (   ):

Далее находим первоначальный опорный план (допустимое базисное решение) методом искусственного базиса.

Если в качестве базиса взять x₅, x₆, x₇, x₈, то x₁, x₂, x₃, x₄ будут свободными. Положим свободные переменные равными нулю, тогда будет получено следующее базисное решение {450, 80, 1400, -2000}. Это решение не является допустимым, так как x₈<0.

Применяем метод искусственного базиса.

Введём в четвертое уравнение искусственную переменную x₉ и решим вспомогательную задачу линейного программирования, заключающуюся в минимизации целевой функции f(x)=x₉ (что эквивалентно максимизации целевой функции f*(x)=-f(x)=-x₉).

Первоначальное допустимое базисное решение для вспомогательной задачи будет

{x₅, x₆, x₇, x₉} = {450, 80, 1400, 2000}.

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

Проведем преобразования:

Так как f≠0 задача не имеет решений.