СКАЧАТЬ:  mod2.zip [36,74 Kb] (cкачиваний: 67)

Лабораторная работа №1

по дисциплине: «Моделирование систем»

на тему: «Решение задач линейного программирования. Симплексный метод»

Цель работы

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

Линейное программирование

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

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

На выбор оптимальных значений переменных  накладываются дополнительные условия, которые заключаются в том, что искомая совокупность значений независимых переменных должна удовлетворять системе линейных соотношений, включающей в общем случае как неравенства, так и равенства:

                                (1)

Коэффициенты  в соотношениях (1) принимаются дей­ствительными числами, положительными или отрицательными, среди которых могут быть равные нулю. Естественно, что число ограниче­ний типа равенств  не должно превышать число независимых переменных  оптимальной задачи. В задачах линейного программирования обычно предполагается, что все независимые переменные неотрицательны, т. е. вместе с условиями (1) должны также выполняться условия неотри­цательности значений величин :

   .                                          (2)

Условия неотрицательности (2) обусловлены тем, что в подавляющем большинстве экономических задач, где линейное программирование находит наиболее широкое применение, независимые переменные, имеющие конкретный физический смысл единиц продук­ции, цены и т. д., как правило, не могут быть отрицательными.

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

  Задачу линейного программирования можно сформулировать следующим образом.

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

Симплексный метод

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

Симплекс-метод, называется также «методом последовательного улучшения плана». Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов. Алгоритмы симплекс-метода позволяют также установить, является ли задача ЛП разрешимой.

Любое решение системы уравнений

    ,

состоящее из на­бора  неотрицательных значений переменных , называется допустимым решением.

Допустимое решение, в котором ровно  составляющих отличны от нуля, называется допустимым базисным решением, или просто базисным решением. Иногда базисное решение называют также планом.

Задача №3

Найти оптимальные неотрицательные решения, минимизирующие линейную форму:

Решение

Определим ранг матрицы:

т.к. r₁= r₂, делаем вывод, что система совместна.

1) Возьмем:

• базисные (x₁, x₄);
• свободные (x₂, x₃).

Получаем первое базисное решение:

(-0.5; 0; 0; 3), при котором l=0.

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

При этом  можно увеличивать до 3, а  превращается в свободную переменную.

2) Возьмем:

• базисные (x₁, x₂);
• свободные (x₃, x₄).

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

3) Возьмем:

• базисные (x₂, x₃);
• свободные (x₁, x₄).

В результате мы получили решение, которое является оптимальным:

(0; 3; 1; 0), при котором l=-1.

Задача №4

Найти оптимальные неотрицательные решения, минимизирующие линейную форму:

Решение:

Составим матрицу системы и расширенную матрицу и найдем их ранги:

За базисные переменные примем , следовательно, свободные переменные :

Следовательно, целевая функция:

Уменьшение L возможно при увеличении , поэтому нужно ввести в базис, а, например, - вывести из базиса.

За базисные переменные примем , следовательно, свободные переменные :

Следовательно, целевая функция:

Ответ: (0, 60, 0, 55)