Тема 1. Методы математического программирования

Обсуждение постановки задачи
2. Решение задачи графическим методом
3. Решение задачи

симплекс-методом
4. Анализ полученных результатов

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

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

направленным перебором наборов базисных и свободных переменных

Определяется начальный набор

Затем каждый

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

Заменяемые переменные не повторяются

то итерационный процесс конечен

Опытным путем установлено, что для большей части

задач число итераций составляет от 1,5m до 3m (где m – число уравнений-ограничений)

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

(1)
х1+х2+ х5

= 5
Требуется найти неотрицательные значения переменных, удовлетворяющих условиям (1) и обращающих в максимум целевую функцию:

Ll = -L = х1-х2 (2)

Поскольку m=3, а n=5, то имеем 3 базисных переменных и (n- m) = 2 свободных переменных.

и х2 за свободные.
Положив переменные х1= х2 = 0,

находим базисное решение
х3=2, х4=2, х5=5, которое является допустимым и при котором
Ll = х1-х2= 0.

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

целевой функции со знаком «+», т. е. при ее увеличении

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

со знаком «+» входит свободная переменная x1:
Ll = х1-х2

Значит, максимум целевой функции не достигнут и перемен-ную x1 следует сделать базисной.
Для определения новой свободной переменной выразим базисные переменные х3, х4, х5 через свободные, приведя уравнения (1) к виду:
х3 = 2 +2х1 - х2
х4 = 2 - х1 + 2х2 (3)
х5 = 5 - х1 - х2
Из этих уравнений видим, что при x2=0 увеличение х1 не приводит к уменьшению х3, но уменьшает х4 и х5, так что при
х1 =2 получаем х4=0, x5=3 > 0.

Таким образом, переменную х4 следует сделать свободной, что приводит к новому базису х1 , х3, х5.

ее к виду

х1 = 2 +2х2 – х4
х3 = 6

+ 3х2 - 2х4 (4)
х5 = 3 - 3х2 + х4

Целевую функцию также выразим через новые свободные переменные х2 и х4:

Ll = 2+х2-х4= 0.

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

этом принимает вид
Ll =3—2х4/3—х5/3.
Из Ll видим, что при увеличении

свободных переменных х4, х5 значение Ll уменьшается.
Следовательно, при данном базисе достигается максимум целевой функции и решением рассмотренной задачи будет следующий набор переменных:
При этом Ll = - L = 3.

связан с громоздкими преобразованиями системы линейных уравнений из одной формы

в другую.

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

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

на примере задачи, решенной выше.

Они в точности соответствуют тем

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

Пусть задача линейного программирования дана в виде системы уравнений (1) рассмотренных ранее и целевой функции (2) , которую надо максимизиро-вать.

уравнений и целевую функцию к виду:

(5)


Матрицу коэффициентов представим в виде табл.1а, в верхнем левом углу клеток запишем коэффициенты аij уравне-ний (5).
Проверим, не найдено ли оптимальное решение, условием которого является а0j ≥ 0, j≠ 0.
Поскольку а01 (коэффициент при х1 в выражении для Ll ) отрицателен, то оптимальное решение не найдено и перемен-ную х1 следует сделать базисной.
Выделим жирными линиями столбец, соответствующий переменной х1.

Ll = 0 - (- х1 + х2);
х3 = 2 - (-2х1 + х2)
х4 = 2 - (х1 - 2х2);
х5 = 5 – (х1 + х2)

а)

б) в)

в базисную можно переводить любую из них.

Определим теперь, какую же

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

Это будет та базисная переменная хi для которой коэффи-циент в отмеченном столбце аi1 >0 и отношение а i0 /аi1 наименьшее.
Такой переменной является базисная переменная х4 с а40=2 и а41 = 1.

Строку, соответствующую базисной переменной х4 , также выделим жирными линиями

выделенных строки и столбца, назовем генеральным коэффициентом (взят в рамку).

Обозначим через λ величину, обратную генеральному коэффициенту. В нашем случае
λ =1/a41=1.
Теперь следует заполнить нижние углы каждой клетки.
Это делаем по следующим правилам:
в клетку на пересечении отмеченных строки и столбца записываем λ =1/a41 ;
в клетках выделенной строки записываем нижние коэффициенты, равные верхним, умноженным на λ (верхние коэффициенты, за исключением генераль-ного, выделены жирным шрифтом);

верхние коэффи-циенты, умножаем на -λ (за исключением клетки с генеральным,

нижние коэффициенты выделены жирным шрифтом);

4) в остальных клетках записываем произведение выделенных жирным шрифтом коэффициентов, на пересечении которых стоит данная клетка.

Затем переходим к заполнению табл. Б, которая отличается от табл. А тем, что отмеченная свободная переменная х1 стала базисной, а отмеченная базисная переменная х4 стала свободной.

строку и столбец, соответствующие новым свободной и базисной переменным, заполняем

нижними коэффи-циентами выделенной строки и столбца табл. А;
2) в остальные клетки записываем суммы коэффици-ентов, стоящих в соответствующих клетках табл. А.
3) умножаем верхние коэффициенты строки х5 на λ=1/3
4) умножаем верхние коэффициенты столбца х4 на – λ.
5) в остальных клетках записываем произведение выде-ленных жирным шрифтом коэффициентов, на пересе-чении которых стоит данная клетка
Заполненная таким образом табл.Б соответствует матрице коэффициентов при новом базисе х1, х3, х5

найдено.
Далее вся процедура повторяется.
Заполнить нижние левые углы строки

х2 и столбца х5 табл. В коэффициентами из строки х5 и столбца х2 таблицы Б соответственно.
Перейти к новой табл. В, соответствующей базису
х1, х2, х3.

В таблице В коэффициенты а0j , j≠ 0 положительны. Значит иттерации следует прекратить.
Найдем оптимальное решение задачи. Заполним клетки столбцов «1» и х4.
Записываем суммы коэффициентов, стоящих в соответствующих клетках табл. Б.

х3= 9;
х4=х5= 0;
Ll = -L = 3
L = -3

задачи на основе симплекс-метода представляется последовательностью следующих шагов:
Шаг 1. Приведение

задачи к каноническому виду
Шаг 2. Построение начального плана
Шаг 3. Проверка оптимальности плана:
1. Если «да», то возможны два варианта:
а) получен оптимальный план и в этом случае - «Оформление полученных результатов» и конец алгоритма;
б) задача не имеет решения и выдача сообщения «Задача не имеет решения»;

значения) – переход на шаг 4.
Шаг 4. Проверка «Разрешающий

элемент выбран?»:
- если «да» - переход на шаг 5;
- если «нет» - выдача сообщения: «Целевая функция не ограничена» и конец алгоритма
Шаг 5. Выполнение процедуры полного исключения с выбранным разрешающим элементом и переход на шаг 3

Рассмотрим выполнение этих шагов алгоритма симплекс-метода на примере следующей постановки задачи.

имеются четыре мастерских.

Мастерская типа j (j = 1, 2, 3,

4) может принять одновременно aij средств пожаротушения типа i (i =1, 2, 3) и произвести их обслуживание и ремонт при стоимости cij

Каждый тип средств пожаротушения представлен bij единицами

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

Исходные данные к задаче представлены в виде таблицы на следующем слайде

необходимо избавиться от неравенств.
Введем дополнительные переменные x5, x6 и x7
Целевая

функция и ограничения примут следующий вид:
U = 4x1 + 4x2 +3x3 +2x4 +0x5 +0x6 + 0x7
1x1 + 2x2 +4x3 +0x4 -1x5 -0x6 + 0x7 = 24
3x1 + 2x2 +0x3 +2x4 +0x5 -1x6 + 0x7 = 18
0x1 + 4x2 +3x3 +1x4 +0x5 +0x6 - 1x7 = 18
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
Каждой дополнительной переменной можно придать смысл числа мастерских фиктивного типа, которые обслуживают средства пожаротушения, создающие превышение над заданным числом bi

необходимо преобразовать так, чтобы базисные переменные остались по одной в

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

X(1) = (x(1)1, x(1)2, …, x(1)j,…, x(1)m, 0, 0,…, 0),
где x(1)1 = β(1)1, x(1)2 = β(1)2,…, x(1)m = β(1)m;

β(1)i – значения преобразованных свободных членов bi;
j/ - порядковый номер базисной переменной в плане

способов является введение искусственных переменных
В каждое уравнение ограничений, где нет

базисной переменной, вводится искусственная переменная xn+k (k = 1, 2,…, m) с единичным коэффициентом
К целевой функции все искусственные переменные xn+k присоединяются с общим коэффициентом М, значение которого выбирается достаточно большим (M >> max cj)

допустимое решение, то в процессе оптимизации каждая из введенных переменных

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

4x1+ 4x2+3x3+2x4+0x5+0x6+ +0x7+Мx8+Мx9+Мx10
x1+2x2+4x3+0x4 -1x5 - 0x6+0x7+1x8+0x9+0x10 = 24
3x1+2x2+0x3+2x4+0x5 -

x6+0x7+0x8+1x9+0x10=18
0x1+4x2+3x3+1x4+0x5+0x6 - 1x7+0x8+0x9+1x10= 18
xj =0, j = 1, 2 ,…, 10
При записи начальной симплекс-таблицы, соответствующей этой модели, производят исключение искусственных перемен-ных в целевой функции
Для этого необходимо выразить каждую базисную переменную в уравнениях-ограничениях через свободные переменные, подставить в целевую функцию и привести подобные члены

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

целевой функции находятся как




В дальнейшем по ним оценивается построенный план
Левый элемент нулевой строки содержит значение целевой функции (U = 60M)
Столбец свободных членов содержит значения базисных неизвестных

x7 нулю, получим значения базисных составляющих начального плана x8 =

24, x9 = 18 и x10 = 18
План обеспечивает значение целевой функции U = 60M

Шаг 3. Проверка оптимальности плана
Чтобы проверить, является ли полученный план оптимальным или нет, необходимо произвести анализ значений коэффициентов при свободных переменных в целевой функции (в строке 0 симплексной таблицы).
Каждый коэффициент в строке 0 определяет положительное (если его значение больше нуля) или отрицательное (если его значение меньше нуля) приращение целевой функции U при увеличении на единицу соответствующей ему небазисной переменной

нуля (вводя ее в базис-ные переменные), мы не сможем уменьшить

значение целевой функции
Следовательно, либо получен оптимальный план и нужно переходить на шаг 6 (при отсутствии искусственных переменных в плане), либо задача не имеет решения (при наличии искус-ственных переменных в плане)
Если же некоторые коэффициенты имеют отрицательные значения, то при увеличении одной из соответствующих им свободных переменных можно добиться улучшения плана
План x(1) не является оптимальным (γ1, γ2, γ3 и γ4 < 0)

подлежит та из свободных переменных xs, для которой оценка γs

отрицательна и имеет наибольшее абсолютное значение:
γs < 0, γs = maxj| γj|.
Это обеспечивает (но не всегда) сокращение числа итераций

Теперь остается выяснить, какая базисная переменная должна исключаться из плана
Тем самым мы определим, с каким значением будет введена свободная переменная
Чем больше значение xs, тем меньше значение U
Однако нельзя забывать об ограничениях

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

переменной в столбце s:

xs в каждом ограничении
Так, по условиям рассматриваемой задачи
(s

= 2):
- исходя из возможностей обслуживания средств пожаротушения первого типа, можно взять x1 = 24/2 = 12;
- исходя из возможностей обслуживания средств пожаротушения второго типа x2 = 18/2 = 9;
- исходя из возможностей обслуживания средств пожаротушения третьего типа x3 = 18/4 = 4,5.
В целом максимально допустимым значением, очевидно, может быть x3 = 4,5 (это узкое место).

переменной с положительным значением отношения βi /αis, то, значит, целевая

функция не ограничена снизу
Строку r, столбец s и элемент ars принято называть разрешающими
В рассматриваемой задаче разрешающим элементом будет элемент a32
Для элемента a32: γ2 = 4 – 8M,
β3 /α32 = 4,5

αrs
Переход к новой симплекс-таблице обеспечивается выполнением процедуры полного исключения, широко

используемой при решении систем линейных уравнений
Все элементы разрешающей строки s делятся на значение разрешающего элемента αrs

строках i (i = 0, 1, 2,…, m, i ≠r),

вычитают из каждой из них строку с αrs, умноженную на значение коэффициента αis

αrs/ = 1;
αrj / = αrj / αrs;
αij / = αij -(αrj / αrs)* αis,
i = 0, 1, 2,…, m;
j = 0, 1, 2,…, n;
i ≠r; i ≠s.

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

шагов 3, 4 и 5 представляет собой одну итерацию по улучшению плана
Далее, начиная с шага 3, должна выполняться следующая итерация

очередной итерации, в какой-то из последующих базисов не имеет смысла,

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

= -24M-18
После трех итераций все искусственные переменные (x8, x9 и

x10) окажутся исключенными из плана (см. таблицу на очередном слайде)
Целевая функция примет значение
U(4) = 38

две итерации
Последней итерации соответствует таблица на следующем слайде

табличном виде (см. таблицу)

оптимальным для решаемой задачи будет план:
x(6) = {x1 = 0,

x2 = 0, x3 = 6, x4 = 9}
При этом затраты составят U(6) = 36 единиц и дополнительно еще может быть обслужено 9 средств пожаротушения, так как x7 = 9

примере, оптимальное решение не было сначала очевидным
С увеличением размерности симплекс-таблицы

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