2020-04-20
4720
Симплексный метод линейного программирования относится к универсальным методам, обеспечивающим эффективное решение разнообразных землеустроительных и других экономических задач. Универсальность данного метода проявляется в том, что он позволяет решать задачи различной размерности, в которых технико-экономические коэффициенты (αij) при переменных (Х ij) выражены в разных единицах измерения.
Сущность симплексного метода заключается в нахождении оптимального решения задачи путем последовательного рассмотрения и анализа ее допустимых базисных решений. Геометрически каждое допустимое базисное решение соответствует одной из вершин многоугольника в n –мерном пространстве ограничивающего в соответствии с условиями задачи область допустимых решений (ОДР).
В процессе решения задачи на каждой итерации осуществляется переход из одной вершины ОДР в смежную, связанную с не худшим значением целевой функции. Для этого используется процедура метода главных элементов. Количество итераций, необходимых для получения оптимального решения, находится в пределах от m до 2m, где m -количество ограничений в задаче.
|
|
|
Экономико-математические модели задач линейного программирования, решаемых симплексным методом, могут быть представлены в структурной форме или в развернутом виде. Структурная модель задачи записывается следующим образом:
Найти Zmax,min = 
(3.1)
при условиях: 
/ i=1,2,…m/ (3.2)
Если подробно описать все условия задачи в виде системы неравенств и уравнений, то такая экономико-математическая модель называется развернутой.
В зависимости от сложности решаемых задач экономико-математические модели могут иметь разные размеры, которые определяются произведением количества ограничений на количество переменных (m∙n).
3.1 РЕШЕНИЕ ЗАДАЧ ПРОГРАММИРОВАНИЯ СИМПЛЕКСНЫМ МЕТОДОМ
Экономико-математические модели линейного программирования структурно состоят из трех частей: целевой функции, системы ограничений и условия не отрицательности переменных. Целевая функция выражает основное условие задачи, критерий её оптимальности, ориентированный на максимум или на минимум.
Система ограничений в экономико-математических моделях задач, решаемых симплексным методом, записывается в стандартной форме, т.е. в виде неравенств и уравнений. В зависимости от типа ограничений задачи решаются по алгоритму симплексного метода, или алгоритму данного метода с искусственным базисом.
Рассмотрим алгоритм решения задач симплексным методом, который применяется и при решении задач с искусственным базисом за исключением некоторых особенностей алгоритма на начальных этапах их решения.
|
|
|
Методика решения задач симплексным методом предусматривает соблюдение следующих этапов их решения:
1. Постановка задачи;
2. Составление экономико-математические модели задачи;
3. Составление исходного плана (первой симплексной таблицы);
4. Анализ плана на оптимальность;
5. Улучшение плана;
6. Контроль правильности решения задачи;
7. Анализ оптимального решения задачи и формулирование ответа.
Для более наглядного представления алгоритма симплексного метода решим задачу, выраженную в условных единицах измерения.
1. Постановка задачи
При постановке задачи формулируется (словесно): оптимальные значения, каких неизвестных необходимо найти, при каких условиях (ограничениях) по видам и размерам ресурсов, какая функция цели и на что она ориентирована (на максимум или минимум). Например, необходимо определить оптимальное сочетание объемов производства трех видов продукции (Х1, Х2, Х3) при имеющихся в хозяйстве трех видах ресурсов в размере в1=100, в2=40, в3=50 (это могут быть трудовые ресурсы, удобрения, капиталовложения и т.п.) с целью получения максимальной денежной выручки (или валовой продукции и т.п.).
2. Составление экономико-математические модели задачи
Экономико-математическая модель в симплексном методе составляется в следующей последовательности:
- записывается уравнение функции цели, правая часть которого представляет собой сумму произведений искомых неизвестных (Х1, Х2, Х3) на соответствующие им по условиям задачи коэффициенты целевой функции:
Zmax =20Х1+10Х2+30Х3 (3.3)
- условия задачи записываются в виде неравенств с ограничениями типа ≤. Каждое из неравенств выражает собой ограничения по одному из видов ресурсов, поэтому в левой части неравенства проставляют искомые переменные с коэффициентами, выражающими расход данного вида ресурса на единицу искомой переменной или, наоборот, выход данного вида ресурса с единицы соответствующей переменной. В правой части неравенства проставляется тип ограничения ≤ и величина соответствующего вида ресурса;
- количество неравенств в системе ограничений обусловлено условиями задачи. При записи неравенств необходимо контролировать правильность их оформления: технико-экономические коэффициенты при переменных, состав переменных (в левой части неравенства), вид и размер ресурса (в правой части неравенства) должны строго соответствовать условиям задачи и характеру её постановки.
Таким образом, система ограничений выглядит следующим образом:
3Х1+5Х2+8Х3≤100 (3.4)
2,5Х1+3Х2+6Х3≤40 (3.5)
2Х1+4Х2+3Х3≤50 (3.6)
- после записи основных условий задачи в виде системы ограничений обязательно формулируется условие не отрицательности переменных, так как алгоритм симплексного метода позволяет решать задачи только с положительными значениями переменных (Х j):
Х1≤0; Х2≤0; Х3≤0. (3.7)
Представленная выше форма записи условий задачи в виде неравенств называется стандартной. Для заполнения первой симплексной таблицы (исходного плана) необходимо перейти от стандартной формы записи условий задачи к канонической, а от неё – к симплексной.
Каноническая форма записи условий задачи предусматривает преобразование неравенств (стандартной формы записи) в уравнения, для этого в левую часть каждого из неравенств вводят дополнительные переменные со следующими знаками: с плюсом, если неравенство типа «≤» и с минусом, если неравенство типа «≥». Дополнительным переменным (Х4, Х5, Х6) поочередно присваиваются номера, продолжающие нумерацию основных переменных (Х1, Х2, Х3). В уравнение дополнительные переменные вводятся с коэффициентом 1, а в целевую функцию с нулевыми коэффициентами для исключения их влияния на результаты решения задачи.
|
|
|
Преобразуем приведенную выше систему неравенств в систему уравнений:
3Х1+5Х2+8Х3+Х4≤100 (3.8)
2,5Х1+3Х2+6Х3+Х5≤40 (3.9)
2Х1+4Х2+3Х3+Х6≤50 (3.10)
Для дальнейшего преобразования канонической формы записи в симплексную система уравнений решается относительно дополнительных переменных:
Х4=100-(3Х1+5Х2+8Х3) (3.11)
Х5=40-(2,5Х1+3Х2+6Х3) (3.12)
Х6=50-(2Х1+4Х2+3Х3) (3.13)
Исходя из симплексной формы записи условий задачи, становится ясен экономический смысл дополнительных переменных. На начальном этапе решения задачи принимается условие, что основные переменные равны нулю, а значения дополнительных переменных, исходя из симплексной формы записи, будут равны величинам ресурсов. В нашем примере: при Х1=0, Х2=0, Х3=0 будем иметь Х4=100, Х5=40, Х6=50.
В экономическом отношении это означает, что пока не реализовано ни одно из мероприятий, намечаемых по условиям задачи, ресурсы остаются неиспользованными. Исходя из данной установки, создается исходный базис (исходное условие), на основе которого начинается поиск оптимального решения задачи из числа допустимых её решений.
Если в системе уравнений отражающих условие задачи, количество переменных (n) больше количества ограничений (m), то система имеет множество решений. При этом допустимым решением системы называется любой набор переменных, удовлетворяющих условиям задачи, а допустимым базисным решением – допустимое решение, содержащее не больше, чем m не нулевых переменных. Поэтому первая симплексная таблица (исходный план) содержит допустимое базисное решение задачи. Рассмотрим порядок заполнения первой симплексной таблицы (таблица 3.1).
|
|
|
3. Составление исходного плана (первой симплексной таблицы)
Содержание первой симплексной таблицы и порядок её заполнения рассмотрим последовательно по столбцам и строкам.
Столбец 1 – приводится нумерация строк, соответствующая нумерации ограничений в задаче.
Столбец 2 – записывается только дополнительные переменные (Х4, Х5, Х6), т.к. они составляют исходный базис для начала решения задачи.
Столбец 3 – записываются коэффициенты целевой функции при дополнительных переменных, вошедших в базис. Они равны нулю, т.к. дополнительные переменные (Х4, Х5, Х6), вошедшие в базис, в целевую функцию введены с нулевыми коэффициентами (Сij =0) для исключения влияния дополнительных переменных на величину функции цели (Z).
Столбец 4 – записывается значение ресурсов (свободных членов), стоящих в правой части соответствующего неравенства (уравнения). Исходя из симплексной формы записи условий рассматриваемой задачи дополнительные переменные, вошедшие в базис, выражают неиспользованные ресурсы, поэтому: Х4=100, Х5=40, Х6=50. Следовательно, в столбец свободных членов (в j) записываются исходные величины ресурсов.
Столбцы 5-7 – это столбцы основных переменных (соответственно, Х1, Х2, Х3). В них на пересечении со строками соответствующих уравнений проставляются технико-экономические коэффициенты (аij), стоящие в данных уравнениях при каждой из основных переменных. Так, из первого уравнения (3.8) 3Х1+5Х2+8Х3+Х4=100 коэффициенты при основных переменных (Х1, Х2, Х3), соответственно 3,5 и 8 занесены в столбцы данных переменных по первой строке таблицы (3.1).
Столбцы 8-10 – это столбцы дополнительных переменных (Х4, Х5, Х6), в которых проставляются коэффициенты при данных переменных по каждому уравнению (соответствующим им строкам таблицы), в которое входит соответствующая переменная. Так, дополнительная переменная Х4 входит в первое уравнение с коэффициентом 1, поэтому данный коэффициент записываем в столбец 8 (это столбец Х4) по первой строке таблицы (это строка первого уравнения 3.8). В остальных столбцах дополнительных переменных Х5 и Х6 (столбцы 9,10) по первой строке проставляем нули, т.к. данные дополнительные переменные не входят в первое уравнение.
Столбец 11 – в него записывается суммы, полученные путем сложения свободного члена (в j) и коэффициентов (аij) по соответствующей строке таблицы. Так, если сложить по первой строке таблицы (3.1) свободный член и коэффициенты (100+3+5+8+1=117), то получим число 117, которое и записано в столбце 11. аналогичным образом получаем значения для столбца 11 и по остальным строкам таблицы.
Столбец 12 – в него записываются значения, полученные в результате построчного деления значений свободных членов (в j) на положительные коэффициенты ключевого (k -го) столбца.
Для выполнения таких расчетов необходимо предварительно выбрать ключевой столбец (k –й столбец). В качестве ключевого (k -го) выбирается столбец (из числа столбцов основных переменных Х1, Х2, Х3, т.е. столбцов 5-7), по которому в индексной (m+n) строке таблицы стоит максимальное по абсолютной величине: отрицательное число при решении задачи на максимум и, наоборот, положительное число, при решении задачи на минимум.
В данной задаче таким максимальным по абсолютной величине числом является -30 (т.к. Z→max), стоящий в столбце основной переменной Х3 (столбец 7), следовательно, это и будет ключевой столбец. Присвоим ему литер «К».
Теперь можно выполнить расчеты для заполнения столбца 12. По первой строке указанное отношение 
получаем, разделив свободный член 100 (в 1 =100) на положительный коэффициент 8 (в1 =8), стоящий по данной строке в ключевом столбце. Оно равно 12,5 (
). Запишем его в таблицу 3.1.
Аналогично определяем остальные значения для столбца 12.
Значения, записываемые в столбце 12 служат, в последующем основанием для выбора ключевой строки (l -строки), используемой вместе с ключевым (k- столбцом) столбцом для получения следующей симплексной таблицы (улучшенного плана).
Столбец m+1 – это индексная строка симплексной таблицы. На пересечении m+1 строки и столбца основных членов в i (столбец 4), записывается численное значение функции цели (Z). В первой симплексной таблице (3.1) оно равно нулю (Z =0).
Все остальные элементы индексной (m+1) строки рассчитываются по формуле:
, (3.14)
где Сi – коэффициенты целевой функции при переменных, вошедших в базис;
Cj - коэффициенты целевой функции при переменных (Х ij), по столбцам которых выполняется расчет;
аij – технико-экономические коэффициенты при переменных Х j, стоящих в i -м ограничении.
Так, для столбца переменной Х1 (столбец 3) элемент индексной строки будет рассчитан следующим образом:
Z1-C1 = (0∙3+0∙2,5+0∙2)-20=-20.
Так же рассчитываются остальные элементы индексной строки (для столбцов 5-10). В столбец 11 проставляется сумма элементов по индексной строке (-60).
Для упрощения расчетов часто при заполнении индексной строки первой симплексной таблицы используют следующий подход: при решении задачи на максимум в индексной строке записываются коэффициенты целевой функции (Сj), стоящие при основных переменных, со знаком «-», а при решении задачи на минимум – со знаком «+».
Заполненная первая симплексная таблица (3.1) представляет собой исходный план, который анализируется на оптимальность.
4. Анализ плана на оптимальность
Признаком оптимальности опорного (как исходного, так и последующих) плана является отсутствие в индексной (m+1) строке при решении задачи на минимум – положительных коэффициентов или нулей. Если это условие не выполняется, то план не оптимален и необходимо его улучшать.
В рассматриваемой задаче, решаемой на максимум, исходный план (таблица 3.1) не оптимален, т.к. в индексной строке имеются отрицательные коэффициенты (-20, -10, -30). В связи с этим его необходимо улучшать.
5. Улучшение плана
Новый, улучшенный план, получают на основе преобразования неоптимального плана. Вычислительная процедура улучшения плана заключается в выведении из базиса неоптимального плана одной из базисных переменных и введение в него новой, небазисной переменной. Для осуществления этой процедуры в неоптимальном (улучшаемом плане, т.е. в первой симплексной таблице) выбирают ключевой К-столбец и ключевую l -строку (таблица 3.1).
Ключевой столбец (К-столбец) выбирают, как было отмечено выше, по наибольшему по абсолютной величине: отрицательному коэффициенту индексной строки при решении задачи на максимум, и положительному коэффициенту при решении задачи на минимум.
В первой симплексной таблице (неоптимальном плане) в качестве ключевого нами выбран столбец переменной Х3 (столбец 7), в котором по индексной строке стоит наибольший по абсолютной величине отрицательный коэффициент -30 (Zmax).
Ключевая строка (l -строка) выбирается по минимальному положительному коэффициенту, стоящему в столбце 12. В первой симплексной таблице рассматриваемой задачи в качестве ключевой l -строки выбрана вторая строка, по которой в столбце 12 стоит наименьший положительный коэффициент (6,67).
Коэффициент, стоящий на пересечении ключевой строки и ключевого столбца называется главным или генеральным элементом (alk).
Новую симплексную таблицу (улучшенный план) с новым базисным решением составляют в следующей последовательности:
- вычерчивают новую симплексную таблицу (3.2) по форме первой таблицы, добавляя столбец 13 (для контроля правильности вычислений). Вместо базисной переменной, стоявшей в базисе (столбец 2) по ключевой l -строке предыдущей таблицы в новую таблицу записывают переменную Х j, столбец которой выбран в качестве ключевого. Этим самым в базис новой симплексной таблицы вводится новая базисная переменная, а прежняя – выводится из базиса;
- в столбец 3, рядом с новой переменной, введенной в базис, записывают её коэффициент целевой функции. Остальные базисные переменные и их коэффициенты целевой функции (столбцы 2 и 3) переписываются в новую таблицу из предыдущей без изменения;
- элементы (
) для заполнения в новой таблице строки, стоящей на месте ключевой l -строки предыдущей таблицы, вычисляются как отношение соответствующего элемента (alj) ключевой l -строки на главный элемент (alk) предыдущей таблицы, т.е. по формуле:
, (3.15)
- элементы остальных строк новой симплексной таблицы, за исключением строки, стоящей на месте бывшей ключевой l -строки, пересчитываются по одной из следующих формул:
, (
) (3.16)
или «способом конверта»
, (
) (3.17)
где , аij – однотипные коэффициенты, соответственно новой и предыдущей симплексной таблиц;
, аlj – коэффициенты строки, стоящей в новой таблице на месте бывшей ключевой l -строки и, соответственно, коэффициенты ключевой l -строки в предыдущей таблице;
aik – коэффициенты ключевого К-столбца предыдущей симплексной таблицы;
alk – главный (генеральный) элемент предыдущей симплексной таблицы, стоящий на пересечении ключевых l -строки и К-столбца.
Расчеты по указанным выше формулам выполняются для заполнения всех строк новой симплексной таблицы, включая индексную (m+1) строку, но исключая ключевую l -строку.
В соответствии с вышеизложенным выполнены расчеты по улучшению первого и второго планов (таблицы 3.1 и 3.2) и получен оптимальный план (таблица 3.3).
Таблица 3.1
Первая симплексная таблица
| Номера строк (ограничений), i | Номера переменных, вошедших в базис, Xn+i | Коэффициенты целевой функции при базисной переменной, Сi | Свободные члены (ресурсы), вi | Коэффициенты целевой функции, С j | Сумма по строке
| Отношение
| |||||
| 20 | 10 | 30 | 0 | 0 | 0 | ||||||
| Коэффициенты при небазисных переменных | Коэффициенты при базисных переменных | ||||||||||
| Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | ||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 1 | Х4 | 0 | 100 | 3 | 5 | 8 | 1 | 0 | 0 | 117 | 12,5 |
| 2 | Х5 | 0 | 40 | 25 | 3 | 6 | 0 | 1 | 0 | 52,5 | 6,67 |
| 3 | Х6 | 0 | 50 | 2 | 4 | 3 | 0 | 0 | 1 | 60 | 16,67 |
| m+1 | Zj-Cj | 0 | -20 | -10 | -30 | 0 | 0 | 0 | -60 | ||
Таблица 3.2
Вторая симплексная таблица
| i | Базис, Xn+i | Сi | вi | 20 | 10 | 30 | 0 | 0 | 0 | Сумма по строке
|
| Контроль |
| Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | |||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 1 | Х4 | 0 | 46,66 | -0,333 | 1 | 0 | 1 | -1,333 | 0 | 47,00 | - | 47,00 |
| 2 | Х3 | 30 | 6,667 | 0,417 | 0,5 | 1 | 0 | 0,167 | 0 | 8,751 | 15,86 | 8,751 |
| 3 | Х6 | 0 | 30 | 0,750 | 2,5 | 0 | 0 | -0,5 | 1 | 33,750 | 40 | 33,750 |
| m+1 | 200 | -7,5 | 5 | 0 | 0 | 5 | 0 | 202,500 | - | 202,500 |
Таблица 3.3
Третья симплексная таблица
| i | Базис, Xn+i | Сi | вi | 20 | 10 | 30 | 0 | 0 | 0 | Сумма по строке
|
| Контроль |
| Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | |||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 1 | Х4 | 0 | 51,990 | 0 | 1,399 | 0,799 | 1 | -1,199 | 0 | 53,989 | 53,989 | |
| 2 | Х1 | 20 | 15,988 | 1 | 1,199 | 2,398 | 0 | 0,400 | 0 | 20,985 | 20,985 | |
| 3 | Х6 | 0 | 18,010 | 0 | 1,600 | -1,799 | 0 | -0,799 | 1 | 18,012 | 18,012 | |
| m+1 | 319,909 | 0 | 13,993 | 17,985 | 0 | 8,003 | 0 | 359,890 | 359,890 |
6. Контроль правильности решения задачи
Контроль правильности задачи должен осуществляться на всех этапах её решения: от составления экономико-математической модели задачи до анализа оптимального её решения.
В порядке осуществления текущего контроля правильности решения задачи и исключения «зацикливания», в поиске оптимального её решения необходимо иметь в виду следующее:
- если в ключевом К-столбце все коэффициенты (aik) отрицательные, то решения задачи не существует;
- если в столбце свободных членов (ресурсов) имеются нули, то при последующем решении задачи может произойти зацикливание (вырождение). Для преодоления вырожденности плана нули заменяют на малые положительные числа, не оказывающие влияния на результаты решения задачи;
- признаком возможной вырожденности плана также является наличие двух равных минимальных положительных отношений 
(в столбце 12) при выборе ключевой l -строки. Для преодоления вырожденности плана по данному признаку необходимо в качестве ключевой l -строки выбирать ту, по которой в ключевом К-столбце стоит наибольший положительный коэффициент;
- начиная со второй симплексной таблицы, следует ввести дополнительный столбец «контроль» (столбец 13), элементы которого вычисляются по формулам (3.16 и 3.17) на основе использования соответствующих элементов столбца 11 и предыдущей таблицы.
В каждой из симплексных таблиц, начиная со второй, элементы 11 и 13 по строкам должны полностью совпадать. В случае несовпадения даже одного из элементов необходимо проверить правильность расчета значений элементов данной таблицы по описанному выше алгоритму.
Если перечисленные условия контроля соблюдены, то это гарантирует получение оптимального решения задачи. Контроль оптимального плана осуществляется в процессе его анализа.
7. Анализ оптимального решения задачи и формулирование ответа
Оптимальное решение задачи содержится в последней третьей симплексной таблице, не имеющей в индексной строке отрицательных элементов, так как задача решалась на максимум.
В столбце 2 последней симплексной таблицы (таблица 3.3) содержатся переменные, а в столбце 4 (вi) их численные значения, составляющие оптимальное решение задачи. В нашем примере: Х1=15,988; Х4=51,990; Х6=18,010. При этом переменные, вошедшие в базис в последней симплексной таблице, имеют следующий смысл:
- основные переменные (в нашем примере Х1=15,988) выражают размеры использованных ресурсов;
- дополнительные переменные (Х4=51,990, Х6=18,010) выражают размеры неиспользованных ресурсов в зависимости от того, в ограничении по какому виду ресурса они стоят.
Для контроля правильности решения задачи значения переменных, вошедших в базис, подставляются в соответствующие им уравнения, и проверяется соблюдение условия равенства. Если, в рассматриваемой задаче, поставить значения Х1, Х4, Х6 в систему уравнений (3.8-3.10), получим следующее:
3Х1+5Х2+8Х3+Х4=3∙15,988+51,990=99,954=100
2,5Х1+3Х2+6Х3+Х5=2,5∙15,988=39,97=40
2Х1+4Х2+3Х3+Х6=2∙15,988+18,010=49,986=50
В результате постановки указанных переменных в уравнения видно, что условие равенства соблюдается, т.е. задача решена правильно. Полученное значение основной переменной Х1=15,988 является оптимальным при поставленных в задаче условиях, обеспечивающим максимальное значение целевой функции (Zопт). Оптимальное значение функции цели находится в индексной строке (m+1) по столбцу вi =319,909.
Остальные переменные, не вошедшие в базис, равны нулю, т.к. при заданных условиях задачи мероприятия, обозначенные основными переменными Х2 и Х3, оказались неэффективными.
Исходя из содержания последней симплексной таблицы (оптимального плана) ответ можно сформулировать следующим образом: оптимальным планом предусматривается проведение мероприятия, соответствующего Х1=15,988 единиц, что обеспечивает получение максимального значения функции цели при заданных размерах ресурсов, равное 319,909 единиц.
ТЕХНОЛОГИЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ НАДСТРОЙКИ ПОИСК РЕШЕНИЯ В ПРОГРАММЕ EXCEL
Идея симплекс метода (последовательного улучшения) заключается в том, что начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальным. Симплекс-метод является универсальным, так как позволяет решить практически любую задачу линейного программирования, заданную в каноническом виде /2/.
ПРИМЕР РЕШЕНИЯ. В хозяйстве имеется три вида сельскохозяйственных угодий: пастбище, сенокос, пашня, на которых производят 3 вида сельскохозяйственной продукции. На производство требуется 4 вида ресурсов: площадь сельскохозяйственных угодий, трудовые ресурсы, минеральные удобрения, оросительная вода. Необходимо составить план производства трёх видов продукции, который обеспечит получение ее максимального количества в стоимостном выражении в условиях ограниченности ресурсов. Исходная информация представлена в таблице 3.4.
Таблица 3.4
Исходные данные задачи
| Вид ресурса | Единицы измерения | Запасы | Коэффициент затрат ресурсов для производства единицы продукции | ||
| пастбище | сенокос | пашня | |||
| Площадь сельскохозяйственных угодий | га | 300 | 0,01 | 0,04 | 0,02 |
| Трудовые ресурсы | чел.-дн | 40000 | 0,3 | 2 | 4 |
| Минеральные удобрения | кг | 100000 | 1,5 | 2 | 5 |
| Оросительная вода | м3 | 1000 | 0,2 | 0,25 | 0,3 |
| Стоимость реализации продукции | руб. | 15 | 50 | 100 | |
Обозначим объем продукции с пастбищ – х1, с сенокосов – х2, с пашни – х3. С учетом этих обозначений математическая модель задачи имеет следующий вид:
Z =15х1+50х2+100х3→max.
Решим задачу с использованием поиска решения. Поиск решения – это надстройка Excel, которая позволяет решать оптимизационные задачи.
Введем исходные данные в таблицу 3.5.
Таблица 3.5
Данные задачи, представленные в виде таблицы
| х1 | х2 | х3 | ||
| 15 | 50 | 100 | ||
| 0,01 | 0,04 | 0,02 | 300 | |
| 0,3 | 2 | 4 | 40000 | |
| 1,5 | 2 | 5 | 100000 | |
| 0,2 | 0,25 | 0,3 | 1000 |
Поместим курсор в ячейку Е3, нажмем на кнопку мастер функций. На экране появится диалоговое окно мастера функций (рис. 3.1).
Рис. 3.1 - Окно мастера функий
В окне функции выбираем СУММПРОИЗВ, и на экране появляется диалоговое окно СУММПРОИЗВ. В строку массив 1 введем $A$2:$С$2, в строку массив 2 – A3:С3.
Рис. 1.2 - Окно СУММПРОИЗВ
Введем зависимости для ограничений. Выделим ячейку D3, скопируем и вставим в содержимое ячеек по данному столбцу до ячейки D7. Полученная таблица будет иметь вид:
Таблица 3.6
Таблица зависимостей для ограничений
| х1 | х2 | х3 | ||
| 15 | 50 | 100 | 0 | |
| 0,01 | 0,04 | 0,02 | 0 | 300 |
| 0,3 | 2 | 4 | 0 | 40000 |
| 1,5 | 2 | 5 | 0 | 100000 |
| 0,2 | 0,25 | 0,3 | 0 | 1000 |
Во вкладке данные выберем команду Поиск решения. Назначим ячейку для целевой функции $D$3. Отметим, что целевая функция равна максимальному значению. Поместим курсор в строку Изменяя ячейки. Введем адреса искомых переменных $A$2:$C$2. Поместим указатель мыши на слово добавить. В окне Добавление ограничения в строке ссылка на ячейку введем адрес $D$4, в строке ограничения ввести $E$4. Введем остальные ограничения по данному алгоритму. Далее выберем параметры для решения задачи линейного программирования. Установим флажок в окне Линейная модель и Неотрицательные значения.
Рис. 3.3 - Поиск решения
Нажмем кнопку выполнить. Через некоторое время появится диалоговое окно результатов поиска и заполненные ячейки А2:С2, в ячейке D3 отобразится максимальное значение целевой функции.
Таблица 3.7
Решение задачи
| х1 | х2 | х3 | ||
| 0 | 0 | 3333,33 | ||
| 15 | 50 | 100 | 333333,0 | |
| 0,01 | 0,04 | 0,02 | 66,67 | 300 |
| 0,3 | 2 | 4 | 13333,33 | 40000 |
| 1,5 | 2 | 5 | 16666,67 | 100000 |
| 0,2 | 0,25 | 0,3 | 1000 | 1000 |
Z = 0*х1 + 0*х2 + 3333,33*x3 = 333333,0 руб.
Ответ: Для получения максимального выхода продукции, составляющей 333333,0 руб. в условиях ограниченности ресурсов всю площадь лучше использовать под пашню.
Задания для самостоятельной работы студентов по решению задач симплексным методом представлены в приложении 3.
ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ
1. В чем проявляется универсальность применения симплексного метода?
2. Что понимается под стандартной, канонической и симплексной формами записи условий задачи в симплексном методе?
3. Отличительные признаки в условиях задач, определяющие возможность их решения симплексным методом?
4. Этапы решения задач симплексным методом.
5. Последовательность составления экономико-математической модели симплексной задачи.
6. В каком случае вводятся дополнительные переменные и какой экономический смысл они несут?
7. Порядок заполнения первой симплексной таблицы (исходного плана).
8. Экономический смысл симплексной формы записи условий задачи и отражения их в первой симплексной таблице в виде исходного базисе.
9. Как рассчитываются коэффициенты для заполнения m+1 строки симплексной таблицы?
10. Как проверяется план на вырожденность (признаки вырожденности плана)? Пути преодоления вырожденности плана.
11. Признаки оптимальности плана в задачах, решаемых симплексным методом (при Zmax и Zmin).
12. Порядок выбора ключевого столбца и ключевой строки в неоптимальном плане.
13. Порядок пересчета значений коэффициентов ключевой строки для заполнения строки, стоящей на её месте в новой симплексной таблице (в улучшенном плане).
14. Порядок пересчета строк в улучшаемом плане, кроме строки, стоящей на месте бывшей ключевой строки.
15. Как выполняется контроль правильности решения задачи?
3.2 РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКСНЫМ МЕТОДОМ С ИСКУССТВЕННЫМ БАЗИСОМ
Задачи линейного программирования решаются с помощью симплексного метода с искусственным базисом в том случае, когда в условиях задачи имеются ограничения типа «≥» или «=». При канонической форме записи таких ограничений возникает необходимость введения дополнительной переменной с отрицательным знаком, что противоречит условию неотрицательности переменных. Так как отрицательную дополнительную переменную нельзя вводить в базис, то в этом случае естественного базиса задачи не существует и её нельзя решить по алгоритму симплексного метода.
Для решения таких задач применяют алгоритм симплексного метода с искусственным базисом. Искусственный базис создают путем введения в левую часть уравнения в канонической форме искусственной переменной y.
Так, если по условиям задачи имеется ограничение типа «≥» (или «=»):
, (3.18)
то в канонической форме записи оно выглядит:
, (3.19)
а с введением искусственной переменной «у» оно будет представлено в виде:
. (3.20)
В первой симплексной таблице искусственные переменные «у i» вводятся в базис, как и положительные дополнительные переменные x n+1. Для последующего исключения искусственных переменных «у i» из оптимального плана в функцию цели их вводят с очень большими по абсолютной величине коэффициентами. При этом коэффициенту присваивается знак «-», если задача решается на максимум, и знак «+», если задача решается на минимум.
В симплексной таблице в дополнение к индексной строке m+1 вводится строка m+2. Значения элементов для обеих индексных строк рассчитывается по формуле (3.14). При этом в строку m+2 записываются слагаемые, которые содержат величину М. В связи с этим строку m+2 называют М-строкой, а сам метод называют М-методом.
Порядок заполнения первой симплексной таблицы в М-методе не отличается от порядка, рассмотренного в симплексном методе за исключением заполнения m+2 строки.
Проверка плана на оптимальность осуществляется по тем же признакам, что описаны выше, но по коэффициентам индексной m+2 строки до её выбытия из расчетов.
Если план не оптимален, то для целей его улучшения (перерасчета) выбираются ключевые К-столбец и l -строка. Ключевой столбец выбирают, руководствуясь коэффициентами m+2 строки, не обращая внимания на строку m+1. Ключевую l -строку выбирают по минимальному положительному отношению, т.е. как и в обычном симплексном методе.
В процессе последовательного улучшения планов искусственные переменные «у» будут выведены из базиса и их столбцы вычеркиваются, а коэффициенты m+2 строки будут равны «0» и в ней отпадает необходимость. В базисе останутся только основные и положительные дополнительные переменные, поэтому дальнейший поиск оптимального плана осуществляется по алгоритму симплексного метода, руководствуясь m+1 строкой.
При решении задач М-методом соблюдается та же последовательность (этапы), что и в симплексном методе.
Пример решения задачи симплексным методом с искусственным базисом.
1. Постановка задачи
В хозяйстве планируется использовать массив пашни площадью 1000 га под посевы: пшеницы (Х1), овса (Х2) и ячменя (Х3).
Объем производства зерна ячменя должен быть равен 3200 ц, а пшеницы не менее 8000 ц. Затраты труда на производство продукции на данном массиве пашни должны составлять не более 4000 чел. - дней.
Необходимо составить оптимальную структуру посевов указанных культур, обеспечивающих максимальную стоимость валовой продукции (Zmax).
Исходную информацию представим в виде таблицы (3.8).
2. Составление экономико-математической модели задачи.
В соответствии с условиями задачи экономико-математическая модель в развернутом виде выглядит следующим образом:
Zmax =84Х1+72Х2+56Х3.
пи условиях: 
(3.21)
Таблица 3.8
Исходная информация
| № п/п | Показатели | Единица измерения | Затраты ресурсов на 1 га посевов культур | Тип ограничения | Размер ресурса | ||
| пшеница | овес | ячмень | |||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1. | Площадь пашни | га | 1 | 1 | 1 | ≤ | 1000 |
| 2. | Урожайность | ц/га | 20 | 18 | 16 | ||
| 3. | Объем производства пшеницы | ц | 20 | - | - | ≥ | 8000 |
| ячменя | ц | - | - | 16 | = | 3200 | |
| 4. | Трудовые ресурсы | чел. - дней | 3,3 | 4,0 | 4,2 | ≤ | 4000 |
| 5. | Стоимость валовой продукции | тыс. руб. | 84 | 72 | 56 | → | макс. |
С введением дополнительных переменных задача примет следующий вид:
Zmax =84Х1+72Х2+56Х3+0∙Х4+0∙Х5+0∙Х6-М(у1+ у2)
пи условиях: 
(3.22)
Введем в уравнения, полученные из исходной системы неравенств и имеющие вначале ограничения типа «≥» или «=», искусственные переменные у1 и у2:
Zmax =84Х1+72Х2+56Х3+0Х4+0Х5-М(у1+ у2)
пи условиях: 
(3.23)
3. Составление исходного плана (первой симплексной таблицы)
Исходный план (первая симплексная таблица) заполняются в следующей последовательности (таблица 3.9):
- в базис (столбец 2) из системы уравнений (3.23) вводим дополнительные переменные Х4, Х5, и искусственные переменные у1, у2;
- в столбец 3 (Сi) записываются коэффициенты целевой функции при дополнительных и искусственных переменных, вошедших в базис. При дополнительных переменных это нули, а при искусственных переменных это коэффициент М (с положительным знаком при Z→min и с отрицательным Z→max);
- в столбец 4 (вi) записываются значения свободных ресурсов (свободных членов);
- в столбцы 5-12 по строкам (ограничениям) записываются коэффициенты (аij) при основных, дополнительных и искусственных переменных;
- строки m+1 и m+2 заполняются коэффициентами, рассчитанными по формуле (3.14). Для столбца вi (столбец 4) данная формула примет вид:
, (3.24)
Рассчитанные по данной формуле значения записываются в строку m+1 – без коэффициентов М, а в строку m+2 – с коэффициентами М. Так, для столбца 4 (вi) для строк m+1 и m+2 значения рассчитаны следующим образом:
=0∙1000+0∙4000+(М∙8000)+(-М∙3200)=0-11200М.
Исходя из этого «0» записываем в строку m+1, а значение -11200М в строку m+2.
Для столбца 5 (аналогично и для столбцов 6-12 таблицы 3.5) коэффициенты для заполнения строк m+1 и m+2 получены следующим образом:
=0∙1+0∙3,3+(-М∙20)+(-М∙0)-84=-84-20М.
Коэффициент -84 записываем по строке m+1, а -20 по строке m+2;
- столбец 13 («сумма по строке») заполняется путем суммирования коэффициентов столбцов 4-12 по строке.
После заполнения данной таблицы можно переходить к анализу исходного плана на оптимальность.
4. Анализ плана на оптимальность
До тех пор, пока в базисе имеются искусственные переменные (у1, у2), проверка плана на оптимальность осуществляется по коэффициентам m+2 строки.
В нашем примере исходный план (таблица 3.9) не оптимален, т.к. в m+2 строке стоят отрицательные коэффициенты М. Они должны быть выведены из m+2 строки в процессе решений.
После выведения из базиса искусственных переменных (у1 и у2) план на оптимальность анализируется по коэффициентам m+1 строки, как и в симплексном методе.
В рассматриваемой задаче искусственные переменные были выведены из базиса в таблицах 3.10-3.11. Поэтому четвертая и пятая симплексные таблицы (таблицы 3.12-3.13) анализировались на оптимальность по коэффициентам m+1 строки. Оптимальным является план в пятой симплексной таблице (таблица 3.13), т.к. в m+1 строке нет отрицательных коэффициентов.
5. Улучшение плана
Для улучшения исходного плана (таблица 3.9) в качестве ключевого К-столбца выбран столбец 5 (переменная Х1), имеющий в m+2 строке наибольший по абсолютной величине отрицательный коэффициент (-20М).
По наименьшему положительному отношению (8000׃20=400) в столбце 14 выбираем ключевую l -строку.
Общий порядок улучшения плана в симплексном методе с искусственным базисом мало чем отличается от порядка улучшения плана в обычном симплексном методе. Особенностью улучшения плана в М-методе является то, что при выведении из базиса искусственной переменной (y i) её столбец вычеркивается из дальнейшего рассмотрения. Однако для получения правильной суммы коэффициентов по строке (для заполнения столбца 13 и сравнения её со значением по строке в столбце 15) необходимо выполнять расчеты коэффициентов аij и по этим столбцам (см. таблицы 3.10-3.13).
Первые четыре симплексные таблицы (таблицы 3.9-3.12) содержали неоптимальные планы, поэтому по уже известному алгоритму было выполнено их улучшение.
6. Контроль правильности решения задачи
Контроль правильности решения расчетов выполнен посредством сравнения значений в столбцах 13 и 15 по каждой из строк в симплексных таблицах (таблицы 3.10 -3.13).
Контроль правильности решения задачи выполняется также путем подстановки полученных численных значений основных и дополнительных переменных, вошедших в базис, в систему неравенств (3.21).
Если условия неравенств соблюдается, то полученные значения базисных переменных допустимы и соответствуют оптимальным.
7. Анализ оптимального решения задач и значений коэффициентов последней симплексной таблицы
Численные значения переменных, составляющие оптимальное решение задачи, содержатся в столбце вi (см. столбец 4 таблицы 3.13). В базис последней симплексной таблицы могут входить как основные, так и дополнительные переменные.
Их экономический смысл заключается в следующем: основные переменные выражают величины использованных ресурсов, а дополнительные переменные – недоиспользованные (при ограничении типа «≤») или перерасходованные (при ограничении типа «≥») ресурсы.
Так, в рассматриваемой задаче численные значения основных переменных Х1=800 и Х3=200 выражают оптимальные размеры посевных площадей, соответственно пшеницы и ячменя. Основная переменная Х2 не вошла в базис, что указывает на нецелесообразность посева овса.
Дополнительная переменная Х5=480 чел.- дн. показывает величину недоиспользованных трудозатрат, а дополнительная переменная Х6=8000 ц, показывает величину дополнительного объема производства пшеницы, превышающего установленное ограничение ≥8000 ц (см. формулу 3.21).
Оптимальное значение функции цели стоит на пересечении столбца вi (столбец 4 таблицы 3.13) и m+1 строки. Оно составляет 78400 тыс. руб. и выражает максимальную стоимость валовой продукции при поставленных в задаче условиях.
АНАЛИЗ КОЭФФИЦИЕНТОВ ПОСЛЕДНЕЙ СИМПЛЕКСНОЙ ТАБЛИЦЫ
Анализ коэффициентов последней симплексной таблицы необходим для выбора других возможных направлений эффективного использования имеющихся ресурсов.
Коэффициенты последней симплексной таблицы имеют следующий экономический смысл:
- нулевые и единичные коэффициенты в столбцах основных и дополнительных переменных (столбцы 5,7,9,10 таблицы 3.13) указывают на то, что данные переменные вошли в базис;
- коэффициенты в столбце основной переменной, не вошедшей в базис (Х2), показывают (в обратном знакам направлении) насколько изменятся по строкам численные значения (вi) переменных, вошедших в базис, при изменении (увеличении основной переменной, не вошедшей в базис (Х2) на единицу её величины.
Так, если увеличить посевы овса на 1 га, то это приведет к следующим изменениям численных значений переменных, вошедших в базис (в соответствии со значениями коэффициентов столбца 6 переменной Х2 таблицы 3.13); объем дополнительного производства пшеницы (Х6) уменьшится на 20 ц, не использованные запасы трудовых ресурсов уменьшатся на 0,6 чел.-дн., посевы пшеницы (Х1) сократятся на 1 га. Все эти структурные изменения приведут к уменьшению функции цели на 12 тыс. руб.;
- коэффициенты в столбце дополнительной переменной, не вошедшей в базис (Х4) показывают структурные изменения численных значений переменных аналогично указанному выше, но в соответствии со знаками коэффициентов в столбце данной дополнительной переменной (Х4).
Так, при увеличении Х4 на 1 га значение Х4 увеличится на 20 ц, резерв трудовых ресурсов уменьшится на 3,4 чел.-дн., посевы пшеницы увеличатся на 1 га. Это приведет к увеличению значения целевой функции на 84 тыс. руб.;
- в строке m+1 по столбцам переменных, не вошедших в базис, стоят коэффициенты двойственных оценок, которые показывают насколько изменится значение целевой функции при увеличении соответствующей переменной на единицу её величины. При этом коэффициенты в m+1 строке по столбцам основных переменных показывают изменение функции цели в обратном знаку направлении, а коэффициенты по столбцам дополнительных переменных – в прямом направлении в соответствии со знаком.
ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ
1. Какие признаки указывают на то, что задачу следует решать симплексным методом с искусственным базисом?
2. Как записываются дополнительные и искусственные переменные в ограничения (в уравнения или вместо ограничений типа ≥)?
3. С какими знаками и коэффициентами искусственные переменные y i вводятся в целевую функцию (при Zmin и Zmax) и в базис первой симплексной таблицы?
4. Как рассчитываются коэффициенты для заполнения индексных строк m+1 и m+2?
5. Какие переменные вводятся в базис исходного плана (первой симплексной таблицы)?
6. Коэффициентами какой строки руководствуются при выборе ключевого столбца неоптимального плана?
7. Что понимается под искусственным базисом задачи?
8. Как составляется исходный план (первая симплексная таблица) в задачах, решаемых симплексным методом и искусственным базисом?
9. Когда заканчивают использование m+2 строки и переходят к проверке плана на оптимальность по m+1 строке?
10. Признаки оптимальности плана.
11. Раскройте содержание последней симплексной таблицы.
Таблица 3.9
Первая симплексная таблица
| № ограничений | Базис | Сi | вi | 84 | 72 | 56 | 0 | 0 | 0 | -М | -М | Сумма по строке | Отношение
| Контроль |
| Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | у1 | у2 | |||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 1 | Х4 | 0 | 1000 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1004 | 1000 | |
| 2 | Х5 | 0 | 4000 | 3,3 | 4,0 | 4,2 | 1 | 1 | 0 | 0 | 0 | 4012,5 | 1212 | |
| 3 | у1 | -М | 8000 | 20 | 0 | 0 | 0 | 0 | -1 | 1 | 0 | 8020 | 400 | |
| 4 | у2 | -М | 3200 | 0 | 0 | 16 | 0 | 0 | 0 | 0 | 1 | 3217 | - | |
| 5 | ||||||||||||||
| m+1 | Zj-Cj | 0 | -84 | -72 | -56 | 0 | 0 | 0 | 0 | 0 | -212 | - | ||
| m+2 | -11200М | -20М | 0 | -16М | 0 | 0 | М | -М | -М | -11237М | - | |||
Таблица 3.10
Вторая симплексная таблица
| № ограничений | Базис | Сi | вi | 84 | 72 | 56 | 0 | 0 | 0 | -М | -М | Сумма по строке | Отношение
| Контроль |
| Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | у1 | у2 | |||||||
| 1 | Х4 | 0 | 600 | 0 | 1 | 1 | 1 | 0 | 0,05 | 0,05 0,165 -0,05 0 -4,2 0 | 0 | 603,0 | 600 | 603,0 |
| 2 | Х5 | 0 | 2680 | 0 | 4,0 | 4,2 | 0 | 1 | 0,165 | 0 | 2689,2 | 638 | 2689,2 | |
| 3 | Х1 | 84 | 400 | 1 | 0 | 0 | 0 | 0 | -0,05 | 0 | 401,0 | - | 401,0 | |
| 4 | у2 | -М | 3200 | 0 | 0 | 16 | 0 | 0 | 0 | 1 | 3217,0 | 200 | 3217,0 | |
| m+1 | Zj-Cj | 3360 | 0 | -72 | -56 | 0 | 0 | -4,2 | 0 | 33472,0 | - | 33472,0 | ||
| m+2 | -3200М | 0 | 0 | -16М | 0 | 0 | <||||||||
|
|
6459
6324