Лабораторная работа №4

Дана ЗЛП

,

.

В табл. 2.8 приведены значения параметров a, b, c.

Таблица 2.8

Номер варианта	a	b	c	Номер варианта	a	b	c	Номер варианта	a	b	c	Номер варианта	a	b	c
1	1	1	2	6	6	2	2	11	2	2	3	16	3	2	4
2	2	1	2	7	7	2	2	12	4	2	3	17	6	2	4
3	3	1	2	8	2	1	3	13	6	2	3	18	3	3	4
4	4	1	2	9	4	1	3	14	3	1	4	19	6	3	4
5	5	2	2	10	6	1	3	15	6	1	4	20	3	4	4

1. Привести ЗЛП к канонической форме.

2. Решить ЗЛП с помощью симплекс-метода с искусственным базисом.

3. Найти оптимальное решение и вычислить значение целевой функции.

3. Двойственность в злп

1. Основные понятия и определения

Рассмотрим ЗЛП в канонической форме:

(3.1.1)

и ЗЛП в симметричной форме:

(3.1.2)

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

Определение 1: Задача

(3.1.3)

называется задачей двойственной к задаче (3.1.1).

Определение 2. Задача

(3.1.4)

называется двойственной к ЗЛП в симметричной форме.

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

Как следует из вида двойственных задач (3.1.3) и (3.1.4):

1. Количество переменных двойственной задачи совпадает с количеством ограничений исходной задачи;

2. Количество ограничений двойственной задачи совпадает с количеством переменных исходной задачи;

3. Каждому ограничению исходной задачи соответствует переменная двойственной задачи;

4. Количество переменных исходной задачи соответствует ограничение двойственной задачи;

5. Матрица ограничений двойственной задачи является транспонированной по отношению к матрице ограничений исходной задачи;

6. Ограничения двойственной задачи являются неравенствами типа «больше или равно»;

7. Целевые коэффициенты исходной задачи являются правыми частями ограничений двойственной задачи;

8. Правые части ограничений исходной задачи являются целевыми коэффициентами двойственной задачи;

9. Если в исходной задаче отыскивается максимум целевой функции, то в двойственной – минимум;

10. Двойственная задача к двойственной задаче совпадает с исходной.

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

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

Таким образом, алгоритм построения двойственной задачи состоит из двух этапов. На первом этапе задача приводится к виду, соответствующему (3.1.1) или (3.1.2), а на втором этапе строится двойственная задача.

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

Этап 1

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

Шаг 2: Рассматривается целевая функция. Если в исходной задаче требуется найти ее минимум, то все коэффициенты умножаются на минус единицу, а функцию переориентируют на максимум.

Этап 2

Шаг 1: Каждому ограничению исходной задачи приписывается , номер которого соответствует номеру ограничения.

Шаг 2: Выписываются в столбик все переменные исходной задачи.

Шаг 3: К каждой переменной приписывается ограничение двойственной задачи вида ( ).

Шаг 4: Если ограничение с номером i исходной задачи является неравенством, то в двойственной задаче записывается ограничение вида .

Замечание 1. Если i-е ограничение является неравенством, то условие неотрицательности на соответствующую двойственную переменную не накладывается.

Шаг 5: Выписывается целевая функция двойственной задачи

Пример 3.1. Дана ЗЛП:

(3.1.5)

(3.1.6)

(3.1.7)

,

.

Этап 1. Ограничение задачи (3.1.6) является ограничением типа «больше или равно», и в соответствии с алгоритмом его необходимо заменить ограничением «меньше или равно».

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

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

(3.1.5)

(3.1.6`)

(3.1.7)

,

.

Этап 2. Каждому ограничению приписываем двойственную переменную :

	,
	,
	,

,

.

Выписываются все переменные двойственной задачи и к ним приписываются ограничения двойственной:

	,
	,
	,
	,

В соответствии с алгоритмом условие типа накладывается на первую и вторую двойственные переменные:

Целевая функция двойственной задачи имеет вид

.

Окончательный вид двойственной задачи следующий:

,

,

,

,

,

.