[ ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10
Учебный центр «Резольвента»
Доктор физико-математических наук, профессор
К. Л. САМАРОВ
МАТЕМАТИКА
Учебно-методическое пособие по разделу
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
© К. Л. Самаров, 2009 © ООО «Резольвента», 2009 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10
СОДЕРЖАНИЕ
ПОСТАНОВКА ОСНОВНОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ОЗЛП) С n ПЕРЕМЕННЫМИ.….………………………….. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ОЗЛП С ДВУМЯ ПЕРЕМЕННЫМИ.………………………………………………………………………. СИМПЛЕКС-МЕТОД РЕШЕНИЯ ОЗЛП...……………………………… 3.3.1. Введение дополнительных переменных в систему ограничений…. 3.2. Преобразование системы уравнений методом полных жордановых исключений..…………………………………………………………… 3.3. Понятие опорного плана...…………………………………………… 3.4. Расчетный алгоритм симплекс-метода……………………………… 3.4.1. Первый этап алгоритма. Формирование симплекс-таблицы.. 3.4.2. Второй этап алгоритма. Анализ решения по целевой (фиктивной целевой) строке симплекс-таблицы…………….. 3.4.3. Третий этап алгоритма. Улучшение решения по целевой (фиктивной целевой) строке симплекс-таблицы……………. 3.4.4. Четвертый этап алгоритма. Запись оптимального плана...…. 3.5. Пример решения типовой задачи с помощью симплекс-метода..… ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ..………………………………………… ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ..………………………… ЛИТЕРАТУРА...………………………………………………………………… ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-
1. ПОСТАНОВКА ОСНОВНОЙ ЗАДАЧИ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ С n ПЕРЕМЕННЫМИ
В линейном программировании изучаются свойства решений линейных систем уравнений и неравенств с n переменными следующего вида:n aij x j bi (i = 1, k ), j = n aij x j = bi (i = k + 1, m), (1.1) j = x 0 ( j = 1, n ).
j • В системах (1.1) коэффициенты aij и правые части bi являются числами.
• Системы (1.1) называются системами ограничений.
• Точка в n мерном пространстве x = ( x1, x2,..., xn ), (1.2) удовлетворяющая системе (1.1), называется допустимым планом.
• Основной задачей линейного программирования (ОЗЛП) с n переменными называется задача о нахождении такого допустимого плана, который доставляет максимум функции n Z = c0 + ci xi. (1.3) i = • Функция Z, определенная соотношением (1.3), называется функцией прибыли (целевой функцией).
• Допустимый план, доставляющий максимум функции (1.3), называется оптимальным планом.
Иногда в задачах линейного программирования вместо нахождения максимума функции прибыли Z требуется найти минимум функции затрат ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28- n R = c0 + ci xi.
В этом случае с помощью введения функции Z = R задача о нахождении минимума функции затрат R сводится к задаче о нахождении максимума функции прибыли Z.
2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ОЗЛП
С ДВУМЯ ПЕРЕМЕННЫМИ
Изложим графический метод решения ОЗЛП с двумя переменными на примере задачи оптимального планирования производства продукции.Задача 2.1. Для производства компьютерных столов I-го и II-го видов требуются три типа ресурсов: дерево, пластик и трудозатраты. Потребности в ресурсах для производства одного стола каждого вида, запасы ресурсов, а также прибыль от реализации одного стола каждого вида, заданы в следующей таблице 2.1.:
Трудозатраты (чел/час) Требуется, решив задачу графическим методом, найти план выпуска продукции, позволяющий получить наибольшую прибыль.
Решение. Если обозначить символом х1 выпуск (число единиц) продукции I-го вида, а символом х2 выпуск (число единиц) продукции II-го вида, то, в соответствии с таблицей 2.1., неизвестные х1 и х2 будут удовлетворять следующей системе ограничений:
ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28- По условию задачи необходимо найти оптимальный план производства продукции, т.е. такой план (х1, х2), который доставляет максимум функции прибыли Для того чтобы решить поставленную задачу графическим методом, изобразим на координатной плоскости x1Ox2 область, заданную системой ограничений (2.1):
ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28- Эта область лежит в первом квадранте координатной плоскости, а её граница задается системой уравнений в которой каждое уравнение является уравнением прямой линии.
Прямая l1, заданная уравнением {х1 + 3х2 = 24}, проходит через точки (24;0) и (0;8); прямая l2, заданная уравнением {4х1 + х2 = 24}, проходит через точки (6; 0) и (0; 24); прямая l3, заданная уравнением {3х1 + 2х2 = 23}, проходит через точки ; 0 и 0; (см. рис.).
Таким образом, область, заданная системой (2.1), является пятиугольником OABCD.
Рассмотрим теперь вектор N = (2; 3) с началом в точке О(0;0), параллельный вектору (200; 300), и построим линию нулевого уровня прибыли Z = 0, т.е. прямую Эта прямая проходит через точку О(0;0) и перпендикулярна вектору N. Заметив, что каждая из линий уровня Z = const является прямой, параллельной линии нулевого уровня Z = 0, будем передвигать линию нулевого уровня Z = 0 параллельно самой себе в направлении вектора N (2; 3) до тех пор, пока она пересекается с точками пятиугольника OABCD. Очевидно, что последними точками, в которых передвигаемая линия пересекается с пятиугольником OABCD, могут быть только вершины пятиугольника.
Найдем координаты вершин пятиугольника.
Координаты точки В удовлетворяют системе уравнений ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28- Решая эту систему, находим, что B = (5;4). Координаты точки C удовлетворяют системе уравнений Решая эту систему уравнений, находим, что C = (3;7). Координаты остальных вершин пятиугольника нам уже известны: A = (6;0), D = (0;8), O = (0;0).
Подсчитаем теперь значения, которые принимает функция прибыли в вершинах пятиугольника:
Таким образом, наибольшая прибыль достигается в точке C(3; 7), и оптимальный план имеет вид (х1, х2) = (3; 7).
Ответ. Наибольшая прибыль 2700 рублей достигается при выпуске 3-х компьютерных столов I-го вида и 7 компьютерных столов II-го вида.
Замечание. Приведенный графический метод решения ОЗЛП с двумя переменными и графический метод решения матричных игр типа 2 n и m 2, изложенный в Модуле 9, являются аналогами.
3. СИМПЛЕКС-МЕТОД РЕШЕНИЯ ОЗЛП
3.1. Введение дополнительных переменных в систему ограничений В предыдущем параграфе для решения ОЗЛП с двумя переменными был применен графический метод. В общем случае ОЗЛП решается с помощью симплекс-метода, к изложению которого мы сейчас и переходим.Рассмотрим ОЗЛП с системой ограничений в следующей форме:
ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10
Если ввести в систему ограничений (3.1) дополнительные переменные по формулам
то система ограничений (3.1) преобразуется в систему уравнений
имеющую специальный вид. В этой системе каждая из переменных xn+1, xn+2,..., xn+m исключена из всех уравнений, за исключением одного уравнения, в котором коэффициент при ней равен 1.
3.2. Преобразование системы уравнений методом Заметив, что мы ввели дополнительные переменные в систему ограничений (1.1) таким образом, что при любом допустимом плане они оказались неотрицательными числами, перейдем к преобразованию системы уравнений (3.3) с помощью метода, который носит название метода полных жордановых исключений.
Для системы уравнений (3.3) назовем переменные x1, x2,..., xn свободными, а переменные xn+1, xn+2,..., xn+m базисными.
ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28- Разделение переменных на свободные и базисные является условным, поскольку систему уравнений можно переписать в другом (эквивалентном) виде, где наборы свободных и базисных переменных будут иными. В частности, можно поменять ролями какую - нибудь свободную переменную xr с некоторой базисной переменной. С этой целью совершим следующие операции:
Рассмотрим какое-нибудь уравнение системы (3.3), в котором коэффициент asr при переменной xr отличен от 0 (это уравнение с номером s ).
Разделим это уравнение на asr. Тогда в нем коэффициент при переменной xr станет равным 1.
Вычтем из каждого i - го уравнения системы (i s ) уравнение с номером s, умноженное на asr.
В результате переменная xr будет исключена из всех уравнений системы, кроме уравнения с номером s, и станет базисной, а переменная xn+ s станет свободной.
• Описанный процесс носит название полного жорданова исключения с разрешающим элементом asr. Коэффициенты s - го уравнения системы (3.3) называются разрешающей строкой, а элементы r - го столбца матрицы системы уравнений (3.3) разрешающим столбцом.
Удобный алгоритм пересчета коэффициентов системы уравнений при проведении полного жорданова исключения с разрешающим элементом asr состоит в следующем (здесь и далее верхний индекс «н» соответствует новому значению элемента матрицы, а верхний индекс «с» старому значению):
Разделим элементы разрешающей строки на разрешающий элемент.
При этом разрешающий элемент станет равным 1;
Все элементы разрешающего столбца, за исключением разрешающего элемента, заменим нулями. При этом разрешающий элемент останется равным 1.
Все остальные элементы матрицы пересчитаем в новые элементы ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28- воспользовавшись «правилом прямоугольника»
В случае, когда в разрешающей строке (разрешающем столбце) есть нули, правило прямоугольника приводит к тому, что элементы столбцов (строк), пересекающих эти нули, остаются без изменения.
• Базисным решением ОЗЛП называется такое решение системы уравнений (3.3), в котором все свободные переменные равны 0.
• Базисное решение ОЗЛП называется опорным решением (опорным планом), если в нем все базисные переменные неотрицательны.
• В теории симплекс-метода доказывается, что, если максимум целевой функции при данной в ОЗЛП системе ограничений существует, то он достигается на опорном решении.
• Опорное решение, на котором целевая функция достигает максимума, является оптимальным планом.
Замечание. Не следует думать, что ОЗЛП всегда имеет решение. Система ограничений, например, может быть противоречивой и задавать пустое множество решений. Система ограничений может также задавать неограниченное множество, на котором функция прибыли является неограниченной.
3.4. Расчетный алгоритм симплекс-метода Алгоритм симплекс-метода состоит из нескольких этапов: сначала происходит построение одного из опорных решений, а затем «улучшение» этого решения, т.е. переход к другим опорным решениям, на которых значение целевой функции не уменьшается. Для проведения расчетов используются ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28- симплекс-таблицы, составленные по коэффициентам системы (3.3), а процесс поиска и улучшения опорного решения заключается в пересчете элементов этих таблиц методом полных жордановых исключений.
3.4.1. Первый этап алгоритма. Формирование симплекс-таблицы Составим первую симплекс-таблицу (Таблица 3.4.1) по системе (3.3) и целевой функции (1.3).
L L L L L L L L L L
Для каждого уравнения системы (3.3) в первом столбце таблицы указывается соответствующая базисная переменная. Строка z называется целевой строкой. Строка добавляется в таблицу лишь в случае поиска опорного решения и называется фиктивной целевой строкой. Последний столбец таблицы (столбец ) организован для контроля правильности вычислений, и в каждой его клетке будем записывать суммы чисел, стоящих в строке.Таблице соответствует базисное решение системы (3.3) вида Возможны два случая:
Все числа b1, b2,..., bm неотрицательны, т.е. решение (3.4.1.1) являетa) ся опорным. В этом случае строку в таблице не заводим и сразу переходим ко 2-му этапу.
Среди чисел b1, b2,..., bm существуют отрицательные, т.е. решение (3.4.1.1) не является опорным. Тогда для построения опорного решения запишем в строку сумму тех строк таблицы, где стоят отрицательные значеООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28- ния bi, а затем перейдем к анализу и улучшению решения (3.4.1.1) по фиктивной целевой строке.
3.4.2. Второй этап алгоритма. Анализ решения по целевой (фиктивной целевой) строке симплекс-таблицы Рассмотрим элементы целевой (фиктивной целевой) строки, стоящие в столбцах x1, …, xn+m. Если среди них имеется хотя бы один отрицательный элемент, то решение надо улучшать по правилам этапа 3.
Если же все указанные элементы неотрицательны, то в случае, когда анализируется опорное решение по целевой строке z, это означает, что на этом решении функция z достигает максимума и нужно переходить к выписыванию соответствующего оптимального плана (этап 4).
В случае поиска опорного решения (анализ по фиктивной целевой строке ) вся строка должна состоять из нулей, иначе система ограничений противоречива, и ОЗЛП не имеет решения. Получение же нулевой строки свидетельствует о том, что опорное решение построено. В этом случае фиктивная целевая строка удаляется из таблицы, а решение анализируется по целевой строке z.
3.4.3. Третий этап алгоритма. Улучшение решения по целевой (фиктивной целевой) строке симплекс-таблицы Найдем среди элементов z1, z2,..., zn целевой строки z (или среди элементов 1, 2,..., n в случае фиктивной целевой строки ) наибольший по абсолютной величине отрицательный элемент. Пусть это будет элемент zr (или r ), тогда столбец xr объявим разрешающим.
цательную дробь (пусть это будет дробь bs a ), и объявим строку xn+ s разsr решающей. Если же все дроби вида air окажутся отрицательными, то это ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28- означает, что при заданной системе ограничений функция z неограничена, т.е. поставленная ОЗЛП решений не имеет.
Элемент asr, стоящий на пересечении разрешающей строки и разрешающего столбца, объявим разрешающим, и, для наглядности, его можно обвести в таблице прямоугольником.
Замечание. Иногда существует несколько возможностей выбора разрешающего элемента. В этом случае для поиска опорного решения разрешающий элемент выбирают отрицательным.
Заготовим новую симплекс-таблицу, заменив в первом столбце переменную xn+ s на переменную xr.
Пересчитаем все элементы старой симплекс-таблицы, включая строки z и, а также столбец, по правилам метода полных жордановых исключений с разрешающим элементом asr. Результат запишем в новую симплекс-таблицу.
Контроль правильности вычислений осуществляем при помощи сравнений сумм элементов каждой строки с числами, записанными в последнем столбце. Расхождение результатов свидетельствует об арифметической ошибке, и соответствующую строку надо пересчитать.
После этого возвращаемся к этапу 2.
3.4.4. Четвертый этап алгоритма. Запись оптимального плана В плане указываем значения только исходных переменных x1, x2,..., xn, причем значения тех из них, которые являются свободными, полагаем равными нулю, а значения остальных переменных берем из второго столбца таблицы (столбца свободных членов). Из этого же столбца выписываем максимальное значение z.
3.5. Пример решения типовой задачи с помощью симплекс-метода Задача 3.5.1. Составляется комбинированный корм из трех злаков: кукурузы, овса и ржи. Калорийность и содержание витамина С в одном кг кажООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28- дого злака, а также цена одного кг каждого злака указаны в следующей таблице 1:
Требуется составить наиболее дешевый комбинированный корм, 1кг которого содержал бы не менее 125 ккал и не менее 2 г витамина С.
Решение. Обозначим содержание кукурузы, овса и ржи в 1кг комбикорма символами х1, х2 и х3 (кг), соответственно. По условию задачи эти переменные удовлетворяют следующей системе ограничений:
Требуется найти план, доставляющий минимум функции затрат Решим поставленную задачу с помощью симплекс-метода. Для этого перепишем систему ограничений (3.5.1) в следующем виде:
Введя дополнительные переменные x4 и x5, преобразуем систему (3.5.3) в систему уравнений ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28- Приведем систему (3.5.4) к специальному виду, исключив переменную x3 из второго и третьего уравнений:
Будем искать решение, доставляющее максимум функции прибыли Составим первую симплекс-таблицу (Таблица 2).
Поскольку базисное решение не является опорным ( x4 < 0 ), то для поиска опорного решения в симплекстаблицу добавляется фиктивная целевая строка, в которую записывается строка x4.
В столбец запишем суммы чисел, стоящие по строкам таблицы.
В строке среди чисел {4, 3, 0, 1, 0} наибольшим по абсолютной величине отрицательным числом является число {4}, поэтому разрешающим столбцом объявляем столбец x1. Для элементов таблицы, расположенных в строках x3, x4 и x5, рассмотрим дроби ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28- числители которых являются элементами второго столбца таблицы, а знаменатели элементами разрешающего столбца. Наименьшей неотрицательной дробью является дробь 0,25, поэтому строка x4 объявляется разрешающей строкой. Таким образом, элемент таблицы, стоящий на пересечении строки x4 и столбца x1 (число 4 ) является разрешающим элементом.
Теперь пересчитаем все элементы Таблицы 2 по правилам метода полных жордановых исключений с разрешающим элементом 4. Получим следующую Таблицу 3:
Так как строка стала нулевой, то опорное решение получено. Исключим строку из таблицы и проведем анализ по целевой строке z.
Среди чисел {0; 0,75 ; 0; 1,25; 0} наибольшим по абсолютной величине отрицательным числом является число { 0,75 }, поэтому разрешающим столбцом объявляем столбец x2. Для элементов таблицы, расположенных в строках x3, x1 и x5, рассмотрим дроби числители которых являются элементами второго столбца таблицы, а знаменатели элементами разрешающего столбца. Наименьшей неотрицательной дробью является дробь, поэтому строка x1 объявляется разрешающей строкой.
Таким образом, элемент таблицы, стоящий на пересечении строки x1 и столбца x2 (число 0,75 ) является разрешающим элементом.
ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28- Теперь пересчитаем все элементы Таблицы 3 в новую симплекс-таблицу по правилам метода полных жордановых исключений с разрешающим элементом 0,75. Получим следующую Таблицу 4:
В строке z среди чисел {1; 0; 0; 1; 0} нет отрицательных. Значит, максимум z достигнут, и можно выписать оптимальный план:
Максимальное значение целевой функции z равно 2, а минимальное значение функции затрат R равно 2.
изо ржи.
ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-
ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ
Что называется общей задачей линейного программирования (ОЗЛП)?Что называется целевой функцией прибыли?
Что называется целевой функцией затрат?
Что называется системой ограничений ОЗЛП?
Какие ОЗЛП можно решать графическим методом?
В чем состоит схема решения задачи линейного программирования графическим методом?
Что называется допустимым планом ОЗЛП?
Что называется оптимальным планом ОЗЛП?
В чем состоит схема введения дополнительных переменных в систему ограничений ОЗЛП?
10. Какие переменные в системе уравнений называются свободными?
11. Какие переменные в системе уравнений называются базисными?
12. Что называется разрешающим столбцом матрицы системы уравнений?
13. Что называется разрешающей строкой матрицы системы уравнений?
14. Что называется разрешающим элементом матрицы системы уравнений?
15. В чем состоит схема преобразования системы уравнений методом полных жордановых исключений?
16. Что называется базисным решением ОЗЛП?
17. Что называется опорным решением ОЗЛП?
18. Из каких этапов состоит симплекс-метод решения ОЗЛП?
19. Как формируется первая симплекс-таблица?
ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
Мини-пекарня планирует выпечку батонов и булочек. На производство одного батона расходуется 450 г муки, 10 г масла и 0,5 яйца, а на производство одной булочки 150 г муки, 5 г масла и 1 яйцо. В пекарню ежедневно завозят 180 кг муки, 5 кг масла и 775 яиц. Прибыль от реализации батона равна 3 рублям, а от реализации булочки 5 рублям. В день необходимо производить не менее 780 единиц продукции и получать не менее 3500 рублей прибыли.1. Составить систему ограничений задачи;
2. Составить целевую функцию ежедневной прибыли;
3. Составить первую симплекс-таблицу;
4. С помощью симплекс-метода найти оптимальный план производства продукции, обеспечивающий максимальную ежедневную прибыль;
5. С помощью симплекс-метода найти максимальную ежедневную прибыль;
6. Найти оптимальный план производства продукции и максимальную ежедневную прибыль с помощью графического метода.
ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10 ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-
ЛИТЕРАТУРА
Основная:1. Вентцель Е.С. Исследование операций: Задачи, принципы, методология.
Учебное пособие. – М.: Дрофа, 2004.
2. Колемаев В.А. Математическая экономика. Учебник для вузов. - М.:
ЮНИТИ-ДАНА, 2005.
3. Кремер Н.Ш. Исследование операций в экономике. – М.: ЮНИТИ, 2006.
4. Орехов Н.А., Левин А.Г., Горбунов Е.А. Математические методы и модели в экономике. Учебное пособие для вузов / Под ред. проф. Н.А. Орехова – М.: ЮНИТИ-ДАНА, 2004.
Дополнительная:
5. Экономико-математическое моделирование. Учебник для вузов / Под общ. ред. И.Н. Дрогобыцкого. – М.: Изд. «Экзамен», 2004.
6. Лунгу К.Н. Линейное программирование. Руководство к решению задач. – М.: Физматлит, 2005.
7. Малыхин В.И. Математика в экономике: Учебное пособие. – М.: ИНФРА-М, 2002.
8. Самаров К.Л., Шапкин А.С. Задачи с решениями по высшей математике и математическим методам в экономике: Учебное пособие – М.: Издательско-торговая корпорация «Дашков и Ко», 2007.
9. Таха Х.А. Введение в исследование операций. – М.: ВИЛЬЯМС, 2007.
ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10
«