- •Глава 1. Линейное программирование 3
- •Глава 2. Транспортная задача линейного программирования (тз) 68
- •Глава 3. Динамическое программирование 98
- •Глава 1. Линейное программирование
- •1.1. Математическая модель задачи линейного программирования
- •1.2. Формы записи задач линейного программирования
- •Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой
- •1.3. Геометрическая интерпретация и графический метод решения задач линейного программирования с двумя переменными
- •Алгоритм графического метода решения злп с двумя переменными
- •1.4. Графический метод решения задач линейного программирования сnпеременными
- •1.5. Симплексный метод решения задач линейного программирования
- •Алгоритм решения злп симплексным методом
- •Нахождение начального опорного плана злп ( )
- •Нахождение начального опорного плана злп методом искусственного базиса
- •Нахождение начального опорного плана злп методом Жордановых исключений
- •Шаг Жордановых исключений осуществляется по следующим правилам:
- •Исследование на оптимальность опорного плана при решении злп на
- •Переход к новому опорному плану
- •1.6. Двойственные задачи линейного программирования
- •Правила построения двойственной задачи.
- •Глава 2. Транспортная задача линейного программирования (тз)
- •2.1. Математическая модель транспортной задачи
- •Закрытая и открытая модели транспортной задачи
- •2.2. Решение транспортной задачи
- •Алгоритм решения транспортной задачи
- •Нахождение начального опорного плана методом «минимального элемента»
- •Нахождение начального опорного плана методом «северо-западного угла»
- •Нахождение начального опорного плана методом Фогеля
- •Проверка на оптимальность невырожденного опорного плана методом потенциалов
- •Переход к новому опорному плану
- •Цикл пересчета
- •Глава 3. Динамическое программирование
- •3.1. Задача оптимального распределения ресурсов
- •I этап. Условная оптимизация.
- •II этап. Безусловная оптимизация.
- •3.2. Задача об оптимальной стратегии замены оборудования
- •I этап. Условная оптимизация.
- •II этап. Безусловная оптимизация.
- •Список использованной литературы
I этап. Условная оптимизация.
1-й шаг. Находим максимальный ежегодный прирост выпуска продукции первого предприятия при выделении ему x млн. руб. по формуле (3.2), которая эквивалентна формуле . Значения функциии условно-оптимальные значения объема выделенных средств первому предприятиюзапишем в табл. 3.2.
Таблица 3.2
x |
|
|
0 |
0 |
0 |
10 |
3 |
10 |
20 |
6 |
20 |
30 |
9 |
30 |
40 |
14 |
40 |
50 |
17 |
50 |
2-й шаг. Находим максимальный ежегодный прирост выпуска продукции первого и второго предприятий вместе при выделении им x млн. руб. по формуле (3.3), т.е.
Вычисление функции произведем в таблице (табл. 3.3), последние два столбца которой – это значения функциии условно-оптимальные значения объема выделенных средств второму предприятию.
Таблица 3.3
x |
|
|
| |||||
0 |
10 |
20 |
30 |
40 |
50 | |||
10 |
0+3 |
5+0 |
– |
– |
– |
– |
5 |
10 |
20 |
0+6 |
5+3 |
8+0 |
– |
– |
– |
8 |
10, 20 |
30 |
0+9 |
5+6 |
8+3 |
12+0 |
– |
– |
12 |
30 |
40 |
0+14 |
5+9 |
8+6 |
12+3 |
15+0 |
– |
15 |
30, 40 |
50 |
0+17 |
5+14 |
8+9 |
12+6 |
15+3 |
18+0 |
19 |
10 |
3-й шаг. Находим максимальный ежегодный прирост выпуска продукции первого, второго и третьего предприятий вместе при выделении им x млн. руб. по формуле (3.3), т.е.
Вычисление функции произведем в таблице (табл. 3.4), последние два столбца которой – это значения функциии условно-оптимальные значения объема выделенных средств третьему предприятию.
Таблица 3.4
x |
|
|
| |||||
0 |
10 |
20 |
30 |
40 |
50 | |||
10 |
0+5 |
2+0 |
– |
– |
– |
– |
5 |
0 |
20 |
0+8 |
2+5 |
5+0 |
– |
– |
– |
8 |
0 |
30 |
0+12 |
2+8 |
5+5 |
11+0 |
– |
– |
12 |
0 |
40 |
0+15 |
2+12 |
5+8 |
11+5 |
14+0 |
– |
16 |
30 |
50 |
0+19 |
2+15 |
5+12 |
11+8 |
14+5 |
18+0 |
19 |
0, 30, 40 |
4-й шаг. Находим максимальный ежегодный прирост выпуска продукции четырех предприятий вместе при выделении им x млн. руб. по формуле (3.3), т.е.
Т.к. это последний шаг условной оптимизации и значения функции в дальнейших вычислениях не будут использоваться, то достаточно вычислить значение функции приx=50 (т.е. максимальный ежегодный прирост выпуска продукции четырех предприятий при выделении им 50 млн. руб.). Вычисление функции произведем в таблице (табл. 3.5), последние два столбца которой – это значение функциии условно-оптимальное значение объема выделенных средств четвертому предприятию.
Таблица 3.5
x |
|
|
| |||||
0 |
10 |
20 |
30 |
40 |
50 | |||
50 |
0+19 |
4+16 |
7+12 |
10+8 |
13+5 |
17+0 |
20 |
10 |
Итак, максимальный ежегодный прирост выпуска продукции четырех предприятий при выделении им 50 млн. руб. будет млн. руб., при этом четвертому предприятию нужно выделитьмлн. руб.