Задачи для решения в классе.

Задача. Найдите ОДР и максимум функции, если они существуют.

Задача 2. Найдите ОДР и минимум функции, если они существуют.

Задача 3. Найти ОДР и минимум функции, если они существуют..

Задача 4. Найдите ОДР и минимум функции, если они существуют.

Практика 3

Симплекс – метод

Симплекс – метод позволяет решать задачу при произвольном числе свободных переменных.

Пусть в задаче ЛП имеется n переменных и m независимых линейных ограничений, заданных в форме уравнений. Оптимальное решение будет достигаться в одной из опорных точек, где, по крайней мере, k из переменных обнуляются. Выберем некоторые k переменных в качестве свободный и выразим через них остальные m базисных переменных.

Более подробно этот метод рассмотрим на примере.

Пример.

Решить задачу симплекс-методом. л

(8)

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

(9)

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

(10)

3. Составляем симплекс – таблицу: по горизонтали записываем свободные член и свободные переменные, по вертикали – целевую функцию и базисные переменные.

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

а) если все свободные члены больше нуля, то допустимое решение существует;

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

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

5. Выбираем разрешающий элемент:

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

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

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

Меняем Х ₁↔ Х ₆

Меняем Х ₂↔ Х ₄

Меняем Х ₅↔ Х ₆

7. Нашли допустимое решение. Находим оптимальное решение.

Меняем Х ₂↔ Х ₃

Оптимальное решение найдено.

Дополнительные задачи для закрепления материала.

Задачи для решения.

Решить задачу симплекс – методом.

Задача 3. Решить задачу симплекс – методом.

Задача 4. Решить задачу симплекс – методом.

Практика 4

Двойственная задача

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

Пусть имеется прямая задача, заключающаяся в определении max функции F=a₁x₁+ a₂x₂+…+a_nx_n→max,

При условии:

a₁₁x₁+ a₁₂x₂+…+a_1nx_n <b₁,

…………………………..

a_k1x₁+ a_k2x₂+…+a_knx_n <b_k,

………………………….

a_m1x₁+ a_m2x₂+…+a_mnx_n <b_m, при этом х_j >0 (j=1,l,l<n)

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

G=b₁y₁+ b₂y₂+…+b_ny_n → min, при условиях:

a₁₁y₁+ a₂₁y₂+…+a_m1y_m >c₁,

…………………………..

a_1ly₁+ a_2ly₂+…+a_mly_m >c_l,

a_1ny₁+ a_2ny₂+…+a_mny_m >c_n, при этом y_i >0 (i=1,k,k<m).

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

1. Если прямая задача - задача max, то двойственная задача min.

2. Коэффициенты целевой функции прямой задачи c₁,с₂,…,с_n становятся свободными членами ограничений двойственной задачи.

3. Свободные члены ограничений прямой задачи b₁,b₂,…,b_m становятся коэффициентами целевой функции двойственной задачи.

4. Матрица ограничений двойственной задачи получается путем транспонирования матрицы ограничений прямой задачи.

5. Число переменных в двойственной задачи равно числу ограничений прямой задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи.

6. Если переменная x_j прямой задачи может принимать только неотрицательные значения, j-ое ограничение в двойственной задачи является неравенством вида >. Если же переменная x_j может принимать как положительные, так и отрицательные значения, то j-ое ограничение в двойственной задачи - это уравнение.

Запишем в матричном виде правило перехода от прямой задачи к двойственной.

Прямая задача:	Двойственная задача:
Найти max f()=max при (3.11)	Найти min L()= при (3.12)