5. Задание для лабораторной работы

1. Варианты заданий к лабораторным работам соответствуют вариантам контрольной работы “Линейное программирование” и приведены в /3/. В данной лабораторной работе следует с помощью программы “Решение и моделирование задач линейного программирования” получить решение заданий пункта 1а контрольной работы “Линейное программирование”. Таким образом, в лабораторной работе, используя программу, необходимо решить следующие задачи:

а) Решить исходную ЗЛП.

б) Решить ЗЛП с измененной целевой функцией.

в) Решить ЗЛП с измененной правой частью системы ограничений.

г) Решить ЗЛП при введении дополнительного ограничения.

д) Решить ЗЛП при введении новой переменной.

е) Для данной ЗЛП сформулировать двойственную задачу. Решить ее симплекс-методом. С помощью соотношений двойственности проверить ответ.

2. Решить исходную ЗЛП с использованием встроенных функций табличного процессора Excel.

3. Отчет лабораторной работы должен содержать:

а) Исходные данные и оптимальную симплекс-таблицу для заданий 1а-1е данного пункта, для задания 1е необходимо представить модель двойственной задачи, ее приведение к стандартной форме, исходные данные для решения на ЭВМ, оптимальную симплекс-таблицу и результаты проверки ее решения с помощью соотношений двойственности.

б) Результаты решения исходной ЗЛП с помощью встроенных функций Excel, включающие в себя исходные данные для решения задачи и для каждой итерации: матрицу базиса и обратную к ней, вектор (матрицу) коэффициентов при базисных переменных, вектор (матрицу) двойственных переменных, текущую симплекс-таблицу.

Отчет по лабораторной работе может быть выполнен на ПЭВМ и представлен в распечатанном виде. Типовой отчет приведен в приложении.

6. Литература

1.	Трушков А. С. Решение и моделирование задач линейного программирования. Отчёт и программная документация. - КФ МГОУ, г. Коломна, 1998 г., 76 с.
2.	Трушков А. С. Симплексный метод решения задач линейного программирования. Алгоритмы и приложения.// Учебное пособие. Изд-во КФ МГОУ, г. Коломна, 1996 г., 107 с.
3.	Трушков А.С. Контрольная работа “Линейное программирование”.// Сборник вариантов контрольной работы. Изд-во КФ МГОУ, г. Коломна, 1996 г., 66 с.

Приложение.

Типовой отчет по лабораторной работе "Решение задач линейного программирования"

Задание.

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

max z = -x₁ + 2x₂ + x₃

2x₁ + 3x₂ - 5x₃  3

-x₁ + 9x₂ - x₃  5

4x₁ + 6x₂ + 3x₃  15

x_i  0

Для приведения задачи к стандартной форме вводим дополнительные переменные:

max z = -x₁ + 2x₂ + x₃

2x₁ + 3x₂ - 5x₃ - x₄ = 3

-x₁ + 9x₂ - x₃ - x₅ = 5

4x₁ + 6x₂ + 3x₃ + x₆ = 15

x_i  0

Матрица системы ограничений не содержит выделенной единичной матрицы:

.

Вводим искусственные вектор-столбцы в матрицу А:

.

Исходная модель приобретает следующий вид:

max z = -x₁ + 2x₂ + x₃ - Mx₆ - Mx₇

2x₁ + 3x₂ - 5x₃ - x₄ + x₆ = 3

-x₁ + 9x₂ - x₃ - x₅ + x₇ = 5

4x₁ + 6x₂ + 3x₃ + x₈ = 15

x_i  0

Результаты решение ЗЛП с помощью программы представлены в следующих таблицах: