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

Шаг 5.3. Выполнение симплекс - преобразования и переход к новой симплекс-таблице.

Элемент a_ij новой симплекс-таблицы вычисляется с помощью следующего симплекс - преобразования:

(3.23)

(3.24)

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

Новое решение имеет следующий вид: все свободные переменные в нем полагаются равными 0, а все базисные переменные - свободным членам, стоящим в одной строке с ними.

После построения новой симплекс-таблицы следует перейти к шагу 3

Поясним на примерах некоторые шаги алгоритма.

Пример 3.4

Базисные переменные: х_з,х₄.

Свободные переменные:

Симплекс-таблица имеет следующий вид (табл. 3.4):

Значение f можно увеличить, увеличивая значение переменной x₁,так как ей соответствует положительный коэффициент в формуле для f, соответственно, отрицательный коэффициент в последней строке симплекс-таблицы. Из системы ограничений видно, что при любом увеличении значения X₁можно подобрать значения х_з,х₄, при которых Будет выполняться система ограничений. Следовательно, функция f будет бесконечно возрастать и не будет ограниченной на области допустимых решений

Таблица 3.4

Базисные переменные	Коэффициенты при переменных	Свободные члены
	х1	х2	х3	х4
х4 х3	-1 -5	2 -3	1 0	0	6 7
-f	-2	3	0	0	0

Пример 3.4

Запишем задачу в каноническом виде, вводя дополнительные переменные х₄, х₅, х_6.

Начальное решение:

Функция Уже выражена через свободные переменные, поэтому можно перейти к составлению симплекс-таблицы
(табл. 3.5).

Таблица 3.5

Базисные переменные	Коэффициенты при переменных	Свободные члены
	х1	х2	х3	х4	х5	х6
х4 х5 х6	3 1 -2	3 0 8	-1 3 0	1 0 0	0 1 0	0 0 1	15 7 20
-f	-5	2	-3	0	0	0	0

Ввод переменной в список базисных переменных означает, что ей приписывается отличное от 0 положительное значение, т. е. ее значение увеличивается. Из формулы для целевой функции видно, что увеличение значения х₂ приводит только к уменьшению f т. е. переменную х₂ бессмысленно вводить в список базисных переменных. Увеличение переменных х₁ и х₃ приводит к увеличению значения f при этом на большую величину значение изменяется с увеличением х_{1 ,}следовательно, переменная х₁ должна стать базисной переменной. Максимальное значение коэффициента при х₁ в формуле для f соответствует максимальному по абсолютной величине отрицательному элементу в последней строке симплекс-таблицы, следовательно, понятен выбор новой базисной переменной.

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

следовательно, из списка базисных переменных надо вывести х₄ , стоящую в первой строке симплекс-таблицы, и разрешающий элемент a₁₁=3.

Поясним этот выбор. Если перейти от симплекс-таблицы к ограничениям, то это значит, что х₁ надо выразить из первого уравнения через остальные переменные, включая х₄ ,и, подставив его во второе и третье уравнения, исключить оттуда х₄ . Проделаем это ниже, а сейчас поясним, почему выбор пал именно на х₄.

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

Подставив х₁ в первое уравнение, получим

Подставив х₂ во второе уравнение, получим

Окончательно получим

- базисные переменные, поэтому решение имеет вид

В этом решении x₄ = -6, что противоречит условию задачи следовательно, Х₁ не является допустимым решением, и, таким образом, переменную x₅ нельзя вывести из списка базисных переменных.

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

Выразив х₁ через х₆, получим

Следовательно, в новом решении х₁ = -10, что противоречит условию неотрицательности х₁, поэтому на шаге 4.2 пренебрегают делением на отрицательное число, полагая равным результат от деления.

Пример расчета экономико-математической модели

Предприятие рекламирует свою продукцию с использованием четырех источников массовой информации: телевидения, радио, газет и расклейки объявлений. Анализ рекламной деятельности в прошлом показал, что эти средства приводят к увеличению прибыли соответственно на 10, 5, 7 и 4 усл. ед., в расчете на 1 усл. ед., затраченную на рекламу. На рекламу выделено 50 000 усл. ед. Администрация предприятия не намерена тратить на телевидение более 40 %, а на радио и газеты -- более 50 % от общей суммы выделенных средств. Как следует предприятию организовать рекламу, чтобы получить максимальную прибыль?

Решение.

Составим математическую модель задачи.

Цель - максимизация прибыли.

Параметрами являются все числа, приведенные в условии задачи.

Управляющие переменные:

х₁ - количество средств, вложенных в рекламу на телевидение;

х₂ - количество средств, вложенных в рекламу на радио;

х₃ - количество средств, вложенных в рекламу в газетах;

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

Область допустимых решений имеет вид

(3.25)

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

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

(3.26)

(3.5), (3.6) - математическая модель задачи организации рекламной деятельности.

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

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

(3.27)

Задача (3.5), (3.7) может быть решена симплекс-методом.

Решение.

Шаг 1. Получение начального решения.

Базисные переменные:

Свободные переменные:

Начальное решение:

Х_о ={ =0; х₂=0; х₃=0;х₄=0; х₅ =50 000; = 20 000; х₇= 25 000}.

Шаг 2. Функция уже выражена через свободные переменные.

Шаг 3. Проверка решения на оптимальность. Составляем симплекс-таблицу (табл. 3.6).

Таблица 3.6

Решение неоптимально, так как последняя строка содержит отрицательные числа.

Шаг 4. Получение нового решения.

Максимальное по абсолютной величине отрицательное число последней строки -- это -10; следовательно, первый столбец является разрешающим и переменная х₁ вводится в список базисных переменных. Найдем переменную, выводимую из списка базисных переменных. Для этого подсчитаем отношения элементов столбца свободных членов к элементам разрешающего столбца и выберем среди них минимальное

Вторая строка является разрешающей, и переменная х₆ должна быть выведена из списка базисных переменных.

Разрешающий элемент а₂₁ = 1.

Составим новую симплекс-таблицу.

Для подсчета элементов новой симплекс-таблицы по формулам (3.23, 3.24) удобно использовать правило треугольника, наглядно отображающее указанные формулы.

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

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

Новая симплекс-таблица имеет следующий вид (табл. 3.7):

Таблица 3.7

Базисные переменные	Коэффициенты при переменных	Свободные члены
	x1	x2	x3	x4	x5	x6	x7
x5	0	1	1	1	1	-1	0	30000
х1	1	0	0	0	0	1	0	20000
x7	0	1	1	0	0	0	1	25000
P	0	-5	-7	-4	0	10	0	200000

Новое решение имеет вид

Таким образом, прибыль увеличилась на 200 000 ус. ед. Это решение неоптимально, так как последняя строка содержит отрицательные числа. Продолжаем оптимизацию.

Разрешающий столбец--третий, так как ему соответствует максимальное по абсолютной величине отрицательное число -7.

Следовательно, третья строка является разрешающей.

Разрешающий элемент: а₃₃ =1.

Перейдем к новой симплекс-таблице (табл. 3.8).

Таблица 3.8

Базисные переменные	Коэффициенты при переменных	Свободные члены
	x1	x2	x3	x4	x5	x6	x7
x5	0	0	0	1	1	-1	-1	5000
х1	1	0	0	0	0	1	0	20000
X3	0	1	1	0	0	0	1	25000
P	0	2	0	-4	0	10	7	375000

Прибыль выросла, но решение X₂ неоптимально, так как в последней строке еще осталось отрицательное число.

Получим новое решение.

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

Разрешающая строка -- первая, и переменная х₅ выводится из списка базисных переменных.

Новая симплекс-таблица имеет следующий вид (табл. 3.9):

Таблица 3.9

Базисные переменные	Коэффициенты при переменных	Свободные члены
	x1	x2	x3	x4	x5	x6	x7
X4	0	0	0	1	1	-1	-1	5000
х1	1	0	0	0	0	1	0	20000
X3	0	1	1	0	0	0	1	25000
P	0	2	0	0	4	6	3	395000

Последнее решение является оптимальным, поскольку все числа, стоящие в последней строке, неотрицательны. Это решение единственно, так как все элементы последней строки, соответствующие свободным переменным х₂, х₅,х₆, х₇,строго положительны.

Таким образом, для получения максимальной прибыли в размере
395 000 усл. ед. надо распределить средства следующим обраэом:
20 000 усл. ед. вложить в рекламу на телевидении; 20 000 усл. ед. вложить в рекламу в газетах и 5000 усл. ед. вложить в рекламу, организованную с помощью расклейки объявлений. Рекламу на радио организовывать не следует.

Изложенные выше вычисления проводились для случая, когда начальное решение является допустимым. Если в начальном решении существуют b_i<0, то допустимое начальное решение можно найти по следующему алгоритму.

Шаг 1. Выражение функции f через свободные переменные.

Шаг 3. Составление симплекс-таблицы.

Шаг 3. Выбор переменной, вводимой в список базисных переменных.

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

Шаг 4. Выбор переменной, выводимой из списка базисных переменных.

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

Шаг 5. По формулам (3.23) и (3.24) проводят симплекс-преобразование и переходят к новой симплекс-таблице. Если в новой таблице все свободные члены неотрицательны, то найденное решение является допустимым и следует перейти к шагу 3 алгоритма симплекс-метода, в противном случае - к шагу 2 рассматриваемого алгоритма.

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

Контрольные вопросы

1. В чем особенности симплекс метода?

2. Может ли в ограничениях присутствовать неравенства при решении задачи симплекс методом?

3. Могут ли, при решении задачи симплекс методом, присутствовать отрицательные переменные?

Двойственная задача линейного программирования. Экономическая интерпретация

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

В задаче требуется максимизировать целевую функцию; все ограничения являются неравенствами со знаком , все переменные х₁ ,х₂,...,х_п неотрицательны. Задача содержи n управляющих переменных и т ограничений. Коэффициенты при переменных в целевой функции: c₁,c₂,...,c_n ; свободные члены: b₁, b₂,…, b_m.

Двойственная задача линейного программирования имеет вид



В двойственной задаче требуется найти минимум целевой функции, ограничения - неравенства со знаком управляющие переменные y₁, y₂,… ,y_m неотрицательны. Задача содержит m управляющих переменных и n ограничений. Коэффициенты целевой функции задачи b₁, b₂,… ,b_m являются свободными членами исходной ЗЛП, а свободные члены двойственной задачи с₁,с₂,...,с_n - коэффициентами целевой функции исходной ЗЛП. Матрица коэффициентов двойственной задачи транспонирована, т. е.. строки заменены столбцами, а столбцы - строками.

Задачи (3.28), (3.29) и (3.30), (3.31) называются парой взаимно двойственных задач линейного программирования.

Для двойственных задач верна следующая теорема.

Теорема двойственности: если одна из взаимно двойственных задач имеет оптимальное решение х* , то другая также имеет оптимальное решение у* . При этом соответствующие им оптимальные значения целевых функций f* =f(x*) и g=g(y*) равны.

Поясним экономический смысл двойственной модели. Пусть в качестве управляющих переменных x_j, исходной модели рассматривается число изделий, производимых некоторым предприятием, а параметрами b_i, - количество ресурсов i-го типа, используемых для изготовления изделий. Через a_ij обозначено количество ресурсов i-го типа, идущее на изготовление одного изделия j-го вида, (j - прибыль от реализации одного изделия j-го вида). Тогда исходная модель (3.28), (3.29) соответствует задаче определения оптимального плана производства продукции, обеспечивающего максимальную прибыль.

Пусть предприятие решило прекратить производство изделий и продать ресурсы, идущие на их изготовление. Обозначим через цены на единицу ресурсов i-го вида, Цены на ресурсы должны удовлетворять следующим двум условиям: во-первых, они нe должны быть слишком высокими, иначе ресурсы невозможно будет продать; а во-вторых, цены на ресурсы должны быть такими, чтобы прибыль от их реализации была больше прибыли от реализации готовой продукции. Первое условие выражается формулой (3.30), второе условие - ограничениями (3.31). В левой части каждого из неравенств (3.31) стоит прибыль от продажи ресурсов всех типов, идущих на изготовление j -го изделия, в правой части - прибыль от продажи j-го изделия, Таким образом, двойственная задача (3.30) - (3.31) соответствует следующей экономической проблеме: по каким минимальным ценам следует продавать ресурсы, чтобы прибыль от их реализации была больше прибыли, полученной от реализации продукции, изготавливаемой с использованием этих ресурсов. Значения переменных y₁, y₂,… ,y_m часто называют теневыми ценами.

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

Целочисленное линейное программирование. Метод Гомори

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

Математическая модель задачи ЦЛП имеет следующий вид 6

где Z - множество целых чисел.

Для решения задачи ЦЛП может быть применен метод Гомори.

Метод Гомори содержит два этапа.

Этап 1. Решение исходной задачи обычным симплекс-методом и проверка решения на целочисленноесть. Если решение содержит хотя бы одно дробное значение, то переходят к этапу 2, в противном случае расчет заканчивается.

Этап 3. Составление дополнительного ограничения (сечения) и решение расширенной задачи обычным симплекс-методом. Дополнительное ограничение (сечение) отсекает нецелочисленные решения. Сечение обладает следующими двумя свойствами:

1) любое целочисленное решение ему удовлетворяет;

2) любое не целочисленное решение задачи ему не удовлетворяет.

Объясним, как составляется сечение.

Пусть выполнен этап 1;

- дробное число.

Рассмотрим i-е ограничение:

b_i = x_i +a_im+lx_m+1 +a_im+2x_m+2+…+a_inx_n .

Так как b_i - дробное, а в правой части все переменные целые, хотя бы одно значение a_ij, должно быть дробным.

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

Обозначим через {r} дробную часть числа r.

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

Дробная часть произведения не превосходит произведения целого на дробную часть, следовательно:

В результате имеем

Обозначим

Тогда из последнего неравенства получаем

Отняв от левой части неравенства дополнительную неотрицательную переменную, переходим к уравнению

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

Эту задачу решают обычным симплекс-методом, т. е.. переходя к этапу 1.

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

Размещено на Allbest.ru

...