Как заполнить симплекс таблицу. Преобразование разрешающей колонки. Определение разрешающей строки
Формируем следующую часть симплексной таблицы. Вместо переменной x6 в план 1 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=1. На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x2 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент
РЭ. НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
(0)-(2 * (-2+2M)):1 |
(-1-M)-(-2 * (-2+2M)):1 |
(-2+2M)-(1 * (-2+2M)):1 |
(-M)-(-1 * (-2+2M)):1 |
(-M)-(0 * (-2+2M)):1 |
(0)-(0 * (-2+2M)):1 |
(0)-(1 * (-2+2M)):1 |
(0)-(0 * (-2+2M)):1 |
Получаем новую симплекс-таблицу
Итерация №1.
- 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
- 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент.
- 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее:
min (-, 1: 3, -) = 1/3
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x7 в план 2 войдет переменная x1. Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x7 плана 1 на разрешающий элемент РЭ=3
На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x1 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы
(0)-(1 * (-5+3M)):3 |
(-5+3M)-(3 * (-5+3M)):3 |
(0)-(0 * (-5+3M)):3 |
(-2+M)-(1 * (-5+3M)):3 |
(-M)-(-1 * (-5+3M)):3 |
(0)-(0 * (-5+3M)):3 |
(2-2M)-(-1 * (-5+3M)):3 |
(0)-(1 * (-5+3M)):3 |
Получаем новую симплекс-таблицу:
Один из методов решения оптимизационных задач (как правило связанных с нахождением минимума или максимума ) линейного программирования называется . Симплекс-метод включает в себя целую группу алгоритмов и способов решения задач линейного программирования. Один из таких способов, предусматривающий запись исходных данных и их пересчет в специальной таблице, носит наименование табличного симплекс-метода .
Рассмотрим алгоритм табличного симплекс-метода на примере решения производственной задачи , которая сводится к нахождению производственного плана обеспечивающего максимальную прибыль.
Исходные данные задачи на симплекс-метод
Предприятие выпускает 4 вида изделий, обрабатывая их на 3-х станках.
Нормы времени (мин./шт.) на обработку изделий на станках, заданы матрицей A:
Фонд времени работы станков (мин.) задан в матрице B:
Прибыль от продажи каждой единицы изделия (руб./шт.) задана матрицей C:
Цель производственной задачи
Составить такой план производства, при котором прибыль предприятия будет максимальной.
Решение задачи табличным симплекс-методом
(1) Обозначим X1, X2, X3, X4 планируемое количество изделий каждого вида. Тогда искомый план: (X1, X2, X3, X4 )
(2) Запишем ограничения плана в виде системы уравнений:
(3) Тогда целевая прибыль:
То есть прибыль от выполнения производственного плана должна быть максимальной.
(4) Для решения получившейся задачи на условный экстремум, заменим систему неравенств системой линейных уравнений путем ввода в нее дополнительных неотрицательных переменных (X5, X6, X7 ).
(5) Примем следующий опорный план :
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Занесем данные в симплекс-таблицу :
В последнюю строку заносим коэффициенты при целевой функции и само ее значение с обратным знаком;
(7) Выбираем в последней строке наибольшее (по модулю ) отрицательное число.
Вычислим b = Н / Элементы_выбранного_столбца
Среди вычисленных значений b выбираем наименьшее .
Пересечение выбранных столбца и строки даст нам разрешающий элемент. Меняем базис на переменную соответствующую разрешающему элементу (X5 на X1 ).
- Сам разрешающий элемент обращается в 1.
- Для элементов разрешающей строки – a ij (*) = a ij / РЭ (то есть каждый элемент делим на значение разрешающего элемента и получаем новые данные ).
- Для элементов разрешающего столбца – они просто обнуляются.
- Остальные элементы таблицы пересчитываем по правилу прямоугольника.
a ij (*) = a ij – (A * B / РЭ)
Как видите, мы берем текущую пересчитываемую ячейку и ячейку с разрешающим элементом. Они образуют противоположные углы прямоугольника. Далее перемножаем значения из ячеек 2-х других углов этого прямоугольника. Это произведение (A * B ) делим на разрешающий элемент (РЭ ). И вычитаем из текущей пересчитываемой ячейки (a ij ) то, что получилось. Получаем новое значение - a ij (*) .
(9) Вновь проверяем последнюю строку (c ) на наличие отрицательных чисел . Если их нет – оптимальный план найден, переходим к последнему этапу решения задачи. Если есть – план еще не оптимален, и симплекс-таблицу вновь нужно пересчитать.
Так как у нас в последней строке снова имеются отрицательные числа, начинаем новую итерацию вычислений.
(10) Так как в последней строке нет отрицательных элементов, это означает, что нами найден оптимальный план производства! А именно: выпускать мы будем те изделия, которые перешли в колонку «Базис» - X1 и X2. Прибыль от производства каждой единицы продукции нам известна (матрица C ). Осталось перемножить найденные объемы выпуска изделий 1 и 2 с прибылью на 1 шт., получим итоговую (максимальную! ) прибыль при данном плане производства.
ОТВЕТ:
X1 = 32 шт., X2 = 20 шт., X3 = 0 шт., X4 = 0 шт.
P = 48 * 32 + 33 * 20 = 2 196 руб.
Галяутдинов Р.Р.
© Копирование материала допустимо только при указании прямой гиперссылки на
Если в условии задачи есть ограничения со знаком ≥, то их можно привести к виду ∑a ji b j , умножив обе части неравенства на -1. Введем m дополнительных переменных x n+j ≥0(j =1,m ) и преобразуем ограничения к виду равенств
(2)
Предположим, что все исходные переменные задачи x 1 , x 2 ,..., x n – небазисные. Тогда дополнительные переменные будут базисными, и частное решение системы ограничений имеет вид
x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m . (3)
Так как при этом значение функции цели F 0 = 0 , можно представить F(x) следующим образом:
F(x)=∑c i x i +F 0 =0 (4)
Начальная симплекс-таблица (симплекс-табл. 1) составляется на основании уравнений (2) и (4). Если перед дополнительными переменными x n+j стоит знак «+», как в (2), то все коэффициенты перед переменными x i и свободный член b j заносятся в симплекс-таблицу без изменения. Коэффициенты функции цели при ее максимизации заносятся в нижнюю строку симплекс-таблицы с противоположными знаками. Свободные члены в симплекс-таблице определяют решение задачи.
Алгоритм решения задачи следующий:
1-й шаг. Просматриваются элементы столбца свободных членов. Если все они положительные, то допустимое базисное решение найдено и следует перейти к шагу 5 алгоритма, соответствующему нахождению оптимального решения. Если в начальной симплекс-таблице есть отрицательные свободные члены, то решение не является допустимым и следует перейти к шагу 2.
2-й шаг. Для нахождения допустимого решения осуществляется , при этом нужно решать, какую из небазисных переменных включить в базис и какую переменную вывести из базиса.
Таблица 1.
базисные переменные | Свободные члены в ограничениях | Небазисные переменные | |||||
x 1 | x 2 | ... | x l | ... | x n|||
x n+1 | b 1 | a 11 | a 12 | ... | a 1l | ... | a 1n |
x n+2 | b 2 | a 21 | a 22 | ... | a 2l | ... | a 2n |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
x n+r | b2 | a r1 | a r2 | ... | a rl | ... | a rn |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
x n+m | b m | a m1 | a m2 | ... | a ml | ... | a mn |
F(x) max | F 0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Для этого выбирают любой из отрицательных элементов столбца свободных членов (пусть это будет b 2 ведущим, или разрешающим. Если в строке с отрицательным свободным членом нет отрицательных элементов, то система ограничений несовместна и задача не имеет решения.
Одновременно из БП исключается та переменная, которая первой изменит знак при увеличении выбранной НП x l . Это будет x n+r , индекс r которой определяется из условия
т.е. та переменная, которой соответствует наименьшее отношение свободного члена к элементу выбранного ведущего столбца. Это отношение называется симплексным отношением. Следует рассматривать только положительные симплексные отношения.
Строка, соответствующая переменной x n+r , называется ведущей, или разрешающей. Элемент симплекс-таблицы a rl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим, или разрешающим элементом. Нахождением ведущего элемента заканчивается работа с каждой очередной симплекс-таблицей.
3-й шаг. Рассчитывается новая симплекс-таблица, элементы которой пересчитываются из элементов симплекс-таблицы предыдущего шага и помечаются штрихом, т.е. b" j , a" ji , c" i , F" 0 . Пересчет элементов производится по следующим формулам:
Сначала в новой симплекс-таблице заполнятся строка и столбец, которые в предыдущей симплекс-таблице были ведущими. Выражение (5) означает, что элемент a" rl на месте ведущего равен обратной величине элемента предыдущей симплекс-таблицы. Элементы строки a ri делятся на ведущий элемент, а элементы столбца a jl также делятся на ведущий элемент, но берутся с противоположным знаком. Элементы b" r и c" l рассчитываются по тому же принципу.
Остальные формулы легко записать с помощью .
Прямоугольник строится по старой симплекс-таблице таким образом, что одну из его диагоналей образует пересчитываемый (a ji) и ведущий (a rl) элементы (рис. 1). Вторая диагональ определяется однозначно. Для нахождения нового элемента a" ji из элемента a ji вычитается (на это указывает знак « – » у клетки) произведение элементов противоположной диагонали, деленное на ведущий элемент. Аналогично пересчитываются элементы b" j , (j≠r) и c" i , (i≠l).
4-й шаг. Анализ новой симплекс-таблицы начинается с 1-го шага алгоритма. Действие продолжается, пока не будет найдено допустимое базисное решение, т.е. все элементы столбца свободных членов должны быть положительными.
5-й шаг. Считаем, что допустимое базисное решение найдено. Просматриваем коэффициенты строки функции цели F(x) . Признаком оптимальности симплекс-таблицы является неотрицательность коэффициентов при небазисных переменных в F-строке.
Рис. 1. Правило прямоугольника
Если среди коэффициентов F-строки имеются отрицательные (за исключением свободного члена), то нужно переходить к другому базисному решению. При максимизации функции цели в базис включается та из небазисных переменных (например x l), столбцу которой соответствует максимальное абсолютное значение отрицательного коэффициента c l в нижней строке симплекс-таблицы. Это позволяет выбрать ту переменную, увеличение которой приводит к улучшению функции цели. Столбец, соответствующий переменной x l , называется ведущим. Одновременно из базиса исключается та переменная x n+r , индекс r которой определяется минимальным симплексным отношением:
Строка, соответствующая x n+r , называется ведущей , а элемент симплекс-таблицы a rl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим элементом.
6-й шаг. по правилам, изложенным на 3-м шаге. Процедура продолжается до тех пор, пока не будет найдено оптимальное решение или сделан вывод, что оно не существует.
Если в процессе оптимизации решения в ведущем столбце все элементы неположительные, то ведущую строку выбрать невозможно. В этом случае функция в области допустимых решений задачи не ограничена сверху и F max ->&∞.
Если же на очередном шаге поиска экстремума одна из базисных переменных становится равной нулю, то соответствующее базисное решение называется вырожденным. При этом возникает так называемое зацикливание, характеризующееся тем, что с определенной частотой начинает повторяться одинаковая комбинация БП (значение функции F при этом сохраняется) и невозможно перейти к новому допустимому базисному решению. Зацикливание является одним из основных недостатков симплекс-метода, но встречается сравнительно редко. На практике в таких случаях обычно отказываются от ввода в базис той переменной, столбцу которой соответствует максимальное абсолютное значение отрицательного коэффициента в функции цели, и производят случайный выбор нового базисного решения.
Пример 1. Решить задачу
max{F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0}
Симплексным методом и дать геометрическую интерпретацию процесса решения.
Графическая интерпретация решения задачи представлена на рис. 2. Максимальное значение функции цели достигается в вершине ОДЗП с координатами . Решим задачу с помощью симплекс-таблиц. Умножим второе ограничение на (-1) и введём дополнительные переменные, чтобы неравенства привести к виду равенств, тогда
Исходные переменные x 1 и x 2 принимаем в качестве небазисных, а дополнительные x 3 , x 4 и x 5 считаем базисными и составляем симплекс-таблицу(симплекс-табл. 2). Решение, соответствующее симплекс-табл. 2, не является допустимым; ведущий элемент обведен контуром и выбран в соответствии с шагом 2 приведенного ранее алгоритма. Следующая симплекс-табл. 3 определяет допустимое базисное решение, ему соответствует вершина ОДЗП на рис. 2 Ведущий элемент обведен контуром и выбран в соответствии с 5-м шагом алгоритма решения задачи. Табл. 4 соответствует оптимальному решению задачи, следовательно: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.
Рис. 2. Графическое решение задачи
Для упрощения процесса решения исходные данные задачи линейного программирования при решении ее симплекс методом записываются в специальные симплекс-таблицы. Поэтому одна из модификаций симплекс метода получила название табличный симплекс метод. Задача линейного программирования в каноническом виде:
a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n + x n+1 =b 1
Исходная таблица для задачи имеет следующий вид:
x 1 | x 2 | ... | x n-1 | x n | b | |
F | -a 0,1 | -a 0,2 | ... | -a 0,n-1 | -a 0,n | -b 0 |
x n+1 | a 1,1 | a 1,2 | ... | a 1,n-1 | a 1,n | b 1 |
x n+2 | a 2,1 | a 2,2 | ... | a 2,n-1 | a 2,n | b 2 |
... | ... | ... | ... | ... | ... | ... |
x n+m | a m,1 | a m,2 | ... | a m,n-1 | a m,n | b m |
x 1 , x 2 , x n - исходные переменные, x n+1 , x n+2 , x n+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные , а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным .
Алгоритм симплекс-метода.
Приводим задачу ЛП к каноническому виду
F=a 0,1 x 1 +a 0,2 x 2 +...a 0,n x n +b 0 → max
a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n +x n+1 =b 1
a 2,1 x 1 +a 2,2 x 2 +...a 2,n x n +x n+2 =b 2
.......................................
a m,1 x 1 +a m,2 x 2 +...a m,n x n +x n+m =b m
В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a 0,n =-a 0,n . Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" - коэффициенты запишутся без изменений.
Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче
x 1 | x 2 | ... | x n-1 | x n | b | |
F | -a 0,1 | -a 0,2 | ... | -a 0,n-1 | -a 0,n | -b 0 |
x n+1 | a 1,1 | a 1,2 | ... | a 1,n-1 | a 1,n | b 1 |
x n+2 | a 2,1 | a 2,2 | ... | a 2,n-1 | a 2,n | b 2 |
... | ... | ... | ... | ... | ... | ... |
x n+m | a m,1 | a m,2 | ... | a m,n-1 | a m,n | b m |
Шаг 1. Проверка на допустимость.
Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент a k,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно .
Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.
Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то ко второму.
Шаг 2. Проверка на оптимальность.
На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность Если среди элементов симплексной таблицы, находщихся в строке F (не беря в расчет элемент b 0 - текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.
Если в строке F есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b 0)
a 0,l =min{a 0,i }
l - столбец в котором он находится будет ведущим. Для того, что бы найти ведущую строку, находим отношение соответсвующего свободного члена и элемента из ведущего столбца, при условии, что они неотрицательны.
b k /a k,l =min {b i /a i,l } при a i,l >0, b i >0
k - cтрока, для которой это отношение минимально - ведущая. Элемент a k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x k) исключается из базиса, переменная соответствующая ведущему столбцу (x l) включается в базис.
Пересчитываем симплекс-таблицу по . Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2
Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена - алгоритм завершает работу.
Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.
Правила преобразований симплексной таблицы.
При составлении новой симплекс-таблицы в ней происходят следующие изменения:
- Вместо базисной переменной x k записываем x l ; вместо небазисной переменной x l записываем x k .
- ведущий элемент заменяется на обратную величину a k,l "= 1/a k,l
- все элементы ведущего столбца (кроме a k,l) умножаются на -1/a k,l
- все элементы ведущей строки (кроме a k,l) умножаются на 1/a k,l
- оставшиеся элементы симплекс-таблицы преобразуются по формуле a i,j "= a i,j - a i,l x a k,j / a k,l
Схему преобразования элементов симплекс-таблицы (кроме ведущей строки и ведущего столбца) называют схемой ”прямоугольника”.
Преобразуемый элемент a i,j и соответствующие ему три сомножителя как раз и являются вершинами ”прямоугольника”.
ИСПОЛЬЗОВАНИЕ ТАБЛИЧНОГО СИМПЛЕКС-МЕТОДА ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ОПТИМИЗАЦИИ ЭКОНОМИЧЕСКИХ ЗАДАЧ
ВВЕДЕНИЕ
Цель данного курсового проекта - составить план производства требуемых изделий, обеспечивающий максимальную прибыль от их реализации, свести данную задачу к задаче линейного программирования, решить её симплекс - методом и составить программу для решения задачи этим методом на ЭВМ.
1. КРАТКИЙ ОБЗОР АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДАННОГО ТИПА
1.1 Математическое программирование
Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом: найти экстремум некоторой функции многих переменных f (x 1 , x 2 , ... , x n) при ограничениях g i (x 1 , x 2 , ... , x n) * b i , где g i - функция, описывающая ограничения, * - один из следующих знаков £ , = , ³ , а b i - действительное число, i = 1, ... , m. f называется функцией цели (целевая функция).
Линейное программирование - это раздел математического программирования, в котором рассматриваются методы решения экстремальных задач с линейным функционалом и линейными ограничениями, которым должны удовлетворять искомые переменные.
Задачу линейного программирования можно сформулировать так. Найти max
при условии: a 11 x 1 + a 12 x 2 + . . . + a 1n x n £ b 1 ;
a 21 x 1 + a 22 x 2 + . . . + a 2n x n £ b 2 ;
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
a m1 x 1 + a m2 x 2 + . . . + a mn x n £ b m ;
x 1 ³ 0, x 2 ³ 0, . . . , x n ³ 0 .
Эти ограничения называются условиями неотрицательности. Если все ограничения заданы в виде строгих равенств, то данная форма называется канонической.
В матричной форме задачу линейного программирования записывают следующим образом. Найти max c T x
при условии
где А - матрица ограничений размером (m´n), b (m ´ 1) - вектор-столбец свободных членов, x (n ´ 1) - вектор переменных, с Т = - вектор-строка коэффициентов целевой функции.
Решение х 0 называется оптимальным, если для него выполняется условие с Т х 0 ³ с Т х, для всех х Î R(x).
Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.
Для решения задач данного типа применяются методы:
1) графический;
2) табличный (прямой, простой) симплекс - метод;
3) метод искусственного базиса;
4) модифицированный симплекс - метод;
5) двойственный симплекс - метод.
1.2 Табличный симплекс - метод
Для его применения необходимо, чтобы знаки в ограничениях были вида “ меньше либо равно ”, а компоненты вектора b - положительны.
Алгоритм решения сводится к следующему:
Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.
Если в исходной системе ограничений присутствовали знаки “ равно ”или “ больше либо равно ”, то в указанные ограничения добавляются
искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума.
Формируется симплекс-таблица.
Рассчитываются симплекс-разности.
Принимается решение об окончании либо продолжении счёта.
При необходимости выполняются итерации.
На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом.
1.3 Метод искусственного базиса
Данный метод решения применяется при наличии в ограничении знаков “ равно ”, “ больше либо равно ”, “ меньше либо равно ” и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами m , а в задачи минимизации - с положительными m . Таким образом из исходной получается новая m - задача.
Если в оптимальном решении m - задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении m - задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.
1.4 Модифицированный симплекс - метод
В основу данной разновидности симплекс-метода положены такие особенности линейной алгебры, которые позволяют в ходе решения задачи работать с частью матрицы ограничений. Иногда метод называют методом обратной матрицы.
В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений по частям, соответствующим текущим базисным векторам. Указанная способность делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени счёта. Хорош для ситуаций, когда число переменных n значительно превышает число ограничений m.
В целом, метод отражает традиционные черты общего подхода к решению задач линейного программирования, включающего в себя канонизацию условий задачи, расчёт симплекс-разностей, проверку условий оптимальности, принятие решений о коррекции базиса и исключение Жордана-Гаусса.
Особенности заключаются в наличии двух таблиц - основной и вспомагательной, порядке их заполнения и некоторой специфичности расчётных формул.
Для производства двух видов изделий А и В используется три типа технологического оборудования. На производство единицы изделия А идёт времени, часов: оборудованием 1-го типа - а 1 , оборудованием 2-го типа - а 2 , оборудованием 3-го типа - а 3 .На производство единицы изделия В идёт времени, часов: оборудованием 1-го типа - b 1 , оборудованием 2-го типа - b 2 , оборудованием 3-го типа - b 3 .
На изготовление всех изделий администрацияпредприятия может предоставить оборудование 1-го типа не более, чем на t 1 ,оборудование 2-го типа не более, чем на t 2 , оборудование 3-го типа не более, чем на t 3 часов.
Прибыль от реализации единицы готового изделия А составляет a рублей, а изделия В - b рублей.
Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации. Решить задачу простым симплекс-методом. Дать геометрическое истолкование задачи, используя для этого её формулировку с ограничениями-неравенствами.
а 1 = 1 b 1 = 5 t 1 = 10 a = 2
а 2 = 3 b 2 = 2 t 2 = 12 b = 3
а 3 = 2 b 3 = 4 t 3 = 10
3. РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ
3.1 Построение математической модели задачи
Построение математической модели осуществляется в три этапа:
1. Определение переменных, для которых будет составляться математическая модель.
Так как требуется определить план производства изделий А и В, то переменными модели будут:
x 1 - объём производства изделия А, в единицах;
x 2 - объём производства изделия В, в единицах.
2. Формирование целевой функции.
Так как прибыль от реализации единицы готовых изделий А и В известна, то общий доход от их реализации составляет 2x 1 + 3x 2 (рублей). Обозначив общий доход через F, можно дать следующую математическую формулировку целевой функции: определить допустимые значения переменных x 1 и x 2 , максимизирующих целевую функцию F = 2x 1 + 3x 2 .
3. Формирование системы ограничений.
При определении плана производства продукции должны быть учтены ограничения на время, которое администрация предприятия сможет предоставить на изготовления всех изделий. Это приводит к следующим трём ограничениям:
x 1 + 5x 2 £10;3x 1 + 2x 2 £ 12 ; 2x 1 + 4x 2 £ 10 .
Так как объёмы производства продукции не могут принимать отрицательные значения, то появляются ограничения неотрицательности:
x 1 ³ 0 ; x 2 ³ 0 .
Таким образом, математическая модель задачи представлена в виде: определить план x 1 , x 2 , обеспечивающий максимальное значение функции:
max F = max (2x 1 + 3x 2)
при наличии ограничений:
x 1 + 5x 2 £10;
3x 1 + 2x 2 £ 12 ;
2x 1 + 4x 2 £ 10 .
x 1 ³ 0 ; x 2 ³ 0 .
3.2 Решение задачи вручную
Табличный метод ещё называется метод последовательного улучшения оценки. Решение задачи осуществляется поэтапно.
1. Приведение задачи к форме:
x 1 + 5x 2 £10;
3x 1 + 2x 2 £ 12 ;
2x 1 + 4x 2 £ 10 .
x 1 ³ 0 ; x 2 ³ 0 .
2. Канонизируем систему ограничений:
x 1 + 5x 2 + x 3 =10;
3x 1 + 2x 2 + x 4 = 12 ;
2x 1 + 4x 2 + x 5 = 10 .
x 1 ³ 0 ; x 2 ³ 0 .
A 1 A 2 A 3 A 4 A 5 A 0
3. Заполняется исходная симплекс-таблица и рассчитываются симплекс-разности по формулам:
- текущее значение целевой функции - расчёт симплекс-разностей, где j = 1..6 .