Симплекс-метод

Цель занятия:

- изучить графический метод для решения линейных оптимизационных задач;

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

- изучить симплекс-метод для решения линейных оптимизационных задач;

Практическое задание:

Пример 2.1. Рассмотрим математическую модель линейной оптимизационной задачи, в которой требуется найти минимум целевой функции

Ограничения

Граничные условия

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

Граничные условия дополняются

Отложим по горизонтальной оси значения переменной х₁, а по

вертикальной оси - значения переменной х₂ (рис. 2.1). Учитывая граничные условия (х₁ >0, x₂ >0), штриховкой выделим полуплоскости допустимых значений переменных х₁ и х₂ (вправо от оси х₂ и вверх от оси х₁).

Рассмотрим одно из ограничений-равенств, например, первое

.

Перепишем относительно х₃ и приравняем к 0.

Последнее соотношение представляет собой уравнение прямой линии в плоскости х₁х₂. На этой прямой значение х₃ =0. Следовательно, по одну сторону от этой прямой х₃ >0, по другую х₃ <0. Учитывая граничное условие х₃ >0, штриховкой выделим полуплоскость, в которой х₃ >0.

Рис. 2.1. Графическое решение задачи

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

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

Следовательно, минимальное значение Z достигается при

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

Начальный выбор свободных и базисных переменных может быть произвольным. Однако структура системы такова, что в качестве базисных переменных удобно принять переменные х₃, х₄ и х₅, а в качестве свободных - переменные х₁ и х₂. В этом случае сразу же получаем некоторое исходное решение системы

свободные переменные х₁ =0, х₂ =0;

базисные переменные х₃=b₁, х₄=b₂, х₅=b₃.

Запишем исходную систему в более подробном виде

Переведем переменную х₁ в разряд базисных, а переменную х₃ в разряд свободных. Поделим первое уравнение на разрешающий коэффициент а₁₁

Выразим из этого уравнения переменную х₁

Подставим значение х₁ во второе и в третье уравнение системы и получим новую преобразованную систему уравнений

В этой системе свободными будут переменные х₂ и х₃, а базисными х₁, х₂ и х₅. Новое решение

свободные переменные х₂ =0, х₃ =0;

базисные переменные х₁= , х₄= , х₅= .

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

Пример 2.3. Решить Пример 2.1 симплекс-методом.

Метод состоит из двух этапов: на первом этапе ищется допустимое решение; на втором этапе это допустимое решение улучшается до оптимального.

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

Ограничения

Граничные условия

Перейдем к табличной форме записи.

Таблица 2.1

Исходное решение:

х₁ =0, х₂ =0, х₃=b₁, х₄=b₂, х₅=b₃.

Исходное значение целевой функции Z =0.

1 этап. Получение допустимого решения. Любое допустимое решение должно удовлетворять системе ограничений-равенств и граничным условиям.

Исходное решение удовлетворяет системе ограничений-равенств. Это решение будет удовлетворять граничным условиям в том случае, когда свободные члены b₁, b₂, b₃ будут неотрицательными. Следовательно, условием получения допустимого решения является неотрицательность свободных членов ограничений-равенств.

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

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

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

Выполняется пересчет всех коэффициентов таблицы 2.1 по правилам пересчета коэффициентов.

2 этап. Получение оптимального решения. Пусть оптимальному решению соответствует минимальное значение целевой функции Z. Необходимо проверить возможность улучшения полученного на первом этапе допустимого решения, то есть проверить возможность уменьшения значения целевой функции Z.

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

Пусть допустимому решению соответствует таблица 2.2.

Таблица 2.2

Условием получения оптимального решения при минимизации целевой функции является неотрицательность коэффициентов целевой функции z_i' >0.

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

Составьте алгоритм симплекс-метода.

Пример 2.4. Решить задачу примера 1 симплекс-методом.

Исходные данные:

прибыль от реализации одного изделия z₁=8; z₂=11; z₃=12 у.е./изд.;

нормы расхода энергии на одно изделие:

а₁₁ = 2; а₁₂ = 2; а₁₃ = 3 е.э./изд. (единиц энергии/изделие)

нормы расхода финансовых средств на одно изделие:

а₂₁ = 6; а₂₂ = 5,5; а₂₃ = 4 у.е./изд

нормы расхода сырья на одно изделие:

а₃₁ = 4; а₃₂ = 6; а₃₃ = 8 е.с./изд. (единиц сырья/изделие)

наличие на предприятии энергетических, финансовых и сырьевых

ресурсов:

b₁ = 50 е.э.; b₂ = 100 у.е.; b₃ = 150 е.с.

минимальное количество всех видов изделий, которое предприятие должно выпустить b₄ = 15 изд.

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

Ограничения

Перейдем к ограничениям-равенствам

Граничные условия

Запишем систему ограничений и целевую функцию в виде таблицы 2.3.

Таблица 2.3

Исходное решение:

Свободные переменные х₁ =0, х₂ =0, х₃= 0.

Базисные переменные х₄ =50, х₅ =100, х₆= 150, х₇= -15.

Значение целевой функции Z =0.

Исходное решение не является допустимым.

Четвертую строку (строку с отрицательным свободным членом b₄ =-15) принимаем в качестве разрешающей. Базисную переменную х₇, находящуюся в разрешающей строке, будем переводить в разряд свободных.

Просматриваем разрешающую строку. Из трех отрицательных коэффициентов этой строки произвольно выбираем коэффициент -1 при переменной х₃ и третий столбец табл. 2.3 принимаем в качестве разрешающего. Свободную переменную х3 будем переводить в базис. Разрешающий коэффициент, находящийся на пересечении разрешающей строки и разрешающего столбца выделен.

Таблица 2.4

В новом решении:

свободные переменные х₁ =0, х₂ =0, х₇ =0;

базисные переменные х₃ =15, х₄ =5, х₅ =40, х₆ =30;

значение целевой функции Z = 180.

В этом решении все переменные неотрицательные. Граничные условия выполняются. Полученное решение является допустимым.

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

Вычисляем положительные отношения свободных членов к коэффициентам разрешающего столбца: 5/3=1,67, 40/4=10 и 30/8=3,75. Первую строку, отвечающую минимальному из этих отношений, принимаем в качестве разрешающей. Базисную переменную х₄, отвечающую разрешающей строке, будем переводить в разряд свободных. Разрешающий коэффициент выделен.

Производим пересчет всех коэффициентов табл. 2.4 и получаем табл. 2.5, отвечающую новому допустимому решению.

Таблица 2.5

В этом допустимом решении:

свободные переменные х₁ =0, х₂ =0, х₄ =0;

базисные переменные х₃ =16,67, х₅ =33,33, х₆ =16,67, х₇ =1,67;

значение целевой функции Z = 200.

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

Производим пересчет всех коэффициентов табл. 2.5 и получаем табл. 2.6, отвечающую новому допустимому решению.

Таблица 2.6

В этом допустимом решении:

свободные переменные х₁ =0, х₄ =0, х₅ =0;

базисные переменные х₂ =11,76, х₃ =8,82, х₆ =8,82, х₇ =5,59;

значение целевой функции Z = 235,29.

Полученное решение является оптимальным, поскольку все коэффициенты в строке целевой функции неположительны и, следовательно, нет возможности дальнейшего увеличения целевой функции. Максимальная прибыль Z = 235,29 у.е.

Практическое занятие 3