Задачи линейного программирования

Переход к шагу 3.

Шаг 4. Проверка решения на оптимальность.

Составляется симплекс-таблица (табл. 3). В левой колонке симплекс-таблицы находятся базисные переменные, в колонке свободных членов – правые части соответствующих ограничений. В i-й строке,  
j-м столбце стоит коэффициент при j-й переменной в i-м ограничении (22),  ,  . В последней строке (f – строке) стоит коэффициент с противоположным знаком при j-ой переменной в целевой функции f.  
В последнем столбце стоят значения свободных членов, входящего в ограничения. 

 

Таблица 3

Базисные   переменные	Коэффициенты при переменных								Свободные члены
	x1	x2	…	xm	…	xp	…	xn
x1 x2 … xq … xm	a11 a21 … aq1 … am1	a11 a22 … aq2 … am2	…… ... … … … …	a1m a2m … aqm … aAmn	…… ... … … … …	a1p a2p … aqp … amp	…… ... … … … …	a1n a2n … aqn … amn	b1 b2 … bq … bm
-f	-c1	-c2		-cm		-cp		-cn	0

 

 

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

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

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

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

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

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

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

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

                                         (23)

                                (24)

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

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

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

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

Пример 4

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

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

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

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

Таблица 4 

 

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

 

 

Пример 

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

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

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

Таблица 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 % от общей суммы выделенных средств. Как следует предприятию организовать рекламу, чтобы получить максимальную прибыль?

Решение.

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

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

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

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

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

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

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

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

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

                                           (25)

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

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

                      (26)

(5), (6) – математическая модель задачи организации рекламной деятельности.

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

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

                                      (27)

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

Решение.

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

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