Математическое программирование
Задача 1
Для производства двух видов изделий А и В используется три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется 2 часа, оборудование второго типа – 1 час, оборудование третьего типа – 3 часа. Для производства единицы изделия В оборудование первого типа используется 2 часа, оборудование второго типа – 2 часа, оборудование третьего типа – 1 час.
На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 48 часа, оборудование второго типа – 38 часов, оборудование третьего типа – 54 часов.
Прибыль от реализации единицы готового изделия А составляет 2 денежные единицы, а изделия В – 3 денежные единицы.
Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации. Решить задачу симплекс-методом путем преобразования симплекс-таблиц. Дать геометрическое истолкование задачи, используя для этого ее формулировку с ограничениями – неравенствами.
Решение.
Данная задача является задачей линейного программирования. Под планом производства понимается: сколько изделий А и сколько изделий В надо выпустить, чтобы прибыль была максимальна.
Прибыль рассчитывается по формуле: />
Запишем математическую модель задачи:
/>
Решим данную задачу графически.
Для этого построим на плоскости /> области, описываемые ограничениями-неравенствами, и прямую />, которая называется целевой функцией.
Три записанных выше неравенства ограничивают на плоскости многоугольник, ограниченный слева и снизу координатными осями (т.к. искомое количество изделий положительно).
График целевой функции передвигается в направлении, обозначенном стрелкой (в направлении своего градиента), до тех пор, пока не достигнет граничной точки многоугольника – в нашем случае это точка – (10; 14). В этой точке целевая функция будет достигать максимума.
/>
/>
Решим эту задачу симплекс-методом. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам, введя дополнительные переменные />.
/>
Составляем симплекс-таблицу:
Базис
Cб
В
2
3
0
0
0
А1
А2
А3
А4
А5
А3
0
48
2
2
1
0
0
А4
0
38
1
2
0
1
0
А5
0
54
3
1
0
0
1
Fi— Ci
0
-2
-3
0
0
0
В графе Базис записываются вектора переменных, принимаемые за базисные. На первом этапе это – А3, А4, А5. Базисными будут переменные, каждая из которых входит только в одно уравнение системы, и нет такого уравнения, в которое не входила бы хотя бы одна из базисных переменных.
В следующий столбец /> записываются коэффициенты целевой функции, соответствующие каждой переменной. Столбец В – столбец свободных членов. Далее идут столбцы коэффициентов Аi при i –й переменной.
Под столбцом свободных членов записывается начальная оценка
/>
Остальные оценки записываются под столбцами соответствующих векторов /> .
/>
/>
Преобразуем симплекс-таблицу следующим образом:
Шаг 1: Проверяется критерий оптимальности, суть которого состоит в том, что все оценки должны быть неотрицательны. В нашем случае этот критерий не выполнен, поэтому переходим ко второму шагу.
Шаг 2: Для отрицательных оценок вычисляются величины:
/>
/>
/>
/>
Из этих элементов выбирается тот, для которого вычисленное произведение минимально, в нашем случае -57 минимально, поэтому в качестве разрешающего элемента выбирается второй элемент второго столбца – 2 (выделен в таблице).
Шаг 3: Вторая строка таблицы делится на 2
От элементов строки 1 отнимает соответствующие элементы строки 2, умноженные на 2.
От элементов строки 3 отнимает соответствующие элементы строки 2.
От элементов строки 4 отнимает соответствующие элементы строки 2, умноженные на -3.
Базис
Cб
В
2
3
0
0
0
А1
А2
А3
А4
А5
А3
0
10
1
0
1
-
0
А5
0
19
0,5
1
0
0,5
0
А2
3
35
2,5
0
0
-0,5
1
Fi— Ci
57
-0,5
0
0
1,5
0
Таким образом, новыми базисными переменными становятся А3, А5, А2.
Возвращаемся к шагу 1 и повторяем весь процесс.
Проверяется критерий оптимальности. Отрицательная оценка только одна – в столбце А1.
Вычисляем:
/>
Разрешающим элементом будет первый элемент первого столбца – 1.
Новыми базисными переменными становятся A5, A2, A1
От элементов строки 2 отнимает соответствующие элементы строки 1, умноженные на 0,5.
От элементов строки 3 отнимает соответствующие элементы строки 1, умноженные на 2,5.
От элементов строки 4 отнимает соответствующие элементы строки 1, умноженные на -0,5.
Базис
Cб
В
2
3
0
0
0
А1
А2
А3
А4
А5
А5
0
10
1
0
1
-1
0
А2
3
14
0
1
-0,5
1
0
А1
2
10
0
0
-2,5
2
1
Fi— Ci
62
0
0
1,5
1
0,5
Отрицательных оценок нет, то есть критерий оптимальности выполнен.
Таким образом, получается искомое значение целевой функции
F(10; 14; 0; 0; 10) = 62, т.е. возвращаясь к системе неравенств, получаем:
/>
Ответы, полученные различными методами, совпадают.
Ответ: хопт = ( 10, 14) Значение функции: F = 62
Задача 2
Имеются три пункта отправления А1, А2, А3однородного груза и пять пунктов В1, В2, В3, В4, В5его назначения. На пунктах А1, А2, А3находится груз в количествах 50, 30, 70 тонн. В пункты В1, В2, В3, В4, В5требуется доставить соответственно 20, 30, 50, 30, 20 тонн груза. Расстояния в сотнях километрах между пунктами отправления и назначения приведены в матрице D:
Пункты
отправления
Пункты назначения
В1
В2
В3
В4
В5
А1
9
5
1
1
9
А2
7
1
4
9
4
А3
5
3
4
9
9
Найти такой план перевозок, при котором общие затраты на перевозку грузов будут минимальными.
Указания: 1) считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое этот груз перевозится, т.е. для решения задачи достаточно минимизировать общий объем плана, выраженный в тонно-километрах;
2) для решения задачи использовать методы северо-западного угла и потенциалов.
Решение.
Составим математическую модель задачи:
Обозначим />— количество груза, перевезенного из пункта отправления i в пункт назначения j.
Получим следующие ограничения (т.к. весь груз должен быть вывезен, и все потребности удовлетворены полностью):
/>/>/>/>/>
/>/>/>
При этом должна быть минимизирована целевая функция
/>
Построим опорный план методом северо-западного угла:
Пункты
отправления
Пункты назначения
Запасы
В1
В2
В3
В4
В5
А1
9
20
5
30
1
1
9
50
А2
7
1
4
30
9
4
30
А3
5
3
4
20
9
30
9
20
70
Потребности
20
30
50
30
20
150
Принцип заполнения таблицы состоит в том, что, начиная с крайней левой верхней ячейки (принцип северо-западного угла), количество грузов вписывается в таблицу так, чтобы потребности полностью удовлетворялись или груз полностью вывозился.
Построим систему потенциалов. Ui— потенциалы, соответствующие поставщикам, Vi— потенциалы, соответствующие потребителям.
Полагаем U1=0, а далее Ui+ Vi= dijдля занятых клеток таблицы.
/>
/>
/>
/>
Пункты
отправления
Пункты назначения
Запасы
В1
В2
В3
В4
В5
V1=9
V2=5
V3=4
V4=9
V5=9
А1
U1=0
9
20
5
30
1
1
9
50
А2
U2=0
7
1
4
30
9
4
30
А3
U3=0
5
3
4
20
9
30
9
20
70
Потребности
20
30
50
30
20
150
Проверим критерий оптимальности: />для свободных клеток.
/>
/>
Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (1, 4). Перебросим в ячейку (1, 4) 20 единиц груза из ячейки (1, 1).
Пункты
отправления
Пункты назначения
Запасы
В1
В2
В3
В4
В5
V1=9
V2=5
V3=4
V4=9
V5=9
А1
U1=0
9
5
30
1
1
20
9
50
А2
U2=0
7
1
4
30
9
4
30
А3
U3=0
5
20
3
4
20
9
10
9
20
70
Потребности
20
30
50
30
20
150
Чтобы компенсировать недостаток в третьей строке, перебросим те же 20 единиц груза из ячейки (3, 4) в ячейку (3, 1).
Получили новую таблицу, для которой повторяем расчет потенциалов:
Полагаем U1=0, а далее Ui+ Vi= dijдля занятых клеток таблицы.
/>
/>
/>
/>
Пункты
отправления
Пункты назначения
Запасы
В1
В2
В3
В4
В5
V1=5
V2=5
V3=4
V4=1
V5=9
А1
U1=0
9
5
30
1
1
20
9
50
А2
U2=0
7
1
4
30
9
4
30
А3
U3=0
5
20
3
4
20
9
10
9
20
70
Потребности
20
30
50
30
20
150
Проверим критерий оптимальности: />для свободных клеток.
/>
/>
Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (2, 5). Перебросим в ячейку (2 ,5) 20 единиц груза из ячейки (1, 2).
Пункты
отправления
Пункты назначения
Запасы
В1
В2
В3
В4
В5
V1=5
V2=5
V3=4
V4=1
V5=9
А1
U1=0
9
5
10
1
20
1
20
9
50
А2
U2=0
7
1
4
10
9
4
20
30
А3
U3=0
5
20
3
20
4
20
9
10
9
70
Потребности
20
30
50
30
20
150
Получили новую таблицу, для которой повторяем расчет потенциалов:
Полагаем U1=0, а далее Ui+ Vi= dijдля занятых клеток таблицы.
/>
/>
/>
Пункты
отправления
Пункты назначения
Запасы
В1
В2
В3
В4
В5
V1=2
V2=5
V3=1
V4=1
V5=1
А1
U1=0
9
5
10
1
20
1
20
9
50
А2
U2=3
7
1
4
10
9
4
20
30
А3
U3=3
5
20
3
20
4
20
9
10
9
70
Потребности
20
30
50
30
20
150
Проверим критерий оптимальности: />для свободных клеток.
/>
/>
Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (2, 2). Перебросим в ячейку (2 ,2) 10 единиц груза из ячейки (1, 2).
Пункты
отправления
Пункты назначения
Запасы
В1
В2
В3
В4
В5
V1=2
V2=5
V3=1
V4=1
V5=1
А1
U1=0
9
5
1
20
1
30
9
50
А2
U2=3
7
1
10
4
9
4
20
30
А3
U3=3
5
20
3
20
4
30
9
9
70
Потребности
20
30
50
30
20
150
Получили новую таблицу, для которой повторяем расчет потенциалов:
Полагаем U1=0, а далее Ui+ Vi= dijдля занятых клеток таблицы.
/>
/>
/>
Пункты
отправления
Пункты назначения
Запасы
В1
В2
В3
В4
В5
V1=3
V2=1
V3=1
V4=1
V5=4
А1
U1=0
9
5
1
20
1
30
9
50
А2
U2=0
7
1
10
4
9
4
20
30
А3
U3=2
5
20
3
20
4
30
9
9
70
Потребности
20
30
50
30
20
150
Проверим критерий оптимальности: />для свободных клеток.
/>
/>
Критерий выполнен, значит, полученное решение оптимально.
Найдем минимальную стоимость перевозок.
/>
Ответ: />
Задача 3
Дана задача выпуклого программирования. Требуется:
1) найти решение графическим методом
2) написать функцию Лагранжа данной задачи и найти ее седловую точку, используя решение задачи, полученное графически.
/>
/>
Решение.
Графическое решение задачи следующее:
/>
Система неравенств определяет область, ограниченную двумя прямыми и координатными осями. График целевой функции представляет собой окружность переменного радиуса с центром в точке (5, 10). Значение целевой функции графически представляет собой квадрат радиуса этой окружности. Минимальным радиусом, удовлетворяющим системе ограничений, будет такой радиус, который обеспечивает касание окружности с границей области так, как это показано на рисунке.
Искомая точка определяется как решение системы уравнений
/>/>/>/>
Получили точку (3, 8), значение целевой функции в этой точке равно />
Запишем задачу в традиционном виде:
/>
/>
Функция />называется функцией Лагранжа, а переменные /> — коэффициентами Лагранжа.
Точка />называется седловой точкой функции Лагранжа, если для любых />выполняются неравенства:
/>
Если функции f, g дифференцируемы, то условия определяющие седловую точку (условия Куна-Таккера):
/>/>
/>/>
/>
В данном случае получаем:
/>
/>
/>
Подставим в эти выражения значения:
/>
/>
Получаем
/>
Седловая точка функции Лагранжа: />
Проверим условие cедловой точки:
/>
Условия выполнены, седловая точка/>.
Ответ: />
Задача 4
Для двух предприятий выделено 900 единиц денежных средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от х единиц, вложенных в первое предприятие равен />, а доход от у единиц, вложенных во второе предприятие равен />. Остаток средств к концу года составляет /> — для первого предприятия, /> — для второго предприятия. Решить задачу методом динамического программирования.
Решение.
Процесс распределения средств разобьем на 4 этапа – по соответствующим годам.
Обозначим /> — средства, которые распределяются на k–ом шаге как сумма средств по предприятиям.
Суммарный доход от обоих предприятий на k–ом шаге:
/>
Остаток средств от обоих предприятий на k–ом шаге:
/>
Обозначим /> — максимальный доход, полученный от распределения средств между двумя предприятиями с k-го шага до конца рассматриваемого периода.
Рекуррентные соотношения Беллмана для этих функций
/>
/>
Проведем оптимизацию, начиная с четвертого шага:
4-й шаг.
Оптимальный доход равен:
/>, т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при />.
3-й шаг.
/>
т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при />.
2-й шаг.
/>т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при />.
1-й шаг.
/>
т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при />.
Результаты оптимизации:
/>/>
/>/>
/>/>
/>/>
Определим количественное распределение средств по годам:
Так как />, />, получаем
/>
/>
/>
Представим распределение средств в виде таблицы:
предприятие
год
1
2
3
4
1
900
90
9
0,9
2
0
0
0
0
При таком распределении средств за 4 года будет получен доход, равный />
Ответ: />