Линейное программирование

13.09.2015 Линейное программирование Основатели советской школы ЭММ НЕМЧИНОВ Василий Сергеевич НОВОЖИЛОВ Виктор Валентинович КАНТОРОВИЧ Леонид Витальевич 2 1 13.09.2015 Основные даты • 1938 г. Леонид Витальевич КАНТОРОВИЧ в порядке научной консультации приступил к изучению задачи фанерного треста. В 1939 году КАНТОРОВИЧ публикует работу «Математические методы организации и планирования производства». • 1942 г. Тьяллинг КУПМАНС в работе «Соотношение между грузами на различных маршрутах» («Exchange Rations Between Cargoes Various Routes») предложил оригинальную аналитическую методику «анализ деятельности» («activity analysis»). • 1947 г., американский математик Джордж ДАНЦИГ разработал симплекс-метод — эффективный метод решения задач линейного программирования. • 1975 г., Канторович и Купманс становятся лауреатами Нобелевской премии по экономике «за вклад в теорию оптимального распределения ресурсов». 3 Американские исследователи Тьяллинг Чарльз КУПМАНC Джордж Бернард ДАНЦИГ 4 2 13.09.2015 Создатели линейного программирования 5 Общая и каноническая форма ЗЛП Требуется найти максимум (или минимум) линейной функции при ограничениях Общая форма Каноническая форма 6 3 13.09.2015 Условия применения методов ЛП 1. Допустимость математической формулировки всех условий экономической проблемы в виде линейных соотношенийуравнений или неравенств. 2. Совместность линейных соотношений. 3. Совместная система должна быть неопределенной. 4. Задача должна иметь один критерий оптимальности. При этом целевая функция должна представляться в виде линейной формы. 7 Типы уравнений-ограничений Тип 1 (ограничение сверху), – ограничение по ресурсам: хi – объем производства какого-то товара i (i = 1, 2, ..., n). Аk – количество ресурса типа k (k = 1, 2, …, m); аi – норма расхода этого ресурса при производстве товара i. а1х1 + а2х2 + … + аnхn ≤ Аk, Тип 2 (ограничение снизу), – задание (план) по производству: а1х1 + а2х2 + … + аnхn ≥ Аk. Если а1 = а2 = … = аn = 1, то Аk – план производства продукции k (k = 1, 2, …, m), а х1, х2, ..., xn – варианты технологий. Тип 3 (равенство). а1х1 + а2х2 + … + аnхn = Аk, Если аi = 1, то условие характеризует какое-то отношение в материальном потоке. Если а1 = а2 = … = аn = 1, то условием может быть строго заданный план производства. 8 4 13.09.2015 Графическое отображение условий-ограничений а1х1 + а2х2 ≤ Ak (ограничение Тип 1) а1х1 + а2х2 ≥ Аk (ограничение Тип 2) а1х1 + а2х2 = Аk (ограничение Тип 3) 9 ПРИМЕР 1 На заводе имеется подсобное производство, которое использует отходы, из которых могут выпускаться два вида изделий. Выпуск этих изделий ограничен двумя ресурсами. Нормы расхода ресурсов, их объем, а также прибыль на единицу продукции показано в таблице. Требуется определить план выпуска изделий, который обеспечит максимальную прибыль. 10 5 13.09.2015 Решение Традиционный метод. Находим «узкое место» по ресурсам: 520 / 9,2 = 56 («узкое место») 24 / 0,3 = 80 3 × 56 = 168 руб. Математическая модель производства. Пусть х1 – план выпуска продукции первого вида, х2 – второго вида. 9,2 х1 + 4 х2 ≤ 520 (1) 0,3 х1 + 0,6 х2 ≤ 24 (2) х1 ≥ 0, х2 ≥ 0 (3), (4) 3х1 + 2х2 → Сmax – функция цели 11 Граф-аналитический метод (ОДЗ) 9,2х1 + 4,0х2 = 520 (прямая AB) при х1 =0; х2 =520 / 4,0 = 130 (т. А) при х2 =0; х1 =520 / 9,2 = 56,2 (т. В) 0,3х1 + 0,6х2 = 24 (прямая CD) при х1 =0; х2 =24 / 0,6 = 40 (т. D) при х2 =0; х1 =24 / 0,3 = 80 (т. С) 12 6 13.09.2015 Граф-аналитический метод (функция цели) Cmax = 210 3х1 + 2х2 = 210 (прямая МN) при х1 = 0; х2 = 105 (т. М) при х2 = 0; х1 = 70 (т. N) 9,2х1 + 4,0х2 = 520 0,3х1 + 0,6х2 = 24 х1 = 50; х2 = 15 (т. R) Cmax = 3·50 + 2·15 = 180 руб. 13 Случай множества оптимальных планов 14 7 13.09.2015 Симплексный М-метод Джордж ДАНЦИГ 1936 г. – степень бакалавра в области математики и физики, Мэрилендский университет 1938 г. – степень магистра математики, Мичиганский университет 1940 г. – докторская программа в области математики, Калифорнийский университет в Беркли 1941 г. – отпуск от докторской программы, работа в статистическом управлении ВВС США 1946 г. – степень доктора философии (PhD) по математике, Калифорнийский университет в Беркли 1947 г. – разработка симплекс метода 1952 г. – математическое подразделение корпорации RAND Позднее преподавал в Калифорнийском и Стэнфордском университетах. 16 8 13.09.2015 Симплексный M-метод. Основные этапы решения. 1. Система уравнений-ограничений приводится к канонической форме. 2. Составляется первый опорный допустимый (базисный) план. 3. План оценивается с точки зрения достижения оптимума (максимум или минимум целевой функции). 4. Если план не является оптимальным, то он пересчитывается таким образом, что функция цели при решении задачи на максимум увеличивается, а при решении задачи на минимум уменьшается. 5. Полученный новый, пересчитанный, план снова оценивается на оптимум. Если, оптимум не достигнут, то делается новый пересчет. 6. Пересчеты по циклической программе осуществляются до тех пор, пока не будет получен оптимальный план. 17 Случай несовместности ограничений 4 9 13.09.2015 Графическое толкование симплексного метода 19 Приведение различных ограничений к канонической форме Тип 1: а1х1 + а2х2 + … + аnхn ≤ Аk, а1х1 + а2х2 + … + аnхn + хдn+1 = Аk, хдn+1 – дополнительная переменная. Экономический смысл: неиспользованная часть ресурса (если производство не началось, то х1 = х2 = … = хn = 0 и хдn+1 = Аk). Тип 2: а1х1 + а2х2 + … + аnхn ≥ Аk, а1х1 + а2х2 + … + аnхn – хдn+1 + у = Аk, хдn+1 – дополнительная переменная, у – искусственная переменная. Экономический смысл: если условие – план производства, то при а1 = а2 = ... = аn = 1 имеем: х1 + х2 + … + хn – хдn+1 + у = Аk. 20 10 13.09.2015 Приведение различных ограничений к канонической форме Тип 3: а1х1 + а2х2 + … + аnхn = Аk, а1х1 + а2х2 + … + аnхn + у = Аk, где у – искусственная переменная. Дополнительная переменная, как правило, в функцию цели не вводится, а искусственная переменная вводится в функцию цели с коэффициентом M, где М – очень большое число: с1х1 + с2х2 + … + сnхn ± Му → opt 21 Пример 2 Определить оптимальную совокупность технологических схем и объемы производства по ним изделий двух типов, обеспечивающую максимум прибыли, если известно что: a) производство изделий типа 1 должно быть не менее 1000 т; b) производство изделий типа 2 должно быть равным 2 000 т c) производство продукции типа 1 возможно по двум технологическим схемам (1 и 2), а производство продукции типа 2 также по двум другим схемам (3 и 4). d) в технологической цепочке каждой из схем занято два типа оборудования, фонд рабочего времени первого типа – 7 000 станко-часов в год, а второго типа – 6 000 станко-часов в год. e) нормы расхода станко-часов на 1 т готовых изделий на различных типах оборудования и по различным технологическим схемам, а также прибыль на 1 т изделий представлены в таблице. 22 11 13.09.2015 23 Математическая модель задачи х1, х2, х3, х4 – интенсивности использования технологических схем Уравнения-ограничения по плану производства: х1 + х2 ≥ 1000 (1) х3 + х4 = 2000 (2) Уравнения-ограничения по фонду времени: 2х1 + 5х2 + 3х3 + 2х4 ≤ 7000 (3) 1,5х1 + 1х2 + 1х3 + 2х4 ≤ 6000 (4) Условия неотрицательности: х1 ≥ 0; х2 ≥ 0; х3 ≥ 0; х4 ≥ 0. Функция цели: 260х1 + 200х2 + 180х3 + 120х4 → max. 24 12 13.09.2015 Приведение к каноническому виду х1 + х2 – х5д + у1 = 1000 (1а) х3 + х4 + у2 = 2000 (2а) 2х1 + 5х2 + 3х3 + 2х4 + х6д = 7000 (3а) 1,5х1 + 1х2 + 1х3 + 2х4 + х7д = 6000 (4а) Функция цели: 260х1 + 200х2 + 180х3 + 120х4 + 0х5д + 0х6д + 0х7д – Му1 – Му2 = Сmax. 25 Исходная матрица задачи в общем виде Примечание: k – кол-во ограничений «тип I», l – кол-во ограничений «тип II», m – кол-во ограничений «тип III», N – общее кол-во ограничений (N = k + l + m). 26 13 13.09.2015 Исходная матрица задачи 27 28 14 13.09.2015 Симплексная таблица 1 29 Правила заполнения симплексной таблицы 1 1. В число базисных переменных должны войти дополнительные переменные, которые имеют коэффициент «+1» или искусственные переменные. Остальные переменные переписываются из исходной матрицы. 2. Оценки базисных переменных переписываются из строки функции цели исходной матрицы Сmax. 3. Все остальные коэффициенты (за исключением последней строки) переписываются из исходной матрицы без пересчета. 4. В строке оценок записывается разность zj – cj, где zj – сумма построчных произведений коэффициентов столбца j-ой переменной на оценки соответствующих переменных, находящихся в числе базисных (по этой строке), cj – оценка j-ой переменной из исходной матрицы. 30 15 13.09.2015 Расчет для нашего примера Столбец свободных членов: z0 = (–М) • 1000 + (–М) • 2000 + 0 • 7000 + 0 • 6000 = –3000 М Столбец по х1: zj = (–М) • 1 + (–М) • 0 + 0 • 2 + 0 • 1,5 = –М cj = 260; zj – cj = –М – 260 и т.д. для всех других столбцов 31 Правило оценки плана на оптимальность В оптимальном плане при решении задачи на максимум все оценки в строке zj – cj должны быть положительными. При решении на минимум – отрицательными. 32 16 13.09.2015 Правила пересчета симплексной таблицы 1. Находим ключевой (ведущий, главный) столбец и ключевую строку. При решении задачи на максимум ключевым будет столбец, имеющий минимальную оценку. При решении задачи на минимум – столбец с максимальной оценкой. В нашем примере нужно отыскать столбец с минимальной оценкой: (–М – 260) < (–М – 200) < … < М Ключевую строку находим по «узкому месту». Делим значения столбца свободных членов на положительные коэффициенты главного столбца соответствующей строки. Строка, в которой лежит наименьшее частное от деления будет являться ключевой. 33 Симплексная таблица 1 (главный столбец и главная строка) 34 17 13.09.2015 Правила пересчета коэффициентов 2. В новой симплексной таблице базисная переменная по главной строке и небазисная переменная по главному столбцу меняются местами. Все остальные переменные остаются на своих прежних местах. 3. Оценки базисных переменных записываются из исходной матрицы задачи. 35 Правила пересчета коэффициентов 4. Коэффициент, стоящий в новой таблице на месте главного элемента в исходной таблице, рассчитываются по формуле: Кrhнов = 1 / ГЭ; Кrhнов = 1 / 1 = 1. 5. Все коэффициенты, стоящие в исходной таблице в главной строке r, рассчитываются для тех же мест в новой таблице по формуле: Кrjнов = Кrjисх / ГЭ Пример: по столбцу свободных членов: 1000 / 1 = 1000 по столбцу х2: 1 / 1 = 1 по столбцу х3: 0 / 1 = 0 и т.д. 36 18 13.09.2015 Правила пересчета коэффициентов 6. Коэффициенты, стоящие по главному столбцу рассчитываются для тех же мест в новой таблице по формуле: Кihнов = Кihисх / ГЭ · (–1) Пример: по строке у2: 0 / 1 · (–1) = 0 по строке х6д: 2 / 1 · (–1) = –2 по строке х7д: 1,5 / 1 · (–1) = –1,5 по строке zj – cj: (–М – 260) / 1 · (–1) = М + 260 37 Правила пересчета коэффициентов 7. Все остальные коэффициенты, включая столбец свободных членов для новой симплексной таблицы, рассчитываются по формуле: Кijнов = (Кijисх · ГЭ – Кrjисх · Кihисх) / ГЭ Коэффициент столбца свободных членов по строке у2: (2000 · 1 – 1000 · 0) / 1 = 2000 Коэффициент столбца свободных членов по строке zj – cj: (–3000М – 1000·(–М – 260)) / 1 = = (–3000М + 1000М + 260 · 103) / 1 = = –2000М + 260·103 38 19 13.09.2015 Симплексная таблица 2 39 Симплексная таблица 2 (главный столбец и главная строка) 40 20 13.09.2015 Практические советы • «Правило диагоналей»: новое значение коэффициента равно разности произведений коэффициентов на концах диагоналей, деленной на значение ГЭ. • Все коэффициенты столбцов исходной таблицы, которые на пересечении с главной строкой имеют «нуль» (в нашем случае это столбцы по х3 и х4), а также все коэффициенты строк, которые на пересечении с главным столбцом также имеют «нуль» (в нашем примере это строка по у2), переписываются в новую симплексную таблицу без пересчета. 41 Дальнейшие расчеты 1. Убеждаемся, что план, записанный в симплексной таблице 2, не является оптимальным (для столбцов х3, х4, х5 коэффициенты по строке оценок zj – cj отрицательны). 2. Находим главный столбец (из столбцов с отрицательными оценками по строке zj – cj выбираем столбец с наименьшей оценкой). 3. Находим ключевую строку (коэффициенты, стоящие в столбце свободных членов, делим на соответствующие коэффициенты главного столбца). 4. Делаем заготовку новой симплексной таблицы 3 (меняем местами х3 и х6д; оценки базисных переменных берем из исходной матрицы задачи). 5. Рассчитываем новые коэффициенты по рассмотренным ранее правилам. 42 21 13.09.2015 «Заготовка» симплексной таблицы 3 43 Практические советы • Столбцы с искусственными переменными можно из дальнейших расчетов исключить. • Значение функции цели от таблицы к таблице увеличивается при решении задачи на максимум и уменьшается при решении задачи на минимум. • Коэффициенты, стоящие в столбце свободных членов всегда должны быть положительными, за исключением zj – cj. • После того, как будут выведены из числа базисных все искусственные переменные, значение функции цели должно стать положительной величиной. 44 22 13.09.2015 Симплексная таблица 5 45 23