№5. Использование табличного симплекс-метода для решения задач линейного программирования

Цель: сформировать умение решать задачу линейного программирования симплексным методом с использованием табличного процессора MS EXCEL.

Оборудование: практикум, тетрадь для лабораторных и практических работ.

Литература:

1. Колеснев В. И. Экономико-математические методы и модели в сфере АПК. Ч. 1. - Мн.: УМЦ, 2006. С. 43-52.
2. Плотников А. Д. Математическое программирование: экспресс-курс. - Мн.: Новое знание, 2007. С. 68-78.

Время выполнения: 2 часа.

ВОПРОСЫ ВХОДНОГО КОНТРОЛЯ:

1. Опишите суть симплекс-метода решения задачи линейного программирования.
2. Опишите процесс приведения задачи линейного программирования к канонической форме записи.
3. Дайте определение базисного решения системы линейных уравнений.
4. Дайте определение опорного решения задачи линейного программирования.
5. Опишите процесс проверки опорного плана решения задачи линейного программирования на оптимальность.
6. Объясните правило прямоугольника, используемое при решении систем линейных уравнений методом Жордана-Гаусса.

КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ:

Алгоритм решения задачи линейного программирования симплексным методом (поиск максимума)

1) представить задачу линейного программирования в канонической форме;

2) определить исходное опорное решение;

3) получить нулевое уравнение (выразить имеющиеся в целевой функции базисные переменные через свободные, затем перенести все переменные в левую часть выражения);

4) составить симплекс-таблицу;

5) рассмотреть оценки свободных переменных. Если все оценки неотрицательны, то имеющееся опорное решение является оптимальным, в противном случае перейти к новому опорному решению;

6) выбрать в качестве разрешающего столбец, которому соответствует отрицательная оценка;

7) найти соотношения a_i0/a_ip для всех a_ip ≥ 0, i = 1, 2, ... , m. В качестве разрешающей выбрать строку, которой соответствует наименьшее из найденных соотношений;

8) выполнить одну итерацию метода Жордана-Гаусса. Перейти к шагу 5.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ:

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

F = x₁ + 3x₂ → max

x₁, x₂ ≥ 0.

Решение. Представим задачу в канонической форме:

F = x₁ + 3x₂ → max

x₁, x₂, x₃, x₄ ≥ 0.

Исходное опорное решение Х = (0, 0, 36, 70).

Целевая функция не содержит базисных переменных. Получаем из нее нулевое уравнение

F - x₁ - 3x₂ = 0

Дальнейшие действия произведем в табличном процессоре MS Excel

СОДЕРЖАНИЕ РАБОТЫ:

ВОПРОСЫ ВЫХОДНОГО КОНТРОЛЯ:

1. Опишите суть симплекс-метода решения задачи линейного программирования.
2. Опишите процесс приведения задачи линейного программирования к канонической форме записи.
3. Дайте определение базисного решения системы линейных уравнений.
4. Дайте определение опорного решения задачи линейного программирования.
5. Опишите процесс проверки опорного плана решения задачи линейного программирования на оптимальность.
6. Расскажите о правилах выбора разрешающей строки и разрешающего столбца в симплекс-таблице.

ДОМАШНЕЕ ЗАДАНИЕ:

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