Алгорим симплексного метода решения злп
1. Исходное опорное решение задачи записывается в полную симплексную таблиц (табл.1).
| № таблицы | cj | -c0 | ck+1 | … | cj* | … | cn | c0 |
| ci | ai0 | xk+1 | … | xj* | … | xn | ||
| c1 | x1 | a10 | a1+1 | … | a1j* | … | a1n | |
| c2 | x2 | a20 | a2+1 | … | a2j* | … | a2n | |
| ci* | xi* | ai*0 | ai*k+1 | … | ai*j* | … | ai*n | |
| … | … | … | … | … | … | … | … | … |
| ck | xk | ak0 | akk+1 | … | akj* | … | akn | |
| ∆j | z=∆0 | ∆k+1 | … | ∆j* | … | ∆n | - |
2. В первую строку таблицы записываются коэффициенты целевой функции при свободных переменных, причем свободный член целевой функции записывается с противоположным знаком. В первый столбец записываются коэффициенты целевой функции при базисных переменных. Базисные переменные записываются во втором столбце, а свободные переменные во второй строке.
3. Подсчитываются оценки по формуле оценок:
и записываются в последнюю строку таблицы.
4. Проверка решения по критерию оптимальности: решение задачи на максимум целевой функции оптимально, если все оценки при переменных неотрицательные. Если критерий выполняется, то переход к пункту 13, если нет, то переход к пункту 5.
5. Разрешающий столбец выбирается по минимальной отрицательной оценке (по отрицательной оценке наибольшей по абсолютной величине). Если наименьших отрицательных оценок несколько, то разрешающий столбец условимся выбирать по наименьшему номеру с наименьшей отрицательной оценкой.
6. Если в разрешающем столбце есть хотя бы один положительный элемент то переход к пункту 7. Если нет, то целевая функция не ограничена.
7. Вычисляются симплексные отношения, то есть отношения неотрицательных свободных членов к строго положительным элементам разрешающего столбца, и записываются в последний столбец.
8. По наименьшему симплексному отношению находится разрешающая строка. Если минимальных симплексных отношений несколько, то условимся разрешающей брать строку с меньшим номером из минимальных симплексных отношений.
9. На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент.
10. Производится пересчет таблицы:
а) элемент, стоящий на месте разрешающего равен взаимообратному с разрешающим элементом числу:
;
б) все остальные элементы разрешающего столбца, включая и оценку, делятся на разрешающий элемент и умножаются на минус единицу:
;
в) все элементы разрешающей строки, кроме разрешающего элемента, делятся на разрешающий элемент:
;
г) все остальные элементы таблицы, включая и строку оценок, подсчитываются по правилу прямоугольника или по формуле:
.
Правило прямоугольника. Тот элемент, который заменяют, соединить диагональю с разрешающим элементов. На полученной диагонали построить прямоугольник. Провести вторую диагональ.
Из элемента, который заменяют, вычесть дробь, числителем которой является вторая диагональ прямоугольника, а знаменателем разрешающий элемент.
Вычисления по правилу многоугольника:
| j1 | … | j* | ||
| i1 | … | |||
| … | ||||
| i* | … |
| j* | … | j2 | ||
| i* | … | |||
| … | ||||
| i2 | … |
| j* | … | j2 | ||
| i1 | … | |||
| … | ||||
| i* | … |
| j1 | … | j* | ||
| i* | … | |||
| … | ||||
| i2 | … |
11. В разрешающей строке в столбец базисных переменных записывается переменная разрешающего столбца, а в столбец коэффициентов целевой функции при базисных переменных записывается коэффициент целевой функции разрешающего столбца.
В разрешающем столбце в строке свободных переменных записывается переменная разрешающей строки, а в строку коэффициентов целевой функции при свободных переменных записывается коэффициент целевой функции разрешающей строки.
12. Переход к пункту 4.
13. Запись оптимального решения и значения целевой функции.
Задача. Требуется определить оптимальное сочетание трех культур: гречихи, гороха и ячменя. Для возделывания этих культур выделено 6000 га пашни, 20000 человеко-дней ручного труда и 10000 человеко-дней механизированного труда. Культуры характеризуются следующими показателями:
| Культура | Затраты труда на 1 га, чел.-дн. | Стоимость продукции в расчете на 1 га, руб | |
| ручного | механизированного | ||
| Гречиха | |||
| Горох | 2,5 | ||
| Ячмень | 2,5 | 1,5 |
Ресурсы могут быть недоиспользованы. Критерий оптимальности - максимум валовой продукции в стоимостном выражении. Решить задачу в полных и сокращенных таблицах.
Введем переменные:
х1 - площадь под гречихой, га;
х2 - площадь под горохом, га;
х3 - площадь под ячменем, га.
z - целевая функция.
Составим исходную форму задачи:
Перейдем к канонической форме задачи. Получим:
Решим задачу в сокращенных таблицах, при этом сократим свободные члены в 1000 раз.
| № 1 | cj | 0 | 175 | 125 | 140 | c0 |
| ci | СП БП | aj0 | x1 | x2 | x3 | |
| 0 | x4 | 6 | 1 | 1 | 1 | 6:1=6 |
| 0 | x5 | 20 | 5 | 2,5 | 2,5 | 20:5=4 i* |
| 0 | x6 | 10 | 2 | 1 | 1,5 | 10:2=5 |
| ∆j | 0 | -175 | -125 | -140 | - |
j*
| № 2 | cj | 0 | 0 | 125 | 140 | c0 |
| ci | СП БП | aj0 | x5 | x2 | x3 | |
| 0 | x4 | 2 | -1/5 | 1/2 | 1/2 | 2:1/2=4 i* |
| 175 | x1 | 4 | 1/5 | 1/2 | 1/2 | 4:1/2=8 |
| 0 | x6 | 2 | -2/5 | 0 | 1/2 | 2:1/2=4 |
| ∆j | 700 | 35 | -37,5 | -52,5 | - |
j*
| № 3 | cj | 0 | 0 | 125 | 0 | c0 |
| ci | СП БП | aj0 | x5 | x2 | x4 | |
| 140 | x3 | 4 | -2/5 | 1 | 2 | |
| 175 | x1 | 2 | 2/5 | 0 | -1 | |
| 0 | x6 | 0 | -1/5 | -1/2 | -1 | |
| ∆j | 910 | 14 | 15 | 105 | - |
Так как все оценки свободных переменных неотрицательные, то решение оптимальное.
Выпишем оптимальное решение, увеличив свободные члены в 1000 раз:
х (2000; 0; 4000; 0; 0; 0); max z=910000.
Получим х1 = 2000 га - площадь под гречихой;
х2 = 0 га - площадь под горохом;
х3 = 4000 га - площадь под ячменем.
Все ресурсы использованы полностью, так как x4= x5= x6=0, максимальный валовой сбор продукции 910000 руб.
1.6. Задача линейного программирования и ее
графическое решение
Рассмотрим построение математической модели и решение оптимизационной задачи ЛП.
Пример 2.1.1. (Задача фирмы Reddy Mikks.) Небольшая фабрика фирмы Reddy Mikks изготовляет два вида красок: для внутренних (1) и наружных (2) работ. Продукция обоих видов поступает в оптовую продажу. Для производства красок используются два исходных продукта — А и В. Максимально возможные суточные запасы их продуктов составляют 6 и 8т соответственно. Расходы А и В на 1т соответствующих красок приведены в таблице.
Изучение рынка сбыта показало, что суточный спрос на краску 1 никогда не превышает спроса на краску 2 более чем на 1т. Кроме того, установлено, что спрос на краску 1 никогда не превышает 2 т в сутки.
Оптовые цены одной тонны красок равны: 3 тыс. долл. для краски 2, 2 тыс. долл. для краски 1.
| Исходный продукт | Расход исходных продуктов (в тоннах) на тонну краски | Максимально возможный запас, т | |
| краска 1 | краска 2 | ||
| А | |||
| В |
Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?
Построение математической модели.
Процесс построения математической модели для решения поставленной задачи можно начать с ответов на три следующие вопроса:
1. Для определения каких величин должна быть построена модель? Другими словами, как идентифицировать переменные (искомые величины) данной задачи?
2. Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, характерные для моделируемой системы?
3. В чем состоит цель, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи?
Конструктивный путь формулировки ответов на поставленные вопросы состоит в том, чтобы словесно выразить суть проблемы. Рассматриваемую ситуацию можно охарактеризовать следующим, образом.
Фирме требуется определить объемы производства (в тоннах) каждой из красок, максимизирующие доход (в тысячах долларов) от реализации продукции, с учетом ограничений на спрос и расход исходных продуктов.
Трудность построения математической модели заключается в идентификации переменных и последующем представлении цели и ограничений в виде математических функций этих переменных. В рассматриваемом случае мы имеем следующее.
Переменные. Так как нужно определить объемы производства каждого вида краски, переменными в модели являются
х1 — суточный объем производства краски 1 (в тоннах);
х2 — суточный объем производства краски 2 (в тоннах).
Целевая функция. Так как стоимость 1 т краски 2 равна 3 тыс. долл., суточный доход от ее продажи составит 3 х2 тыс. долл. Аналогично доход от реализации х1 тонн краски 1 составит 2 тыс. долл. в сутки. При допущении независимости объемов сбыта каждой из красок общий доход равен сумме двух слагаемых — дохода от продажи краски 2 и дохода от продажи краски 1.
Обозначив общий доход, (в тыс. долл.) через z, можно дать следующую математическую формулировку целевой функции: определить (допустимые) значения х2 и х1 максимизирующие величину общего дохода z=3 х2 - 2∙x1.
Ограничения. При решении рассматриваемой задачи должны быть учтены ограничения на расход исходных продуктов и спрос на изготовляемые краски. Ограничение на расход исходных продуктов можно записать следующим образом
Это приводит к следующим двум ограничениям (см. условия задачи):
| х 2х |
Ограничения на величину спроса на продукцию имеют вид
Математически эти ограничения записываются следующим образом:
- (соотношение величин спроса на краску 1 и краску 2),
- (максимальная величина спроса на краску 1).
Неявное (т. е. «подразумеваемое») ограничение заключается в том, что объемы производства продукции не могут принимать отрицательных значений (т. е. быть меньше нуля). Чтобы предотвратить получение таких недопустимых решений, потребуем выполнения условия неотрицательности переменных, т. е, введем ограничения на их знак:
- (объем производства краски 1),
- (объем производства краски 2).
Итак, математическую модель можно записать следующим образом.
Определить суточные объемы производства (х1 и х2) краски 1 и краски 2 (в тоннах), при которых достигается
- (целевая функция)
при
Что определяет линейный характер построенной модели? С формальных позиций данная модель является линейной потому, что все входящие в нее функции (ограничения и целевая функция) линейны. Линейность предполагает наличие двух свойств — пропорциональности и аддитивности.
1. Пропорциональность означает, что вклад каждой переменной (т.е. х2 и х1) в целевую функцию и общий объем потребления соответствующих ресурсов прямо пропорционален уровню (величине) этой переменной. Если, например, фирма будет предоставлять покупателям скидку, продавая краску 2 по цене 2,5 тыс. долл. за тонну при объеме закупок свыше 2 т, то в такой, ситуации не будет выполняться исходное условие задачи, заключающееся в том, что производство одной тонны краски 2 обеспечивает доход от реализации, равный 3 тыс. долл. В новых условиях этот доход будет равен 3 тыс. долл. при и 2,5 тыс. долл. при . т. е. прямая пропорциональность между доходом фирмы и величиной х2 не имеет места.
2. Аддитивность заключается в том, что целевая функция представляет собой сумму вкладов от различных переменных. Аналогично левая часть каждого ограничения должна представлять собой сумму расходов, каждое слагаемое которой пропорционально величине соответствующей переменной. Если, например, фирма производит два конкурирующих вида продукции, увеличение сбыта одного из которых отрицательно сказывается на объеме реализации другого, то такая модель не обладает свойством аддитивности.
Упражнение 2.1.1. Выполните применительно к рассматриваемой модели следующие операции.
(а) Запишите в математической форме каждое из сформулированных ниже ограничений.
1) Суточный спрос на краску 1 превышает спрос на краску 2 по крайней мере на 1 т.
[Ответ: х1-х2≥1].
2) Суточный расход исходного продукта А не может превышать 6 т и быть меньше, чем 3 т. [Ответ: ].
3) Спрос на краску 1 никогда не бывает меньше спроса на краску 2.
[Oтвет: х1-х2≥0].
(б) Проверьте, являются ли допустимыми следующие решения.
1) х2=1, х1 =4; 2) х2=2, x1=2; 3) х2= , х1= ; 4) х2=2, х1 =1; 5) х2=2, х1 =-1.
[Ответ: решения 1) и 5) недопустимы, остальные допустимы].
(в) Рассмотрите допустимое решение х2=2, x1=2. Определите указанные ниже величины.
1) Остаток (неиспользованную часть) исходного продукта А. [Ответ: 0].
2) Остаток исходного продукта В. [Ответ: 2].
(г) Определите, какое из допустимых решений п. (б) является наилучшим.
[Ответ: 2) z=10; 3) z=122/3; 4) z=8, т. е. наилучшее решение – третье].
(д) Каковы ваши предположения о количестве допустимых решений рассматриваемой задачи?
[Ответ. Задача имеет бесконечное число допустимых решений, что делает бесполезной попытку найти оптимальное решение методом простого перебора, как это сделано в п. (г), и указывает на необходимость поиска более целенаправленного метода решения. Этот вопрос будет рассмотрен в следующем разделе.]
1.7. Графическое решение задачи линейного программирования
В данном разделе мы рассмотрим один из способов решения задач и фирмы Reddy Mikks. Так как модель содержит только две переменные, задачу можно решить графически. В случае трех переменных графическое решение задач становится менее наглядным, а при большем числе переменных — даже невозможным. Несмотря на это графическое решение позволит сделать некоторые выводы, который послужат основой для разработки общего метода решения ЛП (см. гл. 3).
Первый шаг при использовании графического метода заключается в геометрическом представлении допустимых решений, т. е. построении области (допустимых) решений, в которой одновременно удовлетворяются все ограничения модели. Искомая область (пространство) решений показана на рис. 1.1.
Рис. 1.1.
Условия неотрицательности переменных х2≥0 и х1≥0 ограничивают область их допустимых значений первым квадрантом (представляющим собой по определению часть плоскости, расположенную над осью х2 и правее оси х1). Другие границы пространства решений изображены на плоскости х2, х1 прямыми линиями, построенными по уравнениям которые получаются при замене знака ≤ на знак = в остальные ограничениях. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных. Полученное таким образом пространство решений — многоугольник ABCDEF показан на рис. 1.1.
В каждой точке, принадлежащей внутренней области или границам многоугольника решений ABCDEF, все ограничения выполняются, поэтому решения, соответствующие этим точкам, являются допустимыми. Пространство решений содержит бесконечное число таких точек, но, несмотря на это, можно найти оптимальное решение, если выяснить, в каком направлении возрастает целевая функция модели z=3 х2 - 2∙x1. На рис. 1.2 показано, как осуществляется такая операция. На график наносят ряд параллельных линий, соответствующих уравнению целевой функции при нескольких произвольно выбранных и последовательно возрастающих значениях z, что позволяет определить наклон целевой функции и направление, в котором происходит ее увеличение (т. е. возрастание общего дохода). На рис. 1.2 были использованы следующие значения целевой функции: z =6 и z =9. (Проверьте!)
Чтобы найти оптимальное решение, следует перемещать прямую, характеризующую доход, в направлении возрастания целевой функции до тех пор, пока она не сместится в область недопустимых решений. На рис. 1.2 видно, что оптимальному решению соответствует точка С. Так как точка С является точкой пересечения прямых (1) и (2) (см. рис. 1.1), значения х2 и х1 в этой точке определяются решением следующей системы двух уравнений:
Решение указанной системы уравнений дает следующий результат: х2=31/3, х1 = 11/3. Полученное решение означает, что суточный объем производства краски 2 должен быть равен 31/3 т, а краски 1 - 11/3 т. Доход, получаемый в этом случае, составит тыс. долл.
Рис. 1.2.
Целевая функция: максимизировать z=3 х2 - 2∙x1.
Оптимальное решение: х1 = 11/3 т., х2=31/3 т., тыс. долл.
Упражнение 2.1.2.
(а) Определите пространство решений и найдите оптимальное решение задачи фирмы Reddy Mikks, считая, что каждое из указанных ниже условий заменяет, а не дополняет соответствующие исходные данные, причем все остальные заданные соотношения остаются неизменными. (Для получения решений и проверки ответов воспользуйтесь рис. 1.1.).
1) Максимальный спрос на краску 1 равен 3 т в сутки.
[Ответ. Пространство решений — многоугольник ABCGF, оптимальное решение по-прежнему достигается в точке С].
2) Спрос на краску 1 не менее 2 т в сутки.
[Ответ. Треугольник EDG, оптимум — точка D, где х2=х1=2 и z=10].
3) Спрос на краску 1 ровно на 1 т превышает спрос на краску 2.
[Ответ. Отрезок EF, оптимум — точка Е, где х2=1, x1=2, z=7].
4) Допустимый расход исходного продукта В не меньше 8 т в сутки.
[Ответ. Треугольник BCJ, оптимум — точка J, где х2=6, х1=0 и z= 18].
5) Допустимый суточный расход исходного продукта В не меньше 8 т, а спрос на краску 1 превышает спрос на краску 2 не менее чем на 1 т.
[Ответ. Задача не имеет допустимых решений].
(б) Используя рис. 1.2, найдите оптимальные решения при следующих целевых функциях:
1) z=3x2+х1. [Ответ: х2=4, х1 = 0, оптимум - точка В].
2) z=3x2+1,5х1. [Ответ. Любая точка, принадлежащая отрезку ВС].
3) z z=x2+3х1. [Ответ: x2=2, х1= 2, оптимум - точка D].
4) При условиях п. 2 задача имеет не единственное оптимальное решение. Каково значение целевой функции во всех оптимальных точках?
[Ответ. Значение целевой функции остается неизменным и равным 12. Такие решения называются альтернативными оптимальными решениями, так как всем им соответствует одно и то же значение целевой функции].
Результаты, которые получены при выполнении упражнения 2.1.2(6), обнаруживают интересную закономерность: оптимальному решению всегда может быть поставлена в соответствие одна из допустимых угловых (или экстремальных) точек пространства решений (на рис. 1.2 это точки А, В, С, D, Е и F). Какая из этих точек окажется оптимальной, зависит от наклона прямой, представляющей целевую функцию (т. е. от коэффициентов целевой функции). Заметим, что даже для условий п. 2, при которых оптимальное решение достигается не в одной точке, все альтернативные оптимальные решения находятся после того, как определены угловые точки В и С.