Разделы сайта

Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

Стр 1 из 3Следующая ⇒

Теоретическая часть

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

Для задачи, записанной в форме основной задачи линейного программирования, можно непосредственно указать ее опорный план, если среди векторов P_j_, компонентами которых являются коэффициенты при неизвестных в системе уравнений данной задачи, имеется mединичных (m – число неравенств ограничений, m ≥ 3).

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

Пусть требуется вычислить максимум функции

F = С₁Х₁ + С₂Х₂+...+ С_nХ_n (11.1)

при условиях

(11.2)

.........

x _j ≥ 0 (), (11.3)

где , m < n и среди векторов

Р₁= Р₂= … Р_n нет m единичных.

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

F = С₁Х₁ + С₂Х₂+...+ С_nХ_n –MX_n₊₁ - …- MX_n+m (11.4)

при условиях

(11.5)

...........

x _j ≥ 0 (), (11.6)

где М — некоторое достаточно большое положительное число, конкретное значение которого обычно не задается, называется расширенной задачей по отношению к задаче (11.1) — (11.3).

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

Х=(0; 0;...; 0; b₁; b ₂;...; b _m), который

n нулей

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

Теорема 11.1. Если в оптимальном плане X*=(х₁*; х₂*;...; x_n*; x*_n₊₁;...; x*_n₊_m) расширенной задачи (11.4) — (11.6)значения искусственных переменных х*_n₊_i = 0 (i= ), то X*=(х₁*; х₂*;...; x_n*) является оптимальным планом исходной задачи (11.1) — (11.3).

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

При опорном плане Х=(0; 0;...; 0; b₁; b₂;...; b_m), расширенной задачи значение линейной формы определяется по формуле

(11.7)

а значения равны - . (11.8)

Таким образом, F_o и разности z _j — C_j состоят из двух независимых частей, одна из которых зависит от М, а другая — нет.

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

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

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

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

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

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

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

2) либо не все искусственные векторы исключены, но (m + 2)-я строка не содержит больше отрицательных элементов в столбцах векторов P₁, P₂,.... _Р_n₊_m;

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

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

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

Следовательно, процесс решения исходной задачи (11.1) — (11.3) методом искусственного базиса включает следующие основные этапы:

1) составляют расширенную задачу (11.4) — (11.6);

2) вычисляют опорный план расширенной задачи;

3) с помощью обычных вычислений симплекс-метода исключают искусственные векторы из базиса. В результате либо получают опорный план расширенной задачи, либо устанавливают ее неразрешимость;

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

Практическое применение метода искусственного базиса. Решение задачи ручным способом.

Вычислить минимум функции F = - 2х₁+3х₂- 6х₃- х₄ (11.9)

при условиях

, (11.10)

x₁, x₂, x₃, x₄ ≥ 0. (11.11)

Обратите внимание – в системе ограничений имеются как неравенства обоих типов, так и равенства.

Решение.

Запишем данную задачу в форме основной задачи: вычислить максимум функции F = 2х₁-3х₂+6х₃+х₄ → max (11.12)

при условиях

(11.13)

x₁, x₂, x₃, x₄, х₅, х₆ ≥ 0.

Обратите внимание, что мы ввели дополнительные (это пока не искусственные) переменные во второе и третье неравенства со знаками, соответствующими виду неравенства (превратили неравенства в равенства)

Запишем векторы из коэффициентов при неизвестных:

Р₁ = ; Р₂ = ; Р₃ = ; Р₄ = ; Р₅ = ; Р₆ = . (11.14)

Среди векторов P₁, Р₂, Р₃, Р₄, Р₅ и Р₆только два единичных (Р₄ и Р₅)-, (вектор, в котором элемент равен (-1) за единичный не принимается).

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

F = 2х₁-3х₂+6х₃+х₄ –Mx₇→ max (11.15)

при условиях

, (11.16)

x₁, x₂, x₃, x₄, х₅, х_6,х₇ ≥ 0.

Выберем в качестве основных переменных – переменные х₄, х₅, х₇

Выразим основные переменные через неосновные:

, (11.1)

Приравняем нулю все неосновные переменные х₁ = 0, х₂ = 0, х₃ = 0, х₆ = 0.

Тогда расширенная задача имеет опорный план X^0Р=(0; 0; 0; 24; 22; 0; 10), определяемый системой трех единичных векторов: P₄, P₅, P₇.

Заполняем строки 1-3 первой симплекс -таблицы расширенной задачи (таблица 11.1).

В верхней подстроке записываем значения коэффициентов при целевой функции расширенной задачи (11.15): (2, (-3), 6, 1, 0, 0, (-М)).

Заполняем столбец базиса Р₄, Р₅, Р₇.

Заполняем столбец Сб: коэффициенты при основных переменных в целевой функции расширенной задачи: х₄ = 1, х₅ = 0, х₇ = -М.

Заполняем столбец Р₀ (вектор столбец свободных членов расширенной задачи: 24, 22, 10 - для базисных векторов).

Заполняем столбцы векторов Р1 – Р7.

Таблица 11.1 – Первая симплекс таблица расширенной задачи

i Базис с_б P₀ -3 -M

P₁ P₂ P₃ P₄ P₅ P₆ P₇

P₄ -2

P₅

P₇ -M -1 -1

-8

-10 -1 -2

Рассчитываем значения элементов строк 4 и 5.

F₀ = = 1*24 + 0 * 22 - 10 M (в строку 4 записываем значение без М, в строку 5 – значение при М);

элемент а₄₁ = = 1*2+ 0*1 – 2 = 0;

элемент а₅₁ =1*(- М) = - 1;

элемент а₄₂ = 1*1+ 0*2 –(-3) =4;

элемент а₅₂ = -1*(- М) = 1;

элемент а₄₃ = 1*(-2) + 0*4 –6 = -8;

элемент а₅₃ = 2*(- М) = -2;

элемент а₄₆ = 1* 0 + 0*0 –0 = 0;

элемент а₅₆ = (-1)(- М) =1.

В результате анализа 4 –й и 5-й строк таблицы 11.1 можно сделать следующий вывод. В 5-й строке в столбцах векторов Рj (j= 1, 7) имеется два отрицательных числа (-1 и -2). Наличие этих чисел показывает, что данный опорный план расширенной задачи не является оптимальным.

Переходим к получению нового опорного плана расширенной задачи. В базис вводим вектор Р₃(в котором максимальное по абсолютной величине отрицательное число).

Для определения вектора, исключаемого из базиса, реализуем правило q = min(22/4; 10/2) = 10/2 (отношение 24/(-2) не берется, т.к. отрицательные элементы в столбце не используются). Следовательно, вектор Р₇ исключаем из базиса. Этот вектор не имеет смысла вводить ни в один из последующих базисов, поэтому в дальнейших таблицах столбец данного вектора исключен (таблицы 11.2 и 11.3).

Составляем таблицу II итерации (таблица 11.2). Она содержит только четыре строки, так как искусственный вектор (вектор Р₇, а он единственный) из базиса исключен.

Разрешающая строка – строка 3 (вектора Р₇), разрешающий столбец – столбец вектора Р₃, разрешающий элемент – а₃₃ = 2.

Заполняем столбец вектора нового базиса – Р₄, Р₅, Р_3.

Заполняем столбец Сб (коэффициенты при управляемых переменных, т.е. переменных в целевой функции) – Р₄ = 1; Р₅ = 0; Р₃ = 6.

Заполняем элементы разрешающей строки. Для этого соответствующие элементы строки три таблицы 11.1 делим на значение разрешающего элемента (а₃₃ = 2).

Рассчитываем оставшиеся элементы столбца Р₀:

b₁₀^Н = b₁₀^C- а₁₃^С * b₃₀^Н= 24 – (-2) * 5 = 34;

b₂₀^Н = b₂₀^C- а₂₃^С * b₃₀^Н= 22 – 4 * 5 = 2;

Рассчитываем значение целевой функции на данном шаге F₁

F₁ = |C_б| x |P₀| (скалярное произведение вектора С_б на вектор Р₀)

F₁ = 1 * 34 + 0 * 2 + 6 * 5 = 64.

Рассчитываем значения оставшихся элементов столбца Р₁:

a₁₁^H = a₁₁^C - a₁₃^C* a₃₁^H₌ 2 - (-2) * ½ = 3;

a₂₁^H = a₂₁^C - a₂₃^C* a₃₂^H₌ 1 - 4 * ½ = -1;

Рассчитываем значения оставшихся элементов столбца Р₂:

a₁₂^H = a₁₂^C - a₂₃^C* a₃₂^H₌ 1 - (-2) * (-1/2) = 0;

a₂₂^H = a₂₂^C - a₂₃^C* a₃₂^H₌ 2 - 4 * (- ½) = 4;

Рассчитываем значения оставшихся элементов столбца Р₆:

a₁₆^H = a₁₆^C - a₁₃^C* a₃₆^H₌ 0 -(-2) * (-1/2) = -1;

a₂₆^H = a₂₆^C - a₂₃^C* a₃₆^H₌ 0 - 4 * (- ½) = 2;

Рассчитываем значения элементов 4-й строки Р₆:

∆ ₁= |C_б| x |P₁| - c₁ = 1 * 3 + 0 *(-1) + 6 * ½ - 2 = 4;

∆ ₂= |C_б| x |P₂| - c₂ = 1 * 0 + 0 * 4 + 6 * (-½) – (-3) = 0;

∆ ₃= |C_б| x |P₃| - c₃ = 1 * 0 + 0 * 0 + 6 * 1 – 6 = 0;

∆ ₄= |C_б| x |P₄| - c₄ = 1 * 1 + 0 * 0 + 6 * 0 – 1 = 0;

∆ ₅= |C_б| x |P₅| - c₅ = 1 * 0 + 0 * 1 + 6 * 0 – 0 = 0;

∆ ₆= |C_б| x |P₆| - c₆ = 1 * (-1) + 0 * 2 + 6 *(-1/2) – 0 = -4;

Таблица 11.2- Вторая симплекс – таблица задачи 11.1

i Базис с_б P₀ _F1 -3

P₁ P₂ P₃ P₄ P₅ P₆

P₄ -1

P₅ -1

P₃ 1/2 -1/2 -1/2

-4

Из анализа таблицы 2 следует, что для исходной задачи опорным является план Х= (0; 0; 5; 34; 2). Проверим его на оптимальность. Для этого рассмотрим элементы 4-й строки. В этой строке в столбце вектора Р₆имеется отрицательное число (-4). Следовательно, данный опорный план не является оптимальным и может быть улучшен благодаря введению в базис вектора P6. Из базиса исключается вектор Р₅ (в векторе Р₆ единственное положительное число а₂₆ = 2). Составляем таблицу III итерации.

Таблица 11.3 - Вторая симплекс – таблица задачи 11.1

i Базис с_б _F2 P₀ _F1 -3

P₁ P₂ P₃ P₄ P₅ P₆

P₄ 5/2 1/2

P₆ -1/2 1/2

P₃ 11/2 1/4 1/2 1/4

В 4-й строке таблицы 3 нет отрицательных значений ∆ _j. Это означает, что полученный опорный план исходной задачи Х*=(0; 0; 11/2; 35; 0; 1) является оптимальным. При этом плане значение линейной формы F_max=68.

Отметим, что решение данной задачи можно проводить, используя только одну объединенную таблицу вида 11.4.

Таблица 11. 4 – Объединенная таблица решения задачи 11.1

i Базис с_б P₀ -3 -M

P₁ P₂ P₃ P₄ P₅ P₆ P₇

P₄ -2

P₅

P₇ -M -1 -1

-8

-10 -10 -2

P₄ -1

P₅ -1

P₃ 1/2 -1/2 -1/2

-4

P₄ 5/2 1/2

P₆ -1/2 1/2

P₃ 11/2 1/4 1/2 1/4

12 3 Следующая ⇒

© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.