карантин 1
.docxГУАП
КАФЕДРА № 41
ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ
ПРЕПОДАВАТЕЛЬ
старший преподаватель |
|
|
|
Н.Н. Григорьева |
должность, уч. степень, звание |
|
подпись, дата |
|
инициалы, фамилия |
ОТЧЕТ ОБ ИНДИВУДУАЛЬНОЙ РАБОТЕ |
Решение задач целочисленного программирования |
по курсу: Исследование операций |
|
|
РАБОТУ ВЫПОЛНИЛА
СТУДЕНТКА ГР. № |
4716 |
|
|
|
С.А. Янышева |
|
|
|
подпись, дата |
|
инициалы, фамилия |
Санкт-Петербург
2020
Оглавление
Решение задач целочисленного программирования 1
по курсу: Исследование операций 1
1. ЦЕЛЬ РАБОТЫ 3
2. ВАРИАНТ ЗАДАНИЯ 3
3. ХОД РАБОТЫ 3
ВЫВОД 8
1. ЦЕЛЬ РАБОТЫ 3
2. ВАРИАНТ ЗАДАНИЯ 3
3. ХОД РАБОТЫ 3
ВЫВОД 8
ЦЕЛЬ РАБОТЫ
Целью данной работы является получение навыка решения задач целочисленного программирования методом ветвей и границ с использованием симплекс-метода или графически.
ВАРИАНТ ЗАДАНИЯ
Вариант 1.
x 1+2x2 ≤ 11
2x1–x2 ≥ 5
x1+3x2 ≥ 14
F = x1+3x2 → max
Х ОД РАБОТЫ
Блок-схема алгоритма решения задачи ЛЦП
Аналитическое решение задачи
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами. Результат работы представлен на рисунке 1.
Рисунок 1 – Область допустимых значений
Рассмотрим целевую функцию задачи F = x1+3x2 → max. Построим прямую, отвечающую значению функции F = x1+3x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией (рисунок 2).
Прямая F = const пересекает область в точке пересечения прямых x1+2x2=11 и 2x1-x2=5, то ее координаты удовлетворяют этим уравнениям.
Рисунок 2 – Построение целевой функции
x 1+2x2 = 11
2x1–x2 = 5
x 1 = 4.2
x2 = 3.4
F = 1*4.2 + 3*3.4 = 14.4
Оптимальное значение переменной x1=4.2 оказалось нецелочисленным. Разбиваем задачу на две подзадачи 1 и 2.
Добавляется условие х1 ≥ 5, результат продемонстрирован на рисунке 3.
Рисунок 3 – Добавление нового условия
Решим систему уравнений:
x 1+2x2≤11
2x1-x2≥5
x1+3x2≥14
x1≥5
x1 ≥ 0
x2 ≥ 0
x 1+2x2=11
x1+3x2=14
x 1 = 5
x2 = 3
Откуда найдем максимальное значение целевой функции:
F = 1*5 + 3*3 = 14
Решение задачи получилось целочисленным, запомним его.
Добавляется условие х1 ≤ 4, результат продемонстрирован на рисунке 4.
Рисунок 4 – Добавление нового условия
Задача не имеет допустимых решений. ОДР представляет собой пустое множество
Оптимальное значение переменной x2=3.4 оказалось нецелочисленным. Разбиваем задачу на две подзадачи 1 и 2.
Добавляется условие х2 ≥ 4, результат продемонстрирован на рисунке 5.
Рисунок 5 – Добавление нового условия
Задача не имеет допустимых решений. ОДР представляет собой пустое множество.
Добавляется условие х2 ≤ 3, результат продемонстрирован на рисунке 6.
Рисунок 6 – Добавление нового условия
x 1+2x2≤11
2x1-x2≥5
x1+3x2≥14
x2≤3
x1 ≥ 0
x2 ≥ 0
x 1+2x2=11
x1+3x2=14
x 1 = 5
x2 = 3
Откуда найдем максимальное значение целевой функции:
F = 1*5 + 3*3 = 14
Решение задачи получилось целочисленным, запомним его.
В ходе решения задачи мы получили 2 одинаковых решения: x1 = 5, x2 = 3, F = 14.
Проверка решения в excel
Был создан файл excel с условиями и целевой функцией., В строке C3 формула =СУММПРОИЗВ(A2:B2;A3:B3) (сумма значений произведения соответствующих ячеек), в строке C4 формула =СУММПРОИЗВ(A2:B2;A4:B4) и в строке C5 формула =СУММПРОИЗВ(A2:B2;A5:B5). В строке целевой функции написана формула: =СУММПРОИЗВ(A2:B2;A7:B7) Для решения данной задачи был использован метод «Поиск решений». Все данные были введены и представлены на рисунке 7. Далее был произведен поиск решения, появившееся окно на рисунке 8 информирует о том, что решение было найдено, оно также представлено на рисунке 8. В желтых ячейках представлено максимально возможное значение решения данной задачи.
Рисунок 7 – Параметры поиска решения
Рисунок 8 – Результаты поиска решения
ВЫВОД
Был получен навык решения задач целочисленного программирования методом ветвей и границ с использованием симплекс-метода или графически. Решение было проверено c помощью Excel. Результаты решений каждым методом получились одинаковыми, следовательно, все подсчитано правильно.