ФЕДЕРАЛЬНОЕАГЕНСТВО ПО ОБРАЗОВАНИЮ
ПСКОВСКИЙГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ
Решениезадач линейного программирования в среде Maple
Курсоваяработа
Студента 4 курса
физико-математического
факультета отделение «математика»
Гоняна Аршака Арзумановича
Научный руководитель
Матвеев Владимир Александрович
Псков
2008
Содержание
§1. Библиотека «simplex» пакета Maple
§2. Постановка задача линейного программирования для Nпеременных
§3. Постановка Транспортной задачи (ТЗ) для n переменных
§4. Пример решения задача линейного программирования
§5. Пример решения Транспортнойзадачи
Список литературы
§1.Библиотека «simplex»пакета Maple
Библиотека«simplex» — предназначена для оптимизациилинейных систем с использованием симплексного алгоритма. Особенность ее в том,что имеется возможность выполнять оценки промежуточных этапов симплексногоалгоритма, например, определять базисные переменные и т.п.
Послеподключения библиотеки командой with(simplex) пользователю становится доступныфункции и опции, указанные в следующей таблице.basis Находит базисные переменые cterm Выводит список элементов вектора ресурсов display Представляет систему в матричной форме dual Преобразует данную задачу в двойственную задачу линейного программирования feasible Возвращает true – если решение существует, и false – если нет maximize Находит максимум целевой функции minimize Находит минимум целевой функции NONNEGATIVE Опция: указание на условие не отрицательности всех переменных setup Приводит систему ограничений к стандартной форме standardize Превращает систему ограничений в пары неравенств
§2. Постановка задачалинейного программирования для N переменных
Рассмотримзадачу формирования плана производства: некоторое предприятие может выпускатьопределённый набор продукции. Нормы затрат известны. Требуется построитьпроизводственный план, учитывающий ограниченность ресурсов в котором необходимоопределить нормы выпуска каждого вида продукции, чтобы прибыль от её реализациибыла максимальной.
Построение экономико-математической модели
n — число различных видовпродукции.
m — число различныхресурсов.
aij — объём i-того ресурса, который расходуется на производство одной единици j-тоговида продукции i=1..m, j=1..n.
Xj — объем (количество единиц) j-того вида продукции в производственном планепредприятия (j от 1 до n).
Прибыльобозначим F, тогда F=c1X1+c2X2+...+cnXn->=max
Составимограничения для первого ресурса:
а11 — объем первого ресурса, который расходуется на производство одной единицыпервого вида продукции;
а11Х1 — объём первого ресурса, который требуется на изготовление Х1единиц первого вида продукции;
а12Х2 — объём первого ресурса, который требуется на изготовление Х2единиц второго вида продукции;
а1nХn — объём первого ресурса, который требуется на изготовление Хnединиц n-ого вида продукции;
а11Х1+a12X2+...+a1nXn — объём первого ресурса, которыйтребуется на изготовление продукции, следовательно, мы имеем следующееограничение:
а11Х1+а12+...+а1nXn
Аналогичнодля остальных ресурсов:
а21Х1+а22+...+а2nXn
а31Х1+а32+...+а3nXn
.........................................
аm1Х1+аm2+...+amnXn
Кроме того,количество выпущенной продукции не может быть отрицательной, следовательно, Х1>= 0, X2>=0, ...,Xn>=0.
§3. ПостановкаТранспортной задачи (ТЗ) для nпеременных
Пусть имеется несколькопоставщиков однородной продукции (каждый с определенным запасом) и несколькопотребителей этой продукции (с известными потребностями у каждого). Заданатакже сеть коммуникаций (дорог, рек, воздушных линий и т.д.) связывающаякаждого поставщика с каждым потребителем. На каждой коммуникации задана ценаперевозки – стоимость перевозки единицы продукции. Если какая – либокоммуникация отсутствует, то считаем, что она есть, но цену перевозки на нейустанавливаем равной бесконечности (+∞). Это соглашение сделаетневыгодным перевозку по ней и автоматически исключит данную коммуникацию изплана перевозок.
Таким образом, требуетсясоставить план перевозок продукции от поставщиков к потребителям так, чтобыпотребности потребителей были бы удовлетворены за счет вывоза запаса отпоставщиков. Цель – минимизация суммарной стоимости всех перевозок.
Транспортные задачибывают:
1) открытые m ≠ n(суммарный запас продукции, имеющейся у поставщиков, не совпадает с суммарнойпотребностью в продукции у потребителей.)
2) закрытые m = n (суммарный запас продукции, имеющейся у поставщиков,совпадает с суммарной потребностью в продукции у потребителей.)
Метод потенциалов«работает» только для закрытых ТЗ, причем, закрытая ТЗ всегда разрешима.
Открытую ТЗ сводят кзакрытой ТЗ путем прибавления к суммарному запасу продукции или суммарнойпотребности продукции недостающих единиц до равенства суммарного запасапродукции и суммарной потребности продукции.
Закрытая транспортнаязадача формулируется как Задача Линейного Программирования (ЗЛП) следующеговида:
/>
/>
/>, где
/> — запас i – го поставщика
/> — потребность j – го потребителя
/> — цена перевозки единицы продукции покоммуникациям (i,j)
(от i – го поставщика к j – му потребителю)
/> — объем перевозки продукции(неизвестный) по коммуникациям (i,j).
Для вывода критерииоптимальности транспортной задачи построим двойственную задачу.
Структура матрицыограничений транспортной задачи такова, что столбец, соответствующей переменной/>содержит ровно два ненулевыхэлемента: единицу в строке с номером i и единицу в строке m + i.
Вектор двойственныхпеременных Y = (/>,…,/>,/>,…,/>) имеет m + n компонент (по числе ограничений ТЗ),которые называются потенциалами: переменные />,/>,…,/> — потенциалы поставщиков; переменные />,/>…,/> — потенциалы потребителей.
Используя схему дляпостроения двойственной задачи к ЗЛП в стандартной форме, имеем: />
/>
В полученной двойственнойзадаче n·m ограничений, соответствующих каждой переменной />ТЗ. Вспоминая, что невязка между левой и правой частьюв ограничений двойственной задачи есть оценка для соответствующей переменнойисходной задачи, запишем условия оптимальности текущего плана перевозок в ТЗ:
/>.
Неизвестные потенциалы />и />(их общее количество равно m + n)могут быть найдены (и именно так отыскиваются) из условия равенства нулю оценокдля базисных переменных (заполненных клеток таблицы) ТЗ (таких равенств (m+n — 1), что следует из замечания ниже).
/> ,
для заполненных клеток (i,j) таблицы ТЗ.
Решение полученнойсистемы (содержащей неизвестных на единицу больше, чем число уравнений) ищется,когда одно из неизвестных (вообще говоря, любое) полагается равным некоторомучислу (тоже, вообще говоря, любому). После этого оставшаяся система имеетединственное решение.
§4. Пример решениязадача линейного программирования
Решимзадачу линейного программирования симплекс – методом:
f(x) = 2x1 + 3x2 + 4x3→ max
3x1 + x2 + 3x3
5x1 + 4x2 + 4x3
2x1 + x2 + 2x3
x1>=0; x2>=0; x3>=0;
Данныезадачи заносим в симплекс таблицу. x1 x2 x3 x4 x5 x6 значения базис оценка 3 1 3 1 0 0 5 x4 5/3 5 4 4 0 1 0 12 x5 3 2 1 2 0 0 1 8 x6 4 2 3 4 0 0 0 0 - f
Вэтой таблице первая, вторая и третья строки соответствуют ограничениям задачи,последняя строка – функция цели. Это оценочная строка. Значение функции целиберём 0. Выделяем базисные переменные. Эта переменная находиться в столбце, длякоторой имеется одна единица, остальные нули. В столбце «базис» отмечаемодноимённые переменные в той строке, где расположена эта единственная единица.Остальные переменные называются свободными.
Позаполненной симплекс таблице определяем решение, соответствующее этой (нулевой)итерации. Свободные переменные равны 0. Базисные переменные и значение функциинаходим из таблицы. Они представлены в столбце «значение». Отметим, чтозначение функции цели берём с противоположенным знаком. Итак, x° = (0,0,0,5,12,8) f° = 0.
Воценочной строке имеются положительные числа. Значит, решение можно улучшить.Выбираем наибольшее из положительных чисел. Если таких чисел несколько – берёмлюбое из них. Соответствующий столбец называют ведущим. По ведущему столбу истолбцу «значения» определяем оценку для каждой строки. Число из столбца «значение»делим на строку. По условию задачи это положительное число. Объявляем ведущейстроку ту, оценка у которой наименьшее положительное число.
Впервой таблице ведущая строка и столбец выделен цветом. На их пересечениинаходится ведущий элемент. В нашем случае это 3.
Переходимк первой итерации. Её суть состоит в том, чтобы свободную x3 сделать базисной, а базиснуюпеременную x4 — свободной. В таблицевыполняем преобразования аналогичные элементарным строчным преобразованияаналогичные элементарным строчным преобразованиям в методе Гаусса при решениисистемы линейных уравнений. В результате преобразований получим: x1 x2 x3 x4 x5 x6 значения базис оценка 1 1/3 1 1/3 0 0 5/3 x3 5 1 8/3 0 -4/3 1 0 16/3 x5 2 0 1/3 0 -2/3 0 1 14/3 x6 14 -2 5/3 0 -4/3 0 0 -20/3 - f
Из таблицы находим базисные переменные и значение функции x¹= (0,0,5/3,0,16/3,14/3) f¹ = 20/3. Этот результат можнопроверить. Полученные результаты должны удовлетворять функции цели вканонической (стандартной) задаче линейного програмирования. В оценочной строкеимеются положительные числа. Значит, решение можно улучшить. Аналогично строимследующую таблицу: x1 x2 x3 x4 x5 x6 значения базис оценка 5/8 0 1 1/2 -1/8 0 1 x3 - 3/8 1 0 -1/2 3/8 0 2 x2 - -1/8 0 0 -1/2 -1/8 1 4 x6 - -21/8 0 0 -1/2 -5/8 0 -10 - f
В оценочной строке данной таблицы все элементы не положительны. Это и означает,что симплекс метод завершён. Результат последней итерации даёт ответ напоставленную задачу.
f* = 10 x* =(0,2,1)
§5.Пример решения Транспортной задачи
Метод потенциаловпредставляет из себя модификацию симплекс-метода, учитывающую спецификутранспортной задачи, поэтому его алгоритм не отличается от алгоритма симплекс-метода,за исключением шага проверки целевой функции на неограниченность на множестверешений. Отсутствие указанного шага в методе потенциалов обусловлено теоремой отом, что закрытая ТЗ всегда разрешима. Итак, алгоритм метода потенциаловдля решения ТЗ состоит из следующих шагов:
ШАГ 1. Построениеначального плана перевозок.
ШАГ 2. Проверкатекущего плана на оптимальность.
Если план оптимален,то алгоритм завершен.
ШАГ 3. Улучшение планаперевозок. Переход к шагу 1.
Опишемалгоритм по шагам, иллюстрируя каждый шаг
ШАГ 1. Построениеначального плана перевозок.
Построение начального решения(как и последующие расчеты) проводят в таблице, имеющей следующий вид:
/>
Клетка ( i, j ) таблицы соответствует коммуникации, связывающей i-гопоставщика сj-м потребителем.
Построить начальный планперевозок означает — назначить объемы перевозок в клетки таблицы таким образом,чтобы:
а)число заполненныхклеток было (m+n-1).(Тогда план перевозок будет отвечать базисному решению ЗЛП);
б)сумма перевозок в любойстроке должна быть равна запасу соответствующего поставщика, а сумма перевозокв каждом столбце равна потребности потребителя. (Условие выполнения ограниченийТЗ). Существует несколько способов нахождения начального решения, которыеотличаются только выбором клетки, в которую назначается очередная перевозка.Так, в способе северо-западного угла (СЗУ) для очередного назначенияперевозки выбирается левая верхняя клетка таблицы (при этом никак неучитываются цены перевозок). Наоборот, в способе минимальной стоимости (МС) длязаполнения выбирается клетка текущей таблицы с минимальной ценой перевозки, чтов большинстве случаев (но не всегда) приводит к более дешевому (а значит иболее близкому к оптимальному) начальному плану перевозок.
Мы будем пользоваться способомминимальной стоимости (МС).
Изложим теперь алгоритмнахождения начального решения.
ШАГ 1. Определенным способом выбираем клетку в текущейтаблице. Пусть она имеет индексы (i, j) (i -номер поставщика, j — номер потребителя).
ШАГ 2. В качестве перевозок в эту клетку назначаем наименьшуюиз ai и потребности bj.
xij = min{ai,bj }
ШАГ З. Уменьшим запас ai и потребность bj на величину перевозки xij, т.е.
ai = ai — xij,
bj =bj -xij
ШАГ 4. При исчерпании запаса (ai = 0) запрещаем к перевозке оставшиеся свободные клетки i-ойстроки, а при исчерпании потребности
(bj =0) запрещаемтакие же клетки вj-ом столбце.
В случае одновременногоисчерпания запасов потребностей (ai =bj = 0) запрещаем перевозки или в строке (тогда считаем, что употребителя осталась потребность в количестве равном нулю, которую необходимоудовлетворить), или в столбце (в этом случае считаем, что у поставщика остаетсязапас равный нулю, который необходимо вывезти). Это делается для того, чтобыпри одновременном запрещении перевозок в строке и столбце количествозаполненных клеток таблицы не стало меньшим, чем m+n-1.
Получим новую текущуютаблицу, в которую не входят заполненные и запрещенные клетки. Если таблица непуста, переходим к шагу 1. (При исчерпании таблицы — конец).
Способ минимальнойстоимости
/>
1.Клетки с минимальнойценой (3,1), (3,2) и (3,3). Выбираем, например, (3,2). (Далее все шаги, как впредыдущем способе).
2. x32 = min{50,60} = 50
3. a '3=50-50=0, b '2 = 100-50=50
4.Запрещаем строку 3.
/>
1. Клетка с min ценой ~ (2,3)
2. x23 = min{70,80} = 70
3. a2=70-70=0, b'3= 80-70=10
4. Запрещаем строку 2. 1 2 3 60
5
60 10 12 Χ
8
-
6
-
4
70 Χ
50
- 50 10
1. Клетка с min ценой ~ (1,1)
2. x 11=min{120,60} =60
3. a 1' =120-60 = 60, b1' = 0
4.В первом столбцезапрещать уже нечего. Текущая таблица содержит две клетки (1,2) и (1,3).
/>
1.Выбираем клетку (1,2)
2.x 12 =min{110,100} = 100
3.a 1 =110-100 = 10, b'1 = 0
4.Текущая таблица содержитодну клетку (1,3).
/>
1. Выбираем последнюю клетку(1,3)
2. x13=min{10,10} = 10
3.a1' = b3 = 0
4.Таблица исчерпана.Конец.
Переходим к описаниюследующего шага метода потенциалов.
ШАГ 2. Проверка текущего плана наоптимальность.
Признаком того, чтотекущий план перевозок является оптимальным, служит условие
(1)ui +vj -cij ≤0
которое выполняется для всехклеток таблицы. Неизвестные здесь величины ui и vj (называемые потенциалами)определяются из условий
(2)ui + vj = cij
Условие (1) означаетневозможность появления «спекулятивной» цены. Само же название«потенциалы» заимствовано из физического закона о том, что работа поперемещению заряда в электростатическом поле равна разности потенциалов вданных точках поля (У нас: "… цена перевозки единицы продукции покоммуникации равна разности цен в конце и в начале пути")
Так как заполненныхклеток в таблице (m+n-1) штук, а неизвестных и (m+n) штук, то для их определения имеется система из (m+n-1) уравнений относительно (m+n) неизвестных. Чтобы найти решение(хотя бы какое-нибудь) такой системы, достаточно положить одно из неизвестных(произвольное) равным некоторому произвольно выбранному числу. Тогда остальныеопределяются единственным образом. Можно решать эту систему непосредственно(продолжаем работать с нашим «старым» примером и найдем потенциалыдля начального плана, построенного способом МС).
Заполненные клетки Уравнения
(1,1) u1+ v1 =5
(1,2) u1+ v2 =10
(1,3) u1+ v3 =12
(2,3) u2+v3 =4
(3,2) u3 +v2 =0
Положим, например,неизвестное u 1 равным 0 (через него можно из первых трех уравненийнайти v1, v2 и v3). Последовательно из них находим u 2, u 3.
Этот метод можносформулировать в виде единой правилы:
Неизвестный потенциал находитсявычитанием известного из цены перевозки в заполненной клетке
Применим это правило дляопределения u и v в нашем примере и получим:
u1 =0, u2 =-8, u3=-6
v1 =5, v2 =10, v3 =12
Переходим к проверкеусловий оптимальности (1). Достаточно проверять их для незаполненных клеток,так как для клеток заполненных эти условия выполняются как равенства. Дляпроверки берется незаполненная клетка, складываются соответствующие ейпотенциалы (первый элемент строки и последний элемент столбца) и из нихвычитается цена перевозки в данной клетке. Если полученное число отрицательное(или ноль), то оптимальность в данной клетке не нарушается (в случае выполненияусловия (1) для всех незаполненных клеток, имеем оптимальный план перевозок).Если же в таблице встретилась хотя бы одна клетка, для которой это числоположительно, тогда решение не является оптимальным и может быть улучшено.
Проверим на оптимальностьимеющееся решение
(2,1) u2+v1-c21=-8+5-8=-11
(2,2) u 2 +v2 -c22=-8+10-6=-4
(3,1) u 3 +v1 -c31=-10+ 5-0=-5
(3,3) u 3 +v3 -c33=-10+12-0=2>0
Следовательно, условие оптимальностинарушено в клетке (3,3).
Имеющийся план перевозокможно улучшить.
Дадим описаниезаключительного шага алгоритма метода потенциалов.
ШАГ 3 Улучшение плана перевозок.
Улучшение планапроисходит путем назначения перевозки θ>0 в ту клетку (i, j) таблицы, в которой нарушилось условие оптимальности. Ноназначение ненулевой перевозки нарушает условия баланса вывоза продукции отпоставщика i (вывозит весь запас и еще плюсθ>0 ) и условия баланса привоза продукции кпотребителю j (получает все что можно и еще плюс θ> 0). Условия баланса восстанавливают путем уменьшения вывоза от i-поставщикак какому-то другому потребителю j (уменьшают на θперевозку в какой-то заполненной клетке (i, j) строкиi). При этом нарушается баланс привозапродукции к потребителю j(получает на θ меньше, чем ему требуется). Восстанавливают баланс встолбце j, тогда он нарушается в некоторой строке i и т.д. до тех пор,пока цикл перемещения перевозок не замкнется на клетке, в которой нарушалосьусловие оптимальности. Продемонстрируем эти рассуждения на нашем примере.
/>120 60 50+ Ө 10- Ө 70 - - 70 50 - 50- Ө * + Ө 60 100 80 120 60 60 -(0) 70 - - 70 50 - 40 * 10 60 100 80
1. Оптимальность нарушенав клетке (3,3). Назначим в нее перевозку θ>0 (+θ означает,увеличение на θ).
2.Нарушается балансвывоза от поставщика 3 (вывозит 50+ θ, а это больше его запаса!). Уменьшаемна θ перевозку в заполненной клетке строки 3 (вне заполненной уменьшатьнельзя, так как это приведет к отрицательной перевозке).
Рассмотрим те клеткицикла в которых уменьшаем на θ перевозку и берём минимум из вычетаемых, унас это min{10- θ ,50- θ }=10.
И данное число надоподставить в цикл
Список литературы
1. Матвеев В.А.Конечные бескоалиционные игры и равновесия. Псков, 2004,176с.
2. Аладьев В.З.,Богдявичюс М.А. MAPLE 6: Решениематематических, статистических и физико – технических задач – М.: ЛабораторияБазовых Знаний,2001 – 824с..
3. Петросян Л.А.,Зенкевич Н.А., Семина Е.А. Теория игр. М.: ВШ, Книжный дом «Университет», 1998.
4. Акулич И.Л.Математическое программирование в примерах и задачах. М.: Высшая школа, 1993.
5. Воробьёв Н.Н.Основы теории игр. Бескоалиционные игры. М.: Наука, 1984.
6. Прохоров Г.В.,Колбеев В.В., Желнов К.И., Леденев М.А… Математический пакет Maple V Release 4. М. 1998.