- •Раздел 1. Модели линейного программирования и его приложения Тема 1. Математическое моделирование экономических систем
- •1.1. Описание процесса математического моделирования.
- •1.2. Примеры построения математических моделей простейших экономических задач
- •1. Задача об использовании ресурсов (планирование производства, задача оптимального использования удобрений и т.Д.).
- •2. Оптимальное смешивание (составление рациона питания, смесей, задача о диете и т.Д.).
- •3. Задача об использовании мощностей (задача о загрузке оборудования)
- •4. Задача о раскрое материалов
- •Рекомендованная литература: [ 3, 8, 11, 12] Тема 2. Линейные векторные пространства
- •Понятие n-мерного пространства
- •Задача о закреплении самолетов за воздушными линиями.
- •Контрольные вопросы
- •Линейная зависимость векторов
- •2.3. Базис n-мерного векторного пространства
- •2.4. Система единичных векторов n-мерного векторного пространства
- •2.5. Решение системы линейных уравнений методом Жордана – Гаусса
- •Контрольные вопросы
- •Для приведения неравенства к равенству необходимо к его левой части прибавить неотрицательную величину . (2)
- •Пусть удовлетворяет уравнению (3) и неравенству (2), т.Е.
- •3.2. Выпуклые множества
- •3.3. Геометрическая интерпретация задачи линейного программирования
- •3.4. Свойства решений задачи линейного программирования
- •Контрольные вопросы
- •Примеры задач, решаемых графическим методом.
- •4.2. Графический метод решения злп с n переменными
- •Контрольные вопросы
- •5.2. Алгоритм симплекс-метода
- •5.3. Пример отыскания максимума линейной функции
- •5.4. Пример отыскания минимума линейной функции
- •Решение. Введем дополнительные неотрицательные переменные y5, y6 со знаком “-”, т.К. Неравенства имеют вид ””:
- •Симплексные таблицы
- •В общем случае достаточно воспользоваться правилом:
- •5.6. Метод искусственного базиса
- •Контрольные вопросы
- •Предположим, что некоторая организация решила закупить ресурсы s1, s2,…, Sm предприятия и необходимо установить оптимальные цены на эти ресурсы y1,y2,…,ym.
- •Аналогично стоимость всех затраченных ресурсов, идущих на изготовление единицы j-ой продукции, не может быть меньше стоимости окончательного продукта, т.Е.
- •6.2. Взаимно двойственные задачи линейного программирования и их свойства
- •6.3. Первая теорема двойственности
- •6.4. Вторая теорема двойственности
- •Рассмотренная теорема является следствием следующей теоремы.
- •6.5. Объективно обусловленные оценки и их смысл
- •Контрольные вопросы
- •7.2. Нахождение опорного плана
- •Пример 1. Исходные данные приведены в таблице 1.
- •7.3. Метод последовательного улучшения плана перевозок, цикл пересчета
- •7.4. Решение транспортной задачи методом потенциалов
- •Приложения транспортной задачи к решению некоторых экономических задач
- •Контрольные вопросы
- •Понятие цикла. Рекомендованная литература: [ 3, 5, 6, 7, 8, 11]
- •Тема 8. Элементы теории матричных игр
- •8.1. Предмет теории игр, основные понятия
- •8.2. Платежная матрица. Нижняя и верхняя цена игры
- •8.3. Решение игры в смешанных стратегиях
- •Решая эту систему, получим оптимальную стратегию:
- •8.4. Геометрическая интерпретация игры 2 х 2
- •8.5. Приведение матричной игры к задаче линейного программирования
- •Составив расширенные матрицы для задач, убеждаемся, что одна матрица получилась из другой транспонированием:
- •Контрольные вопросы
- •Графический метод решения игры mx2. Рекомендованная литература: [ 1, 2, 4, 9, 12] раздел 2. Модели нелинейного программирования
- •Тема 9. Нелинейное программирование
- •9.1. Общая задача нелинейного программирования
- •9.2. Метод множителей Лагранжа
- •9.3. Обобщёние метода множителей Лагранжа
- •9.4. Теорема Куна-Таккера
- •9.5. Модели выпуклого программирования
- •9.6. Приближенное решение задач выпуклого программирования методом кусочно-линейной аппроксимации
- •Контрольные вопросы
- •Задачі про мінімізацію розходу горючого літаком за набором висоти та швидкості. Рекомендованная литература: [ 3, 6, 7, 8, 11] Бібліографічний список
7.3. Метод последовательного улучшения плана перевозок, цикл пересчета
В ТЗ переход от одного опорного плана к другому осуществляется с помощью цикла. Для некоторой свободной клетки таблицы строится цикл, содержащий часть клеток, занятых опорным решением.
Циклом пересчета называется такой цикл в таблице с базисным распределением перевозок, при котором одна из его вершин лежит в свободной клетке, остальные – в занятых.
Цикл пересчета называется означенным, если в его вершинах расставлены знаки “+” и “-“ так, что в свободной клетке стоит знак “+”, а соседние вершины имеют противоположные знаки.
Сдвигом по циклу на некоторую величину называется увеличение объемов перевозок во всех клетках цикла, отмеченных знаком “+”, и уменьшение объемов перевозок на ту же величину во всех клетках цикла, отмеченных знаком “-“. По-другому это может называться перенос («переброс») какого-то количества единиц груза по означенному циклу.
Очевидно, что при переносе любого числа единиц по циклу, равновесие между запасами и заявками не меняется: по-прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозок в каждом столбце - заявке этого столбца. Таким образом, при любом циклическом переносе, оставляющем перевозки неотрицательными, допустимый план остается допустимым, хотя стоимость плана может изменяться - увеличиваться или уменьшаться.
Теорема. Для каждой свободной клетки транспортной таблицы всегда существует и притом единственный цикл пересчета, одна из вершин которого лежит в этой свободной клетке, а все остальные - в базисных клетках.
При улучшении плана циклическими переносами пользуются приемами, заимствованными из симплекс-метода: при каждом шаге (цикле) заменяют одну свободную переменную на базисную, т.е. заполняют одну свободную клетку и взамен этого освобождают одну из базисных клеток. При этом общее число базисных клеток остается неизменным и равным m + n - 1. Таким образом, по построенному циклу перераспределяются объемы перевозок (осуществляется сдвиг по циклу). Перевозка “загружается” в выбранную клетку и освобождается одна из занятых клеток, получается новый опорный план.
Количество единиц груза , которое можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла (если переместить большее число единиц груза, возникнут отрицательные перевозки). Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что дальнейшее улучшение плана невозможно, т.е. оптимальный план достигнут.
7.4. Решение транспортной задачи методом потенциалов
С помощью рассмотренных методов построения первоначального плана можно получить вырожденный или невырожденный опорный план. Построенный опорный план ТЗ как ЗЛП можно было бы довести до оптимального с помощью симплекс-метода. Однако из-за громоздкости симплексных таблиц, содержащих mn переменных, и большого объема вычислительных работ для получения оптимального плана используют более простые методы, самый распространенный из которых метод потенциалов (модифицированный распределительный метод).
Пусть имеется ТЗ с балансовыми условиями
;
,
причем
.
Стоимость перевозки единицы груза из Ai в Bj равна cij; таблица стоимостей (cij) задана. Требуется найти план перевозок (xij), который удовлетворял бы балансовым условиям, и при этом стоимость всех перевозок была минимальна:
L = min.
Идея метода потенциалов. Представим себе, что каждый из пунктов отправления Ai вносит за перевозку груза сумму Ui, в свою очередь каждый из пунктов назначения Bj также вносит за перевозку единицы груза сумму Vj.
Обозначим
Ui
+ Vj
=
(i=1,
...,m;
j=1,
...,n)
и будем называть
«псевдостоимостью» перевозки единицы
груза из Ai
в Bj.
Ui,
и Vj
не обязательно должны быть положительными.
Обозначим совокупность платежей U1,
..., Um,
V1,
..., Vn
через (Ui,
Vj).
Предположим, что план (xij) невырожденный, т.е. число базисных клеток в таблице перевозок равно m + n - 1. Для всех этих клеток xij > 0. Определим платежи
(Ui, Vj) так, чтобы во всех базисных клетках псевдостоимости были равны стоимостям:
=Ui + Vj = cij при xij > 0;
Что касается свободных клеток, то для них соотношение между псевдостоимостями и стоимостями может быть каким угодно: = cij или > cij или < cij.
Теорема.
Если план
ТЗ
является оптимальным, то можно отыскать
систему из m+n
чисел
и
,
для которой будут выполняться равенства:
(1)
+
=cij
для
>0,
где сij
– элементы матрицы транспортных затрат,
соответствующие занятым данным решением
клеткам;
(2) + cij для =0, где сij – элементы матрицы, соответствующие незанятым оптимальным решением клеткам.
Числа и называются потенциалами соответственно поставщиков и потребителей.
Доказательство.
ТЗ минимизации линейной функции L = при ограничениях
можно
рассматривать как двойственную некоторой
исходной ЗЛП, условия которой получают
по общей схеме, рассмотренной выше, если
каждому ограничению вида (*) в исходной
задаче соответствует переменная Ui
(i=1,2,…,m),
а каждому ограничению вида (**) –
переменная Vj
(j=1,2,…,n),
а именно максимизировать линейную
функцию Z=
при
ограничениях
+
cij
(i=1,2,…,m,
j=1,2,…,n).
План Х* - оптимальный план двойственной
задачи, поэтому план Y*=(
,
)
является планом исходной задачи и на
основании второй теоремы двойственности
Lmax=Zmin
или
На основании второй теоремы получаем, что ограничения исходной задачи, соответствующие положительным компонентам оптимального плана двойственной задачи, удовлетворяются удовлетворяются как строгие равенства, а соответствующие компонентам, равным нулю, - как неравенства, т.е.
+ =cij для x* ij>0;
+ cij для x* ij=0.
План, обладающий таким свойством, называется потенциальным. Всякий потенциальный план является оптимальным.
На основании теоремы для того, чтобы первоначальный план был оптимальным, необходимо выполнение следующих условий:
а) для каждой занятой клетки сумма потенциалов должна быть равна стоимости единицы перевозки, стоящей в этой клетке:
(1) + =cij при xij>0;
б) для каждой незанятой клетки сумма потенциалов должна быть меньше или равна стоимости единицы перевозки, стоящей в этой клетке:
(2) + cij при xij=0.
Если хотя бы одна незанятая клетка не удовлетворяет условию(2), то опорный план является неоптимальным и его можно улучшить, вводя в базис вектор, соответствующий клетке, для которой нарушается условие оптимальности (т.е. в клетку надо переместить некоторое количество груза). Таким образом, для проверки плана на оптимальность необходимо сначала построить систему потенциалов.
Рассмотрим алгоритм решения ТЗ методом потенциалов и проиллюстрируем его применение на примере:
Пример. Решить ТЗ, исходные данные которой заданы в таблице 1.
Табл. 1
ПН ПО |
B1 |
B2 |
B3 |
B4 |
Запасы ai |
A1 |
4
|
3
|
2 |
1 |
200 |
A2 |
2
|
3
|
5 |
6 |
300 |
A3 |
6 |
7
|
9 |
12 |
500 |
Заявки bj |
200 |
200 |
300 |
400 |
10001100 |
Проверка выполнения необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводится фиктивный поставщик или потребитель с недостающими запасами или запросами и нулевыми стоимостями перевозок.
Находим суммарные запасы поставщиков и суммарные запасы потребителей:
Задача с неправильным балансом. Вводим 4-го, фиктивного поставщика с запасами а4=1100-1000=100 и нулевыми стоимостями перевозок единиц груза (см. табл. 2).
Построение первоначального опорного плана (методом минимальной стоимости или другим методом), проверка правильности его построения по количеству занятых клеток (их должно быть m+n-1). Убедиться в линейной зависимости векторов условий (используя метод вычеркивания).
Находим первоначальный опорный план методом минимальной стоимости (см. табл. 2). Полученное решение Х1 имеет 4+4-1=7 базисных переменных.
Табл. 2
-
ПН
ПО
B1
B2
B3
B4
Запасы
ai
A1
4
-
3
-
2
-
1
200
200
A2
2
200
3
100
5
-
6
-
300
A3
6
-
7
100
9
300
12
100
500
Aф
0
-
0
-
0
-
0
100
100
Заявки
bj
200
200
300
400
1100=1100
Вычисляем значение целевой функции на этом опорном плане:
Z(X)=1*200+2*200+3*100+7*100+9*300+12*100+0*100=5300.
Построение системы потенциалов. Группа равенств (1) используется как система уравнений для нахождения потенциалов. Данная система уравнений имеет m+n неизвестных Ui, I=1,2,…,m и Vj, j=1,2,…,n. Число уравнений системы и число отличных от нуля компонент невырожденного опорного плана равно m+n-1, т.е. m+n-1 занятых клеток. Уравнений на одно меньше, чем неизвестных, поэтому система является неопределенной и одному неизвестному (обычно U1) придают нулевое значение. После этого остальные потенциалы определяются однозначно из системы.
В случае вырожденного опорного плана, т.е. когда занятых клеток меньше m+n-1, то остаются неопределенные потенциалы. Для устранения вырожденности дополняют количество занятых клеток до m+n-1, вводя нулевые перевозки. Клетки, в которые введены нулевые перевозки, называются фиктивно занятыми. Причем, т.к. задача решается на минимизацию линейной функции, целесообразно сделать фиктивно занятой ту клетку, в которой стоит наименьшая стоимость.
Значения потенциалов записываем рядом с запасами или запросами соответствующих поставщиков и потребителей. Система уравнений для нахождения потенциалов достаточно проста, обычно ее решают устно. Любой неизвестный потенциал, соответствующий занятой клетке, равен находящейся в этой клетке стоимости минус известный потенциал, соответствующий этой же клетке.
Проверяем правильность построения системы. Для этого просматриваем занятые клетки строк и для каждой из них определяем сумму потенциалов. Если для всех занятых клеток выполняется (1), то система построена правильно, в противном слу-чае ее надо построить заново или изменить так, чтобы условие (1) выполнялось.
В нашем примере записываем систему уравнений для нахождения потенциалов и решаем ее:
U1+V4=1,
U2+V1=2,
U2+V2=3,
U3+V2=7,
U3+V3=9,
U3+V4=12,
U4+V4=0.
Пусть U3=0, тогда V2=7- U3=7,
V3=9- U3=9, V4=12- U3=12,
U1=1-V4=-11, U4=0-V4=-12,
U2=3-V2=-4, V1=2- U2=6.
Табл. 3
-
V1=6
V2=7
V3=9
V4=12
U1=-11
4
3
2
1
200
U2=-4
2
200
-
3100
5
0
+ 6
2
U 3=0
6
0
+ 7
1 00
9
300
- 12
100
U4=-12
0
0
0
0
100
Проверка выполнения условия оптимальности для свободных клеток с помощью группы неравенств (2)
+
cij
при
xij=0.
Для чего просматриваем строки и для
каждой незанятой клетки проверяем
выполнение условия (2), т.е. суммируем
потенциалы, на пересечениях которых
стоит незанятая клетка, сумму сравниваем
со стоимостью, стоящей в ней.
Условие оптимальности: если для всех незанятых клеток Ui+Vjcij, то план оптимальный, если для некоторых клеток Ui+Vj>cij, то план неоптимальный, необходимо перейти к новому опорному плану, на котором значение целевой функции будет меньше.
Для каждой свободной клетки, в которой не выполняется условие оптимальности, находим величину разности ij=(Ui+Vj)-Сij>0 и записываем ее значение в левый нижний угол этой же клетки. Числа ij называются оценками для свободных клеток таблицы (векторов условий) ТЗ.
Тогда условие оптимальности можно перефразировать: опорный план является оптимальным, если для всех клеток таблицы (векторов условий) оценки неположительные ij0.
Для нашего примера найдены положительные оценки 23=0, 24=2, 31=0. Начальной опорное решение не является оптимальным, т.к. имеется положительная оценка 24=2. См. табл. 3.
Выбор клетки, в которую необходимо послать перевозку.
ТЗ решается на минимум линейной функции, поэтому алгоритм ее решения также следует общим принципам алгоритма симплекс-метода решения задач на минимум.
Если
отождествлять занятые клетки с векторами,
составляющими базис, а свободные – с
остальными векторами системы ограничений,
то в ОЗЛП в базис включается тот вектор,
которому соответствует максимальная
оценка целевой функции. В ТЗ загрузке
подлежит в первую очередь клетка,
например (l,k),
которой соответствует наибольшая
положительная оценка lk=
{ij}=
[(Ui+Vj)-Сij].
Выбираем клетку, в которую пошлем перевозку {24=2}=24.
Построение цикла и определение величины перераспределения груза.
Для определения количества единиц груза, подлежащих перераспределению, отмечаем знаком «+» свободную клетку, которую надо загрузить. Это означает, что клетка присоединяется к занятым клеткам. В таблице занятых клеток стало m+n, поэтому появляется цикл, все вершины которого, за исключением клетки, отмеченной знаком «+», находятся в занятых клеток, причем этот цикл единственный. Стрелками будем показывать направление обхода цикла. Отыскиваем цикл и, начиная движение от клетки, помеченной знаком «+», поочередно проставляем знаки «-» и «+».
Затем
находим 0=
{xij}
, где xij
– перевозки, стоящие в вершинах цикла,
отмеченных знаком «-». Величина 0
определяет,
сколько единиц груза можно перераспределить
по найденному циклу. Значение 0
записываем в
свободную клетку со знаком «+». Двигаясь
по циклу, вычитаем 0
из объемов
перевозок в клетках со знаком «-», и
прибавляем к объемам перевозок в клетках
со знаком «+». Если 0
соответствуют
несколько минимальных перевозок, то
при вычитании оставляем в соответствующих
клетках нулевые перевозки в таком
количестве, чтобы во вновь полученном
опорном плане занятых клеток было m+n-1.
Отмечаем «+» клетку (2,4) и для нее строим цикл, присоединяя ее к занятым клеткам. Применяя метод вычеркивания, находим цикл (2,4), (3,4), (3,2), (2,2).
Начиная с клетки (2,4) с «+», поочередно в вершинах расставляем знаки. Определим величину 0 , перераспределяемую по циклу, она равна значению наименьшей из перевозок в клетках со знаком «-»:0=100.
6. В результате перераспределения 0 получен новый опорный невырожденный план, который снова подлежит проверке на оптимальность. Для проверки на оптимальность нового плана вновь строим систему потенциалов и проверяем выполнение условия оптимальности для каждой незанятой клетки.
Если полученный план снова окажется неоптимальным, то следует выполнить вычисления, приведенные в п. 5. Процесс повторяется до тех пор, пока все незанятые клетки не будут удовлетворять условию + cij.
В нашем примере полученный план оказался неоптимальным, следует выполнить вычисления, приведенные в п. 5.
