Образцы решения злп симплексным методом

Планирование решений в экономике

Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Пример решения ЗЛП симплекс-методом

Пример решения ЗЛП симплекс-методом . Рассмотрим на конкретном примере процесс решения КЗЛП табличным симплекс-методом. Пусть дана каноническая задача ЛП:

образцы решения злп симплексным методом

Как видно, столбцы матрицы с номерами <5, 2, 3> являются линейно независимыми. И можно получить разложение по данным столбцам вектора ограничений с положительными коэффициентами. Последнее означает, что столбцы <5, 2, 3> образуют допустимый базис, с которого можно начать решение задачи. Из столбцов, входящих в базис, с учетом нулевых элементов формируется матрица ( (1) ) и обратная по отношению к ней -1 ( (1) ):

образцы решения злп симплексным методом

Используя их, по формуле (1.26) получаем

Пример - Табличный симплекс метод

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

Целевая функция:

Ограничивающие условия:

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

Так как наша задача - задача минимизации, то нам необходимо преобразовать ее к задаче на поиск максимума. Для этого изменим знаки коэффициентов целевой функции на противоположные. Элементы первого неравенства записываем без изменений, добавив в него дополнительную переменную x₅ и изменив знак ≤ на =. Т. к. второе и третье неравенства имеют знаки ≥ необходимо поменять знаки их коэффициентов на противоположные и внести в них дополнительные переменные x₆ и x₇ соответственно. В результате получем эквивалентную задачу:

Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции с противоположным знаком.

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

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

Рассмотрим однородную задачу ЛП из примера №1 п. 1.5.:

(1)

Добавив к левым частям системы неравенств соответствующие балансовые переменные преобразуем задачу (1) в каноническую форму:

Для удобства и единообразия запишем определение целевой функции в виде уравнения:

(3)

Запишем (2) и (3) в виде первой симплекс таблицы:

Пример решения прямой и двойственной задачи симплекс методом

Рассмотрен пример решения задачи симплекс методом, а также пример решения двойственной задачи.

Условие задачи

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b₁ = 240, b₂ = 200, b₃ = 160 единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a₁₁ = 2 единицы, ресурса второго вида в количестве a₂₁ = 4 единицы, ресурса третьего вида в количестве a₃₁ = 4 единицы. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a₁₂ = 3, a₁₃ = 6 единицы, ресурса второго вида в количестве a₂₂ = 2, a₂₃ = 4 единицы, ресурса третьего вида в количестве a₃₂ = 6, a₃₃ = 8 единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно c₁ = 4, c₂ = 5, c₃ = 4 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

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

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

Решение задачи симплекс методом

Решаем симплекс методом.

Вводим дополнительные переменные x₄ &ge 0, x₅ &ge 0, x₆ &ge 0, чтобы неравенства преобразовать в равенства.

Данные заносим в симплекс таблицу

Симплекс таблица № 1

образцы решения злп симплексным методом

Целевая функция:

образцы решения злп симплексным методом 0 · 240 + 0 · 200 + 0 · 160 = 0

Вычисляем оценки по формуле:

&Delta₂ = 0 · 3 + 0 · 2 + 0 · 6 - 5 = - 5

&Delta₃ = 0 · 6 + 0 · 4 + 0 · 8 - 4 = - 4

&Delta₄ = 0 · 1 + 0 · 0 + 0 · 0 - 0 = 0

&Delta₅ = 0 · 0 + 0 · 1 + 0 · 0 - 0 = 0

&Delta₆ = 0 · 0 + 0 · 0 + 0 · 1 - 0 = 0

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:

Вводим переменную x₂ в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение образцы решения злп симплексным методом для столбца x₂ .

Из 1-й строки вычитаем 3-ю строку, умноженную на 3

Из 2-й строки вычитаем 3-ю строку, умноженную на 2

образцы решения злп симплексным методом

Получаем новую таблицу:

Симплекс таблица № 2

образцы решения злп симплексным методом

Целевая функция:

образцы решения злп симплексным методом 0 · 160 + 0 · 440/3 + 5 · 80/3 = 400/3

Вычисляем оценки по формуле:

образцы решения злп симплексным методом

&Delta₁ = 0 · 0 + 0 · 8/3 + 5 · 2/3 - 4 = - 2/3

&Delta₂ = 0 · 0 + 0 · 0 + 5 · 1 - 5 = 0

&Delta₃ = 0 · 2 + 0 · 4/3 + 5 · 4/3 - 4 = 8/3

&Delta₄ = 0 · 1 + 0 · 0 + 5 · 0 - 0 = 0

&Delta₅ = 0 · 0 + 0 · 1 + 5 · 0 - 0 = 0

&Delta₆ = 0 · (-1)/2 + 0 · (-1)/3 + 5 · 1/6 - 0 = 5/6

Поскольку есть отрицательная оценка &Delta₁ = - 2/3, то план не оптимален.

Вводим переменную x₁ в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение образцы решения злп симплексным методом для столбца x₁ .

образцы решения злп симплексным методом

Наименьшее неотрицательное: Q₃ = 40. Выводим переменную x₂ из базиса

3-ю строку делим на 2/3.

Из 2-й строки вычитаем 3-ю строку, умноженную на 8/3

образцы решения злп симплексным методом

Получаем новую таблицу:

Симплекс таблица № 3

образцы решения злп симплексным методом

Целевая функция:

образцы решения злп симплексным методом 0 · 160 + 0 · 40 + 4 · 40 = 160

Вычисляем оценки по формуле:

&Delta₆ = 0 · (-1)/2 + 0 · (-1) + 4 · 1/4 - 0 = 1

Ответ

Решение двойственной задачи

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

Задача. Для изготовления различных изделий A и B используется 2 вида сырья. На производство единицы изделия A его требуется затратить: 1-го вида -15кг, 2-го вида - 11кг, 3-го вида - 9кг. На производство единицы изделия B требуется затратить сырья 1-го вида - 4кг, 2-го вида - 5кг, 3-го вида - 10кг.

Производство обеспечено сырьем 1-го вида в количестве 1095кг, 2-го вида - 865кг, 3-го вида -1080кг.

Прибыль от реализации единицы готового изделия А составляет 3 рубля, изделия B - 2 рубля. Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации.

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

образцы решения злп симплексным методом