Теория игр и программирование

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

5. Определяется вектор, который нужно вывести из базиса, используя равенство:

 

 

Это условие позволяет найти  направляющую строку. Переменная x_r, соответствующая этой строке, выводится из базисного решения и заменяется переменной x_k направляющего столбца. Элемент a_rk, который стоит на пересечении направляющего столбца и направляющей строки, называется разрешающим элементом.

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

b_r/a_rk,  a_r1/a_rk , ... , a_rn/a_rk.

Остальные элементы новой таблицы определяются по правилу прямоугольника:

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

§4. Метод искусственного базиса.

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

Пусть требуется найти максимум функции

 

При условии 

          

           

где   и среди векторов

;      ;   . . .   ;    .  

нет m единичных.

Определение. Задача, состоящая в определении максимального значения функции

 

при условии 

 

 

 где M – некоторое  достаточно большое положительное  число, конкретное значение которого  обычно не задается, называется  расширенной задачей по отношению к основной задаче.

Расширенная задача имеет  опорный план

 

 определяемый системой  единичных векторов Pn+1, Pn+2, …, Pn+m, образующих  базис m-мерного пространства, который  называется искусственным. Сами  векторы, так же как и переменные xn+i (i=1,m), называются искусственными. Так как расширенная задача имеет опорный план, то ее решение может быть найдено симплексным методом.

 

Теорема. Если в оптимальном  плане 

 

 расширенной задачи  значения искусственных переменных  (i= ), то X=( ) является оптимальным планом основной задачи.

При опорном плане X*=(0, …, 0, , …, ) расширенной задачи значение линейной формы есть 

Таким образом, и разности  состоят из двух частей, одна из которых зависит от M, а другая – нет.

После вычисления , и j их значения, а также исходные данные расширенной задачи заносят в таблицу, которая содержит на одну строку больше, чет обычная симплексная таблица. При этом в (m+2)-ю строку помещают коэффициенты при M, а в (m+1)-ю слагаемые, не содержащие M.

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

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

Итерационный процесс  по (m+2)-й строе ведут до тех  пор, пока:

1) либо все искусственные  векторы не будут исключены  из базиса;

2) либо не все искусственные  векторы исключены, но (m+2)-я строка не содержит больше отрицательных элементов в столбцах векторов 

В первом случае базис  отвечает некоторому опорному плану  исходной задачи и определение ее оптимального плана продолжают по (m+1)-й  строке.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

§5. Понятие двойственности.

Понятие двойственности рассмотрим на примере задачи оптимального использования сырья. Пусть на предприятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы сырья m видов в объемах единиц . Из этих отходов, учитывая специализацию предприятия, можно наладить выпуск n видов неосновной продукции. Обозначим через норму расхода сырья i-го вида на единицу j-й продукции, - цена реализации единицы j-й продукции (реализация обеспечена). Неизвестные величины задачи: — объемы выпуска j-й продукции, обеспечивающие предприятию максимум выручки.

Математическая модель задачи:

                         (1)

                             (2)

                                                         (3)

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

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

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

Эти требования формализуются в виде следующей ЗЛП.

Требование 1 покупающей организации – минимизация покупки:

    (4)

Требование 2 предприятия, реализующего отходы сырья, можно сформулировать в виде системы ограничений. Предприятие  откажется от выпуска каждой единицы  продукции первого вида, если , где левая часть означает выручку за сырьё идущее на единицу продукции первого вида; правая – её цену.

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

         (5)

По смыслу задачи оценки не должны быть отрицательными:

                          (6)

Переменные    называют двойственными оценками или объективно обусловленными оценками.

Задачи (1)-(3) и (4)-(6) называют парой взаимно двойственных ЗПЛ.

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

1. Если прямая задача на максимум, то двойственная к ней — на минимум, и наоборот.
2. Коэффициенты целевой функции прямой задачи являются свободными членами ограничений двойственной задачи.
3. Свободные члены ограничений прямой задачи являются коэффициентами целевой функции двойственной.
4. Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу.
5. Если прямая задача на максимум, то ее система ограничений представляется в виде неравенств типа . Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа .
6. Число ограничений прямой задачи равно числу переменных двойственной, а число ограничений двойственной — числу переменных прямой.
7. Все переменные в обеих задачах неотрицательны.

Теорема. Для любых допустимых планов и прямой и двойственной ЗЛП справедливо неравенство , т.е.

  (7) – основное неравенство  теории двойственности.

Теорема. (критерий оптимальности Канторовича)

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

Теорема. (малая теорема двойственности)

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 2.

§6. Постановка задачи

Челябинский консервный завод начинает выпуск трех видов продукции: салат «Весенний», консервированые овощи, салат «Ассорти». Для их приготовления используется четыре вида продуктов: помидоры, огурцы, перец, редис. Запас данных продуктов ограничен помидоров – 1200 кг, огурцов – 1400 кг, перца – 1000 кг, редиса – 600 кг. На изготовление используется

• салат «Весенний»: помидоров – 5 кг, огурцов –4 кг, перца – 3 кг, редиса – 1 кг
• консервированые овощи: помидоров – 4 кг, огурцов – 4 кг, перца – 3 кг
• салата «Ассорти»: помидоров – 4 кг, огурцов – 6 кг, перца – 2 кг, редиса – 1 кг

Помидоры и огурцы должны быть использованы полностью, остальные  же могут быть оставлены. 

Стоимость единицы продукции  салата «Весенний» - 6 тысяч рублей, консервированных овощей – 5 тыс рублей, салата «Ассорти» - 8 тысяч рублей.

Цель расчетов – найти такие количества выпускаемых  товаров, при которых  прибыль  будет максимальна (при условии  полного расхода помидоров и  огурцов).

A – Салат «Весенний»

B – Консервированые овощи

C – Салат «Ассорти»

a – помидоры

b – огурцы

c – перец

d – редис

 

 

 

 

 

 

 

 

 

§7. Математическое решение

Составим таблицу  исходных данных

Расход продукта на единицу изделия(кг)			Продукты	Запас продуктов(кг)
A	B	C
5	4	4	a	1200
4	4	6	b	1400
3	3	2	c	1000
1	-	1	d	600

 

Составим по таблице систему ограничений

 

 

Общую прибыль от реализации продукции, которую нужно максимизировать  выразим через F:

 

Перед нами ЗЛП в произвольной форме, приведем ее к канонической форме

 

 

 

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

 

 

 

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

 

 

i	базис	С базис	В	6	5	8	0	0
1			1200	5	4	4	0	0	1	0
2			1400	4	4	6	0	0	0	1
3		0	1000	3	3	2	1	0	0	0
4		0	600	1	0	1	0	1	0	0
m+1			0	-6	-5	-8	0	0	0	0
m+2			-2600	-9	-8	-10	0	0	0	0