Лабораторная работа №5. Реализация пошагового алгоритма решения задачи линейного программирование методом искусственного базиса (м-методом) средствами Excel

Задание. Реализуйте все нижеприведенные шаги в табличном процессоре Excel, необходимые для решения задачи ЛП табличным симплекс-методом, применяя метод искусственного базиса.

Поясним последовательность действий при решения задачи ЛП методом искусственного базиса (М-методом) на примере.

Задача. Решить задачу табличным симплекс-методом [8].

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

Порядок выполнения работы:

I. Проверка выполнения условий, необходимых для решения задачи табличным симплекс-методом.

1. .

2. Задача не является канонической, приведите ее к канонической форме.

Переведите исходную функцию на максимум.

Избавьтесь от неравенств во втором и третьем ограничении способом, указанным в 2.1.

3. В ограничениях 1 и 2 есть базисные переменные: - в первом,- во втором, в третьем ограничении нет базисной переменной, следовательно, необходимо применить М-метод.

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

Расширенная задача:

,

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

,

.

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

,

II. Оформление исходных данных.

1. Откройте табличный процессор Excel и введите заголовок Метод искусственного базиса.

2. Заполните начальную симплекс-таблицу, таким же образом как в лабораторной работе №4, добавив в нее столбец для переменной и-строку (рис. 42).

Рис. 42. Исходная симплекс таблица.

11. Проконтролируйте правильность заполнения таблицы. Так как ,,- базисные переменные, то на пересечении(5 строка) с (столбецF) должна стоять 1 (ячейка F5), а в соответствующем столбце ниже – нули, на пересечении (6 строка) с (столбецG) должна стоять 1 (ячейка G6), а в соответствующем столбце ниже – нули, (7 строка) с (столбецI) должна стоять 1 (ячейка I7), а в соответствующем столбце ниже – нули.

3. Запишите значение целевой функции, начальный опорный план, опираясь на столбец свободных членов (рис. 43).

Рис. 43. Значение целевой функции и начальный опорный план.

III. Нахождение оптимального плана и оптимального значения целевой функции.

1. Так в индексной строке есть отрицательный коэффициент при переменной, то опорный план не является оптимальным. Организуйте процесс улучшения плана, выполнив предложенные шаги.

2. В индексной строке найдите отрицательные элементы. Составьте выражения, учитывая -строку. Получите.

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

3. Соответствующий столбец назовите ведущим. Данный столбец показывает, какую переменную необходимо включить в базис (рис. 44).

Рис. 44. Ведущий столбец.

4. Определите какую переменную необходимо исключить из базиса. Для этого составьте отношения для всех элементов столбца свободных членов () к соответствующим элементам ведущего столбца (). Найдите ведущую строку и ведущий элемент (рис. 45).

Рис. 45. Ведущая строка и ведущий столбец.

5. Постройте новую симплексную таблицу. Выведите переменную из базиса, на ее место запишите ту переменную, которой соответствует ведущий столбец. Выполните симплексные преобразования, таким же образом, как и в лабораторной №4, получите базисный столбец, который соответствует переменной. Значения столбцаможно удалить, так как переменная вышла из базиса (рис. 46).

Рис. 46. Первая и вторая симплексные таблицы.

6. Так как в -строке все нули, то ее можно удалить из таблицы и получить таблицу, в которой будет только функция(рис. 47).

Рис. 47. Симплексная таблица.

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

8. Запишите значение целевой функции, найденный новый опорный план, опираясь на столбец свободных членов (рис. 48). Проконтролируйте, что значение целевой функции максимизируется.

9. Организуйте процесс улучшения плана, выполнив те же шаги, до тех пор, пока не будет выполняться какой-нибудь из критериев остановки, получите новую таблицу (рис. 48).

Рис. 48. Симплексные таблицы.

10. В индексной строке нет отрицательных элементов, поэтому план оптимален,. Так как в исходной задаче функция стремится к минимуму, то

Задание. Воспользуйтесь материалами лабораторной работы №3. Выполните проверку, используя программу MathCad.