- •Введение
- •Тема 1: задача линейного программирования (злп). Системы линейных неравенств. Графический метод решения злп для двумерного случая. Постановка задачи линейного программирования (злп).
- •Решение
- •Исходные данные задачи
- •Характеристики вариантов раскроя отрезов ткани по 10
- •Решение
- •Содержательную
- •Системы линейных неравенств.
- •Графический метод.
- •Алгоритм решения злп графическим методом:
- •Тема 2: симплексный метод.
- •Алгоритм симплексного метода:
- •Заполняем симплекс-таблицу второго шага:
- •Тема 3. Транспортная задача.
- •Нахождение исходного опорного решения (правило «северо-западного угла»)
- •Нахождение исходного опорного решения (метод минимального тарифа)
- •Проверка найденного опорного решения на оптимальность
- •Тема 4. Дискретное программирование.
- •Метод Гомори.
- •Задача о назначениях (зн).
- •Алгоритм решения задачи о назначениях.
- •Тема 5. Нелинейное программирование
- •Дробно-линейное программирование.
- •Метод множителей Лагранжа
- •Тема 6. Динамическое программирование.
- •Нахождение рациональных затрат при строительстве трубопроводов и транспортных артерий.
- •Применение метода функциональных уравнений в определении оптимальных сроков замены оборудования
- •Оптимальное распределение ресурсов.
- •Тема 7. Управление запасами. Модель Уилсона
- •Формулы модели Уилсона
- •Модель планирования экономичного размера партии
- •Формулы модели экономичного размера партии
- •Модель управления запасами, учитывающая скидки
- •Тема 8. Сетевые модели
- •Общие рекомендации
- •Задания для самостоятельной работы
- •1. Одноиндексные задачи линейного программирования
- •2. Графический метод решения одноиндексных задач
- •Стоимость транспортировки бобов, руб./т
- •4. Построение сетевых моделей
- •5. Управление запасами
- •Лабораторная работа №1 “решение задач линейного программирования с использованием Microsoft Excel”
- •Запуск задачи на решение
- •Лабораторная работа №2 (часть I) “одноиндексные задачи линейного программирования”
- •Лабораторная работа №2 (часть II) “анализ чувствительности одноиндексных задач линейного программирования”
- •Лабораторная работа №3 “двухиндексные задачи линейного программирования. Стандартная транспортная задача”
- •Постановка задачи
- •Лабораторная работа №4 “двухиндексные задачи линейного программирования. Задача о назначениях”
- •Лабораторная работа №5 “двухиндексные задачи линейного программирования. Организация оптимальной системы снабжения”
- •Лабораторная работа №6 “двухиндексные задачи лп. Оптимальное распределение производственных мощностей”
- •Лабораторная работа №7. Построение и расчет моделей сетевого планирования и управления
- •Лабораторная работа №8. Построение и расчет моделей управления запасами
- •Вариант 1
- •Вариант 2
- •Вариант 3
- •Вариант 4
- •Вариант 5
- •Вариант 6
- •Вариант 7
- •Лабораторная работа №9. Построение и расчет моделей динамического программирования
- •Значения коэффициентов условия задачи
- •Значения коэффициентов условия задачи
- •Список литературы
Проверка найденного опорного решения на оптимальность
Получив исходно опорное решение, переходят к построению опорных решений, улучшающих друг друга. Для этого применим метод потенциалов по следующему критерию: если опорное решение ТЗ является оптимальным, то ему соответствует система m+n действительных чисел и , удовлетворяющих условиям:
+ = - для занятых клеток,
+ - 0 – для свободных клеток.
Числа и называются потенциалами. В распределительную таблицу добавляют строку столбец . Потенциалы и находят из равенства + = , справедливого для занятых клеток. Только одному из потенциалов дается произвольное значение, например , тогда остальные потенциалы определяются однозначно. Так, если известен потенциал , то = - ; если известен потенциал , то = - .
Обозначим = + - . Эту оценку называют оценкой свободных клеток.
Если , то опорное решение является оптимальным. Если хотя бы одна из оценок , то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому.
Наличие положительной оценки свободной клетки при проверке опорного решения на оптимальность свидетельствует о том, что полученное решение не оптимально и для уменьшения значения целевой функции надо перейти к другому опорному решению. При этом надо перераспределить грузы, перемещая их из занятых клеток в свободные. Свободная клетка становится занятой, а одна из занятых клеток – свободной.
Для свободной клетки с строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак “+”, затем поочередно проставляют знаки “-” и “+”. У вершин со знаком “-” выбирают минимальный груз; его прибавляют к грузам, стоящим у вершин со знаком “+”, и отнимают от грузов у вершин со знаком “-”.
В результате перераспределения получают новое опорное решение. Это решение проверяют на оптимальность, и т.д. до тех пор, пока не получат оптимальное решение.
Пример.
|
1 |
2 |
3 |
|
||||
140 |
300 |
160 |
||||||
1 |
90 |
|
2 |
|
5 |
|
2 |
0 |
90 |
0 |
0 |
||||||
2 |
400 |
|
4 |
|
1 |
|
5 |
-2 |
0 |
300 |
100 |
||||||
3 |
110 |
|
3 |
|
6 |
|
8 |
1 |
50 |
0 |
|
60 |
|||||
|
2 |
3 |
7 |
|
(3;1): ;
(3;3): ;
(2;3): ;
(2;2): ;
= + - ;
= + - ;
= + - ;
= + - .
Опорное решение не является оптимальным. у.е. Улучшим его. Строим цикл для клетки (1;3), :
9
-
+
+
-
50 60
У вершин со знаком “-” выбираем минимальный груз 60; его прибавляем к грузам у вершин со знаком “+” – 0 и 50 и отнимаем от грузов у вершин с “-” – 90 и 60. Получаем новый цикл:
3
+
-
-
+
110 0
Новое опорное решение . у.е. Проверим полученное решение на оптимальность. Найдем потенциалы занятых (1;1), (1;3), (2;3), (2;2), (3;1) и оценки свободных клеток:
|
1 |
2 |
3 |
|
||||
140 |
300 |
160 |
||||||
1 |
90 |
|
2 |
|
5 |
|
2 |
0 |
30 |
0 |
60 |
||||||
2 |
400 |
|
4 |
|
1 |
|
5 |
3 |
0 |
300 |
100 |
||||||
3 |
110 |
|
3 |
|
6 |
|
8 |
1 |
110 |
0 |
|
0 |
|||||
|
2 |
-2 |
2 |
|
= + - ;
= + - ;
= + - .
Построим цикл для клети с
положительной оценкой =1:
3
-
+
+
-
0 100
0
+
-
-
+
30 70
Новое опорное решение . у.е.
|
1 |
2 |
3 |
|
||||
140 |
300 |
160 |
||||||
1 |
90 |
|
2 |
|
5 |
|
2 |
0 |
0 |
0 |
90 |
||||||
2 |
400 |
|
4 |
|
1 |
|
5 |
3 |
0 |
300 |
70 |
||||||
3 |
110 |
|
3 |
|
6 |
|
8 |
2 |
110 |
0 |
|
0 |
|||||
|
1 |
-2 |
2 |
|
Все оценки , следовательно , у.е.