Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!
Определение 4.1. Задача, состоящая в определении максимального значения функции
|
|
Теоретическая часть
Метод искусственного базиса
Для задачи, записанной в форме основной задачи линейного программирования, можно непосредственно указать ее опорный план, если среди векторов Pj, компонентами которых являются коэффициенты при неизвестных в системе уравнений данной задачи, имеется mединичных (m – число неравенств ограничений, m ≥ 3).
Однако для многих задач линейного программирования, записанных в форме основной задачи и имеющих опорные планы, среди векторов Рj- не всегда есть mединичных. Рассмотрим такую задачу:
Пусть требуется вычислить максимум функции
F = С1Х1 + С2Х2 +...+ СnХn (11.1)
при условиях
(11.2)
.........
x j ≥ 0 (
), (11.3)
где 
, m < n и среди векторов
Р1 = 
Р2 = 
… Рn 
нет m единичных.
Определение 4.1. Задача, состоящая в определении максимального значения функции
F = С1Х1 + С2Х2 +...+ СnХn –MXn+1 - …- MXn+m (11.4)
при условиях
(11.5)
...........
x j ≥ 0 (
), (11.6)
где М — некоторое достаточно большое положительное число, конкретное значение которого обычно не задается, называется расширенной задачей по отношению к задаче (11.1) — (11.3).
Расширенная задача имеет опорный план
Х=(0; 0;...; 0; b1; b 2;...; b m), который
n нулей
определяется системой единичных векторов Рn+1, Рn+2, ...., Рn+m, образующих базис m-го векторного пространства, который называется искусственным. Сами векторы, так же как и переменные xn+i (i= 1, m), называются искусственными. Так как расширенная задача имеет опорный план, то ее решение может быть получено симплексным методом.
Теорема 11.1. Если в оптимальном плане X*=(х1*; х2*;...; xn*; x*n+1;...; x*n+m) расширенной задачи (11.4) — (11.6)значения искусственных переменных х*n+i = 0 (i= 
), то X*=(х1*; х2*;...; xn*) является оптимальным планом исходной задачи (11.1) — (11.3).
Таким образом, если в полученном оптимальном плане расширенной задачи, значения искусственных переменных равны нулю, то тем самым получен оптимальный план исходной задачи. Поэтому остановимся более подробно на вычислении решения расширенной задачи.
При опорном плане Х=(0; 0;...; 0; b1; b2;...; bm), расширенной задачи значение линейной формы определяется по формуле
(11.7)
а значения 
равны - 
. (11.8)
Таким образом, Fo и разности z j — Cj состоят из двух независимых частей, одна из которых зависит от М, а другая — нет.
После вычисления F0 и 
их значения, а также исходные данные расширенной задачи заносят в таблицу, которая содержит на одну строку больше, чем обычная симплексная таблица. При этом в (m + 2)-ю строку помещают коэффициенты при М, а в (m+1)-ю—слагаемые, не содержащие М.
При переходе от одного опорного плана к другому в базис вводят вектор, соответствующий наибольшему по абсолютной величине отрицательному числу (m + 2)-й строки.
Искусственный вектор, исключенный из базиса в результате некоторой итерации, в дальнейшем не имеет смысла вводить ни в один из последующих базисов и, следовательно, преобразование столбцов этого вектора излишне.
Необходимо иметь ввиду, что возможны случаи, когда в результате некоторой итерации ни один из искусственных векторов из базиса не будет исключен.
Пересчет симплекс-таблиц при переходе от одного опорного плана к другому производят по общим правилам симплексного метода.
Итерационный процесс по (m + 2)-й строке ведут до тех пор, пока:
1) либо все искусственные векторы не будут исключены из базиса;
2) либо не все искусственные векторы исключены, но (m + 2)-я строка не содержит больше отрицательных элементов в столбцах векторов P1, P2,.... Рn+m;
В первом случае базис отвечает некоторому опорному плану исходной задачи и определение ее (исходной задачи) оптимального плана продолжают по (m+1)-й строке.
Во втором случае, если элемент, стоящий в (m+2)-й строке столбца вектора Ро отрицателен, исходная задача не имеет решения; если же он равен нулю, то полученный опорный план исходной задачи является вырожденным и базис содержит по крайней мере один из векторов искусственного базиса.
Если исходная задача содержит несколько единичных векторов, то их следует включить в искусственный базис.
Следовательно, процесс решения исходной задачи (11.1) — (11.3) методом искусственного базиса включает следующие основные этапы:
1) составляют расширенную задачу (11.4) — (11.6);
2) вычисляют опорный план расширенной задачи;
3) с помощью обычных вычислений симплекс-метода исключают искусственные векторы из базиса. В результате либо получают опорный план расширенной задачи, либо устанавливают ее неразрешимость;
4) используя полученный опорный план расширенной задачи, либо получают симплекс-методом оптимальный план исходной задачи, либо устанавливают ее неразрешимость.
Практическое применение метода искусственного базиса. Решение задачи ручным способом.
Вычислить минимум функции F = - 2х1+3х2 - 6х3 - х4 (11.9)
при условиях
,
, (11.10)
,
x1, x2, x3, x4 ≥ 0. (11.11)
Обратите внимание – в системе ограничений имеются как неравенства обоих типов, так и равенства.
Решение.
Запишем данную задачу в форме основной задачи: вычислить максимум функции F = 2х1-3х2+6х3+х4 → max (11.12)
при условиях
(11.13)
x1, x2, x3, x4, х5, х6 ≥ 0.
Обратите внимание, что мы ввели дополнительные (это пока не искусственные) переменные во второе и третье неравенства со знаками, соответствующими виду неравенства (превратили неравенства в равенства)
Запишем векторы из коэффициентов при неизвестных:
Р1 = 
; Р2 = 
; Р3 = 
; Р4 = 
; Р5 = 
; Р6 = 
. (11.14)
Среди векторов P1, Р2, Р3, Р4, Р5 и Р6только два единичных (Р4 и Р5)-, (вектор, в котором элемент равен (-1) за единичный не принимается).
В левую часть третьего уравнения системы ограничений (там, где нет единичного вектора) задачи добавим дополнительную неотрицательную переменную х7) с тем же знаком, что и свободный член), и рассмотрим расширенную задачу, состоящую в максимизации функции
F = 2х1-3х2+6х3+х4 –Mx7 → max (11.15)
при условиях
,
, (11.16)
,
x1, x2, x3, x4, х5, х6, х7 ≥ 0.
Выберем в качестве основных переменных – переменные х4, х5, х7
Выразим основные переменные через неосновные:
,
, (11.1)
.
Приравняем нулю все неосновные переменные х1 = 0, х2 = 0, х3 = 0, х6 = 0.
Тогда расширенная задача имеет опорный план X0Р=(0; 0; 0; 24; 22; 0; 10), определяемый системой трех единичных векторов: P4, P5, P7.
Заполняем строки 1-3 первой симплекс -таблицы расширенной задачи (таблица 11.1).
В верхней подстроке записываем значения коэффициентов при целевой функции расширенной задачи (11.15): (2, (-3), 6, 1, 0, 0, (-М)).
Заполняем столбец базиса Р4, Р5, Р7.
Заполняем столбец Сб: коэффициенты при основных переменных в целевой функции расширенной задачи: х4 = 1, х5 = 0, х7 = -М.
Заполняем столбец Р0 (вектор столбец свободных членов расширенной задачи: 24, 22, 10 - для базисных векторов).
Заполняем столбцы векторов Р1 – Р7.
Таблица 11.1 – Первая симплекс таблица расширенной задачи
| i | Базис | сб | P0 | -3 | -M | |||||
| P1 | P2 | P3 | P4 | P5 | P6 | P7 | ||||
| P4 | -2 | |||||||||
| P5 | ||||||||||
| P7 | -M | -1 | -1 | |||||||
| -8 | ||||||||||
| -10 | -1 | -2 |
Рассчитываем значения элементов строк 4 и 5.
F0 = 
= 1*24 + 0 * 22 - 10 M (в строку 4 записываем значение без М, в строку 5 – значение при М);
элемент а41 = 
= 1*2+ 0*1 – 2 = 0;
элемент а51 =1*(- М) = - 1;
элемент а42 = 1*1+ 0*2 –(-3) =4;
элемент а52 = -1*(- М) = 1;
элемент а43 = 1*(-2) + 0*4 –6 = -8;
элемент а53 = 2*(- М) = -2;
элемент а46 = 1* 0 + 0*0 –0 = 0;
элемент а56 = (-1)(- М) =1.
В результате анализа 4 –й и 5-й строк таблицы 11.1 можно сделать следующий вывод. В 5-й строке в столбцах векторов Рj (j= 1, 7) имеется два отрицательных числа (-1 и -2). Наличие этих чисел показывает, что данный опорный план расширенной задачи не является оптимальным.
Переходим к получению нового опорного плана расширенной задачи. В базис вводим вектор Р3 (в котором максимальное по абсолютной величине отрицательное число).
Для определения вектора, исключаемого из базиса, реализуем правило q = min(22/4; 10/2) = 10/2 (отношение 24/(-2) не берется, т.к. отрицательные элементы в столбце не используются). Следовательно, вектор Р7 исключаем из базиса. Этот вектор не имеет смысла вводить ни в один из последующих базисов, поэтому в дальнейших таблицах столбец данного вектора исключен (таблицы 11.2 и 11.3).
Составляем таблицу II итерации (таблица 11.2). Она содержит только четыре строки, так как искусственный вектор (вектор Р7, а он единственный) из базиса исключен.
Разрешающая строка – строка 3 (вектора Р7), разрешающий столбец – столбец вектора Р3, разрешающий элемент – а33 = 2.
Заполняем столбец вектора нового базиса – Р4, Р5, Р3.
Заполняем столбец Сб (коэффициенты при управляемых переменных, т.е. переменных в целевой функции) – Р4 = 1; Р5 = 0; Р3 = 6.
Заполняем элементы разрешающей строки. Для этого соответствующие элементы строки три таблицы 11.1 делим на значение разрешающего элемента (а33 = 2).
Рассчитываем оставшиеся элементы столбца Р0 :
b10Н = b10C - а13С * b30Н = 24 – (-2) * 5 = 34;
b20Н = b20C - а23С * b30Н = 22 – 4 * 5 = 2;
Рассчитываем значение целевой функции на данном шаге F1
F1 = |Cб| x |P0| (скалярное произведение вектора Сб на вектор Р0)
F1 = 1 * 34 + 0 * 2 + 6 * 5 = 64.
Рассчитываем значения оставшихся элементов столбца Р1 :
a11H = a11C - a13C * a31H = 2 - (-2) * ½ = 3;
a21H = a21C - a23C * a32H = 1 - 4 * ½ = -1;
Рассчитываем значения оставшихся элементов столбца Р2 :
a12H = a12C - a23C * a32H = 1 - (-2) * (-1/2) = 0;
a22H = a22C - a23C * a32H = 2 - 4 * (- ½) = 4;
Рассчитываем значения оставшихся элементов столбца Р6 :
a16H = a16C - a13C * a36H = 0 -(-2) * (-1/2) = -1;
a26H = a26C - a23C * a36H = 0 - 4 * (- ½) = 2;
Рассчитываем значения элементов 4-й строки Р6 :
∆ 1 = |Cб| x |P1| - c1 = 1 * 3 + 0 *(-1) + 6 * ½ - 2 = 4;
∆ 2 = |Cб| x |P2| - c2 = 1 * 0 + 0 * 4 + 6 * (-½) – (-3) = 0;
∆ 3 = |Cб| x |P3| - c3 = 1 * 0 + 0 * 0 + 6 * 1 – 6 = 0;
∆ 4= |Cб| x |P4| - c4 = 1 * 1 + 0 * 0 + 6 * 0 – 1 = 0;
∆ 5= |Cб| x |P5| - c5 = 1 * 0 + 0 * 1 + 6 * 0 – 0 = 0;
∆ 6= |Cб| x |P6| - c6 = 1 * (-1) + 0 * 2 + 6 *(-1/2) – 0 = -4;
Таблица 11.2- Вторая симплекс – таблица задачи 11.1
| i | Базис | сб | P0 F1 | -3 | |||||
| P1 | P2 | P3 | P4 | P5 | P6 | ||||
| P4 | -1 | ||||||||
| P5 | -1 | ||||||||
| P3 | 1/2 | -1/2 | -1/2 | ||||||
| -4 |
Из анализа таблицы 2 следует, что для исходной задачи опорным является план Х= (0; 0; 5; 34; 2). Проверим его на оптимальность. Для этого рассмотрим элементы 4-й строки. В этой строке в столбце вектора Р6имеется отрицательное число (-4). Следовательно, данный опорный план не является оптимальным и может быть улучшен благодаря введению в базис вектора P6. Из базиса исключается вектор Р5 (в векторе Р6 единственное положительное число а26 = 2). Составляем таблицу III итерации.
Таблица 11.3 - Вторая симплекс – таблица задачи 11.1
| i | Базис | сб F2 | P0 F1 | -3 | |||||
| P1 | P2 | P3 | P4 | P5 | P6 | ||||
| P4 | 5/2 | 1/2 | |||||||
| P6 | -1/2 | 1/2 | |||||||
| P3 | 11/2 | 1/4 | 1/2 | 1/4 | |||||
В 4-й строке таблицы 3 нет отрицательных значений ∆ j. Это означает, что полученный опорный план исходной задачи Х*=(0; 0; 11/2; 35; 0; 1) является оптимальным. При этом плане значение линейной формы Fmax=68.
Отметим, что решение данной задачи можно проводить, используя только одну объединенную таблицу вида 11.4.
Таблица 11. 4 – Объединенная таблица решения задачи 11.1
| i | Базис | сб | P0 | -3 | -M | |||||
| P1 | P2 | P3 | P4 | P5 | P6 | P7 | ||||
| P4 | -2 | |||||||||
| P5 | ||||||||||
| P7 | -M | -1 | -1 | |||||||
| -8 | ||||||||||
| -10 | -10 | -2 | ||||||||
| P4 | -1 | |||||||||
| P5 | -1 | |||||||||
| P3 | 1/2 | -1/2 | -1/2 | |||||||
| -4 | ||||||||||
| P4 | 5/2 | 1/2 | ||||||||
| P6 | -1/2 | 1/2 | ||||||||
| P3 | 11/2 | 1/4 | 1/2 | 1/4 | ||||||
|
|