- •Оглавление Введение. Экономика и математика Часть I. Линейные модели и методы в экономике.
- •Глава 1. Принятие решений в экономике
- •Глава 2. Линейное программирование. Теоретические основы и алгоритмы.
- •Глава 3. Теория двойственности в линейном программировании и ее экономические приложения.
- •Глава 4. Транспортная задача и ее приложения.
- •Глава 5. Задача целочисленного линейного программирования
- •Введение. Экономика и математика
- •Часть I. Линейные модели и методы в экономике.
- •Глава 1. Принятие решений в экономике.
- •1.1. Моделирование
- •1.2. Математическое моделирование.
- •1.3. Алгоритм исследования операции.
- •Алгоритм исследования операций.
- •1.4. Примеры исследования операции (моделирование)
- •1.5.Классификация моделей и методов исследования операций
- •Глава 2.
- •2.1. Постановки задачи линейного программирования
- •Основная задача линейного программирования (ОснЗлп)
- •Каноническая задача линейного программирования (кзлп)
- •2.2. Выпуклые множества.
- •0Пределение 2.4.
- •2.3. Теоретические основы линейного программирования
- •2.4. Графический метод и анализ решения злп
- •Проведем графический анализ решения (модели) на чувствительность.
- •2.5. Симплекс-метод решения злп.
- •Определение к-матрицы кзлп
- •Переход от одной к-матрицы злп к другой к-матрице
- •Симплекс-разность к-матрицы злп
- •Алгоритм симплекс-метода
- •2.6. Двойственный сиплекс-метод (р-метод)
- •Определение р-матрицы злп
- •Условия перехода от одной р-матрицы злп к другой
- •Решение задач р-методом
- •2.7.Метод искусственного базиса Назначение и принцип работы методов искусственного базиса
- •2.8. Модифицированный симплекс-метод Постановка задачи
- •Алгоритм модифицированного симплекс-метода
- •Решение задачи модифицированным симплекс-методом
- •2.9. Решение злп на основе Ms Excel
- •Глава 3. Теория двойственности в линейном программировании и ее экономические приложения.
- •3.1. Определение двойственной задачи:
- •3.2. Основные теоремы двойственности
- •3. 3. Экономическая интерпретация двойственности
- •Экономическое содержание теории двойственности.
- •3.4.Применение теории двойственности к решению задач. Применение теоремы 3.5 к решению дз.
- •3.5. Анализ решения злп на основе отчетов ms excel
- •2. Определите статус, ценность каждого ресурса и его приоритет при решении задачи увеличения запаса ресурсов.
- •3. Определите максимальный интервал изменения запасов каждого из ресурсов, в пределах которого структура оптимального плана, то есть номенклатура выпускаемой продукции, остается без изменения.
- •4. Определите суммарную стоимостную оценку ресурсов (себестоимость), используемых при производстве единицы каждого изделия. Производство какой продукции нерентабельно?
- •5. На сколько уменьшится стоимость выпускаемой продукции при принудительном выпуске единицы нерентабельной продукции?
- •6. На сколько можно снизить запас каждого из ресурсов, чтобы это не привело к уменьшению прибыли?
- •8. Определите оптимальное решение задачи для случая, когда вектор ресурсов задан в виде .
- •9. Определите интервалы изменения цен на каждую продукцию, при которых сохраняется оптимальный план.
- •10. На сколько нужно снизить затраты каждого вида сырья на единицу продукции, чтобы сделать производство нерентабельного изделия рентабельным?
- •11. На сколько нужно изменить запас каждого из дефицитных ресурсов, чтобы прибыль возросла на 20%?
- •3. Определите суммарную стоимостную оценку питательных веществ в единице каждого корма, использование какого вида корма нерентабельно.
- •Глава 4. Транспортная задача линейного программирования
- •0, Если безразлично, какой потребитель недополучит заявленного количества груза
- •4.3. Экономические задачи, сводящие к транспортной задаче.
- •Теорема о разрешимости транспортной задачи
- •4.4. Опорный план тз. Алгоритмы нахождения исходного плана.
- •4.4.1. Определения опорного плана тз.
- •4.4.2. Методы составления первоначальных опорных планов
- •4.5. Метод потенциалов решения транспортной задачи
- •4.6. Задача о назначениях
- •Глава 5. Задача целочисленного линейного программирования
- •5.1.Постановки и методы решения
- •5.2.Метод ветвей и границ решения целочисленных задач линейного программирования (цзлп)
- •5.3. Задача Коммивояжера.
5.2.Метод ветвей и границ решения целочисленных задач линейного программирования (цзлп)
Задачей целочисленного линейного программирования (ЗЦЛП) называют следующую:
Найти вектор , максимизирующий линейную форму
(5.9)
и удовлетворяющий условиям:
(5.10)
(5.11)
- целые (5.12)
При p = n (p < n) задача (5.9)-(5.12)- называется полностью (частично) целочисленной задачей линейного программирования.
Для решения ЗЦЛП обычно применяются методы типа отсечений, например, метод Гомори и методы типа возврата - метод ветвей и границ.
Метод ветвей и границ применим для решения как полностью, так и частично целочисленных задач. Пусть, для каждой целочисленной переменной можно указать верхнюю и нижнюю границы, в пределах которых безусловно содержатся ее оптимальные значения, то есть
, (5.13)
которые являются функциональными ограничениями.
В начале любой S-й итерации метода ветвей и границ необходимо иметь:
1) основной список (ОС) задач линейного программирования, каждая из которых должна быть решена в последующих итерациях (на первой итерации список содержит одну ЗЛП - ЗI (5.9-5.11) и (5.13).
нижнюю границу оптимального значения линейной формы задачи (5.9-5.11) и (5.13) - , S = 2,3,...... . На первой итерации в качестве можно взять значение функции в любой целочисленной точке, лежащей внутри области (5.10)- (5.11) и (5.13). Если такую точку указать трудно, то можно положить = - , но это приводит к значительному увеличению числа итераций.
Алгоритм S-й итерации метода ветвей и границ.
Пусть в результате S итераций метода получили список из N задач: 1,2,...,Z, …N и имеем .
Шаг 1. Выбираем из списка ЗЛП одну задачу для решения, задачу Z и решаем ее.
Шаг 2. Если задача Z имеет решение, то переходим к шагу 3. В противном случае - исключаем задачу Z из списка и, полагая , возвращаемся к шагу 1. При S = 0, то есть на первой итерации, делаем вывод, что исходная задача (5.9)-(5.13) не имеет решения, и процесс решения заканчивается.
Шаг 3. Если > , то переходим к шагу 4. В противном случае - задачу Z исключаем из списка и, полагая , возвращаемся к шагу 1.
Шаг 4. Если не все компоненты вектора удовлетворяют условиям целочисленности (5.12), то переходим к шагу 5. В противном случае - задачу Z из списка исключаем, план - запоминаем и, полагая = , возвращаемся к шагу 1. При S = 0 вектор является решением и исходной задачи (5.9)-(2.12) и процесс решения заканчивается.
Шаг 5. Задачу Z исключаем из списка, включая в него две новые задачи линейного программирования - задачу (Z+1) и задачу (Z+2). Далее, полагая , возвращаемся к шагу 1. Процесс разбиения задачи Z на две новые ЗЛП осуществляется следующим образом: Пусть - дробная компонента в полученном оптимальном плане и ее целая часть равна . Тогда задача Z+1 имеет вид:
,
………………
……………….
Задача Z+2:
,
………………
………………..
Процесс решения продолжаем до тех пор, пока не будут решены все задачи линейного программирования из списка. Тогда решением задачи (5.9)-(5.12) и (5.13) будет вектор для которого = на последней итерации.
Пример 5.4. Решить ЗЦЛП.
- целые числа (3)
(4)
(5)
Основной список содержит ЗI – (1), (2), (4), (5). Положим =0, т.к. точка (0, 0) – целочисленный план этой задачи.
Итерация 1. Шаг 1.
Решаем задачу (1), (2), (4), (5). Ее решением будет точка = C = (4,5;2.5),
Шаг 2. Так как ЗI имеет решение, то переходим к шагу 3.
Шаг 3. Так как , то переходим к шагу 4.
Шаг 4. Так как обе компоненты вектора не целые, то переходим к шагу 5.
Шаг 5. ЗI исключаем из ОС и включаем в него 2 новые задачи ЗII и ЗIII.
Пусть -дробная компонента, ее целая часть [4,5]=4. Следовательно, ЗII и ЗIII будут иметь вид:
ЗII |
ЗIII |
(4) (5)
|
(4) (5)
|
Далее полагая = , переходим к шагу 1.
Итерация 2.
ОС содержит ЗII и ЗIII, =0.
Шаг1. Выбираем из ОС ЗII и решаем ее. Ее решением будет =К=(4;8/3)
Шаг 2. Т.к. ЗII имеет решение, то переходим к шагу 3.
Шаг 3. Т.к. > , то переходим к шагу 4.
Шаг 4. Т.к. -дробная, то переходим к шагу 5.
Шаг 5. ЗII выбрасываем из ОС и включаем в него 2 новые задачи ЗIV и ЗV.
Т.к. [8/3]=2, то. Следовательно, ЗIV и ЗV будут иметь вид:
ЗIV |
ЗV |
(4) (5)
|
(4) (5)
|
Далее полагая = , переходим к шагу 1
Итерация 3.
ОС содержит ЗIII, ЗIV и ЗV, =0.
Шаг 1. Выбираем из ОС ЗIII и решаем ее. Ее решением будет =L=(5;20/9)
Шаг 2. Т.к. ЗIII имеет решение, то переходим к шагу 3.
Шаг 3. Т.к. > , то переходим к шагу 4.
Шаг 4. Т.к. -дробная, то переходим к шагу 5.
Шаг 5. ЗIII исключаем из ОС и включаем в него 2 новые задачи ЗVI и ЗVII.
Т.к. [20/9]=2, то, следовательно, ЗVI и ЗVII будут иметь вид:
ЗVI |
ЗVII |
(4) (5)
|
(4) (5)
|
Далее полагая = , переходим к шагу 1.
Итерация 4.
ОС содержит ЗIV и ЗV, ЗVI и ЗVII =0.
Шаг 1. Выбираем из ОС ЗIV и решаем ее. Ее решением будет =M=(4;2)
Шаг 2. Т.к. ЗIV имеет решение, то переходим к шагу 3.
Шаг 3. Т.к. > , то переходим к шагу 4.
Шаг 4. Т.к. обе компоненты целочисленные, то задачу ЗIV из ОС исключаем, план запоминаем и, полагая =8= , переходим
к шагу 1.
Итерация 5.
ОС содержит ЗV, ЗVI и ЗVII =8.
Шаг 1. Решаем ЗV . Ее решением будет =D=(3;3).
Шаг 2. Т.к. ЗV имеет решение, то переходим к шагу 3.
Шаг 3. Т.к. > , то переходим к шагу 4.
Шаг 4. Т.к. обе компоненты целочисленные, то задачу ЗV из ОС исключаем, план запоминаем и, полагая =9= , переходим к шагу 1.
Итерация 6.
ОС содержит ЗVI и ЗVII =9.
Шаг 1. Выбираем из ОС ЗVI и решаем ее. Ее решением будет =N=(27/5;2)
Шаг 2. Т.к. ЗVI имеет решение, то переходим к шагу 3.
Шаг 3. Т.к. > , то переходим к шагу 4.
Шаг 4. Т.к. -дробная, то переходим к шагу 5.
Шаг 5. ЗVI выбрасываем из ОС и включаем в него 2 новые задачи ЗVIII и ЗIX.
Т.к. [27/5]=5, то. Следовательно, ЗVIII и ЗIX будут иметь вид:
ЗVIII |
ЗIX |
(4) (5)
|
(4) (5)
|
Далее полагая = , переходим к шагу 1.
Итерация 7.
ОС содержит ЗVII, ЗVIII и ЗIX =9.
Шаг 1. Выбираем из ОС ЗVII и решаем ее. Она не имеет решения, т.к. множество ее планов пусто.
Шаг 2. Т.к. ЗVII не имеет решения, то исключаем её из ОС и переходим к шагу 1, полагая что = .
Итерация 8.
ОС содержит, ЗVIII и ЗIX =9.
Шаг1. Выбираем из ОС ЗVIII и решаем ее. Ее решением будет =О=(5;2),
Шаг 2. Т.к. ЗVIII имеет решение, то переходим к шагу 3.
Шаг 3. Т.к. = , то переходим к шагу 4.
Шаг 4. Т.к. обе компоненты целочисленные, то ЗVIII из ОС исключаем, план запоминаем и, полагая =9= , переходим к шагу 1.
Итерация 9.
ОС содержит ЗIX =9.
Шаг 1. Выбираем из ОС ЗIX и решаем ее. Ее решением будет =P=(6;15/9)
Шаг 2. Т.к. ЗIX имеет решение, то переходим к шагу 3.
Шаг 3. Т.к. > , то переходим к шагу 4.
Шаг 4. Т.к. -дробная, то переходим к шагу 5.
Шаг 5. ЗIX исключаем из ОС и включаем в него 2 новые задачи ЗX и ЗXI.
Т.к. [15/9]=1, то. Следовательно, ЗX и ЗXI будут иметь вид:
ЗX |
ЗXI |
(4) (5)
|
(4) (5)
|
Далее полагая = , переходим к шагу 1.
Итерация 10.
ОС содержит ЗX и ЗXI =9.
Шаг 1. Выбираем из ОС ЗX и решаем ее. Ее решением будет =Q=(36/5;1)
Шаг 2. Т.к. ЗX имеет решение, то переходим к шагу 3.
Шаг 3. Т.к. > , то переходим к шагу 4.
Шаг 4. Т.к. -дробная, то переходим к шагу 5.
Шаг 5. ЗX исключаем из ОС и включаем в него 2 новые задачи ЗXII и ЗXIII.
Т.к. [36/5]=7, то. Следовательно, ЗXII и ЗXIII будут иметь вид:
ЗXII |
ЗXIII |
(4) (5)
|
(4) (5)
|
Далее полагая = , переходим к шагу 1.
Итерация 11.
ОС содержит ЗXI, ЗXII и ЗXIII = 9.
Шаг1. Выбираем из ОС ЗXI и решаем ее. Она не имеет решения, т.к. множество ее планов пусто.
Шаг 2. Т.к. ЗXI не имеет решения, то исключаем её из ОС и переходим к шагу 1, полагая что = .
Итерация 12.
ОС содержит ЗXII и ЗXIII =9.
Шаг 1. Выбираем из ОС ЗXII и решаем ее. Ее решением будет =R(7;1)
Шаг 2. Т.к. ЗXII имеет решение, то переходим к шагу 3.
Шаг 3. Т.к. = , то переходим к шагу 4.
Шаг 4. Т.к. обе компоненты целочисленные, то задачу ЗXII из ОС исключаем, план запоминаем и, полагая =9= переходим к шагу 1.
Итерация 13.
ОС содержит ЗXIII =9.
Шаг 1.Выбираем из ОС ЗXIII и решаем ее. Ее решением будет =T = (8;5/9)
Шаг 2. Т.к. ЗXIII имеет решение, то переходим к шагу 3.
Шаг 3. Т.к. > , то переходим к шагу 4.
Шаг 4. Т.к. -дробная, то переходим к шагу 5.
Шаг 5. ЗXIII исключаем из ОС и включаем в него 2 новые задачи ЗXIV и ЗXV.
Т.к. [5/9]=0, следовательно, ЗXIV и ЗXV будут иметь вид:
ЗXIV |
ЗXV |
(4) (5)
|
(4) (5)
|
Далее полагая = , переходим к шагу 1.
Итерация 14.
ОС содержит ЗXIV и ЗXV =9.
Шаг 1. Выбираем из ОС ЗXIV и решаем ее. Ее решением будет =Z=(9;0)
Шаг 2. Т.к. ЗXIV имеет решение, то переходим к шагу 3.
Шаг 3. Т.к. = , то переходим к шагу 4.
Шаг 4. Т.к. обе компоненты целочисленные, то задачу ЗXIV из ОС исключаем, план запоминаем и, полагая =9, переходим к шагу 1.
Итерация 15.
ОС содержит ЗXV =9.
Шаг1. Выбираем из ОС ЗXV и решаем ее. Она не имеет решения, т.к. множество ее планов пусто.
Шаг 2. Т.к. ЗXV не имеет решения, то переходим к шагу 1, полагая что = .
Итерация 16.
Шаг1. Т.к. ОС пуст, то задача решена.
Задача (1)-(5) имеет 4 оптимальных плана: