Основная и каноническая задачи ЛП

Date: 2015-10-07; view: 463.

Тема 4. СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Контрольные задания

Найти наибольшее и наименьшее значение функции на множестве, заданном указанными неравенствами.

3.1.			3.2.
3.3.			3.4.
3.5.			3.6.
3.7.			3.8.
3.9			3.10.
3.11.
3.13.
3.15.
3.17.
3.19.

Ограничениями основной задачи ЛП являются уравнения, задача имеет вид:

(1)

(2)

(3)

Система (1) содержит m уравнений с n неизвестными. Будем считать, что m<n, все m уравнений линейно независимы. (Напомним, что линейная независимость уравнений предполагает невозможным представить одно уравнение через линейную комбинацию остальных). Тогда любые m переменных можно выбрать (сделать) базисными, оставшиеся n – m переменных — свободными. В каждой системе существует конечное число наборов базисных переменных.

Основная задача (1) — (3) является канонической при выполнении следующих условий:

1. b_i ; ;

2. в каждом уравнении системы ограничений (1) есть базисная переменная. Базисной является переменная, которая встречается в системе уравнений только один раз и входит в уравнение с коэффициентом, равным +1;

3. целевая функция максимизируется: .

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

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

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

1. Убедиться, что все b_i 0, (в противном случае умножить соответствующее уравнение на (–1)).

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

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

3. Каноническая задача подразумевает максимизацию целевой функции, поэтому если поставлена задача , то следует рассматривать функцию . (Очевидно, что функция F(X) достигает наименьшего значения при тех же неизвестных , что и — наибольшего.)