Ім'я файлу: Вар 13 Цыбиков МПР ЛП КР.docx
Розширення: docx
Розмір: 172кб.
Дата: 31.05.2023
скачати
Пов'язані файли:
Задача о макс потоке.docx
Розширення: docx
Розмір: 172кб.
Дата: 31.05.2023
скачати
Пов'язані файли:
Задача о макс потоке.docx
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«Московский авиационный институт
(национальный исследовательский университет)»
Институт №1 «Авиационная техника»
Кафедра №107Б «Внешнее проектирование и эффективность авиационных комплексов»
Курсовая работа
по курсу «Модели принятия решений»,
раздел «Линейное программирование»
Выполнил:
Цыбиков Т.Т.
Проверил:
Топорова М.И.
Москва, 2022
СОДЕРЖАНИЕ
ВВЕДЕНИЕ 3
1Формулировка задачи 4
2Составление и анализ математической модели 5
3Методы решения задачи 7
3.1Симплекс-метод 7
3.1.1Алгоритм симплекс-метода 7
3.1.2Алгоритм спуска на область 9
3.2Алгоритм Гомори 9
4Подготовка исходных данных 10
5Решение задачи в Excel 11
6Разработка программы для решения ЗЛП симплекс‑методом. Решение задачи 13
6.1Реализация симплекс-метода 14
6.1.1Основной алгоритм 14
6.1.2Алгоритм спуска на область 18
6.2Метод Гомори 20
6.3Решение задачи 21
7Анализ на чувствительность 22
ЗАКЛЮЧЕНИЕ 24
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ 25
ВВЕДЕНИЕ
В данной работе требуется решить задачу, сводящуюся к задаче распределения ограниченных ресурсов в целях получения требуемой выгоды. Задача выдается в вербальной (словесной) постановке.
Для ее решения необходимо:
Составить математическую модель и провести ее анализ.
Определить методы решения задачи. Описать их.
Подготовить и проанализировать исходные данные задачи.
Решить задачу алгебраическим методом с использованием табличного процессора Excel.
Произвести контроль результатов ручным просчетом (в случае возможности применения графического метода, произвести контроль графически).
Проанализировать результат.
Провести анализ задачи на чувствительность к изменению исходных данных, указанному в задании. Для этого разработать программу решения ЗЛП симплекс-методом на любом алгоритмическом языке.
Формулировка задачи
Мебельная фабрика выпускает столы, стулья, платяные и книжные шкафы. При изготовлении этой продукции используется два типа досок. В таблице приведены нормативные затраты на единицу изделия (табл. 1).
Таблица №1 – Нормативные затраты на единицу изделия
| Производственный фактор | Затраты на единицу изделия | |||
| столы | стулья | шкафы платяные | шкафы книжные | |
| доски I типа, м | 5 | 1 | 12 | 15 |
| доски II типа, м | 3 | 2 | 6 | 5 |
| трудовые ресурсы, чел./ч | 7 | 5 | 10 | 12 |
Объемы наличных ресурсов каждого типа соответственно равны 1500, 1000, 3200. Прибыль от реализации единицы изделия – 60, 25, 140, 160 р. соответственно.
Существуют следующие условия: столов необходимо произвести не менее 40, стульев – не менее 120, платяных шкафов – не менее 20, книжных шкафов – не более 20.
Определить ассортимент продукции, максимизирующей прибыль фабрики в данных условиях. Запас какого типа досок следует изменить в первую очередь и насколько для увеличения прибыли?
Составление и анализ математической модели
Обозначим за (xj) искомое количество изделий j‑го типа (ассортимент). Количество изделий должно быть неотрицательным и целым (неявные ограничения). Также даны ограничения на ассортимент.
Таблица №2 – Ассортимент
| Изделие |  | Удельная прибыль | Огр-я на ассортимент | Неявные огр-я |
| стол |  | 60 |  |    |
| стул |  | 25 |  | |
| шкаф платяной |  | 140 |  | |
| шкаф книжный |  | 160 |  |
Задачей установлена целевая функция – прибыль – которая подлежит максимизации. Также дана удельная прибыль от реализации одного изделия j‑го типа (таб. 1). Тогда общая прибыль – это сумма произведений удельных прибылей и количеств изделий.
(0)Таблица №3 – Ограниченные ресурсы
| Ресурс | Затраты на единицу изделия | Количество ресурса | |||
| столы | стулья | шкафы платяные | шкафы книжные | ||
| доски I типа, м | 5 | 1 | 12 | 15 | 1500 |
| доски II типа, м | 3 | 2 | 6 | 5 | 1000 |
| труд, чел./ч | 7 | 5 | 10 | 12 | 3200 |
В решении задачи должны быть учтены ограничения на расход ресурсов.
Итак, запишем математическую модель полностью:
Максимизировать
(0)при ограничениях
.Существует графический метод решения задач линейного программирования. Однако его использование при решении данной задачи невозможно: при приведении математической модели к каноническому виду мы обнаружим, что число свободных переменных n – m = 4, а в таком случае графический метод уже не пригоден [1, с. 59]. Поэтому будет рассмотрен наиболее универсальный вычислительный метод – симплекс‑метод. Задача также относится к классу задач целочисленного программирования. Будет рассмотрен метод Гомори для решения таких задач.
Симплекс-метод
Оптимальному решению всегда соответствует одна из угловых точек пространства решений. В симплекс-методе реализуется алгоритм, при котором, начиная с некоторой исходной допустимой угловой точки, осуществляются последовательные переходы от одной допустимой угловой точки к другой до тех пор, пока не будет найдена точка, соответствующая оптимальному решению [2, с. 74].
Алгоритм симплекс-метода
1. Привести задачу к каноническому виду.
2. Найти начальное базисное решение.
2.1. Выделить свободные и базисные переменные;
2.2. Переразрешить систему относительно выбранного базиса (метод Гаусса-Жордана);
2.3. Свободные переменные приравнять к нулю. Найти базисные переменные и значение целевой функции в этой точке.
Все элементы решения записать в виде начальной симплекс-таблицы.
3. Проверка начального базисного решения на опорность.
Если условие неотрицательности не выполняется, решение является базисным, но не опорным: применить алгоритм спуска на область и продолжить.
4. Проверка полученного базисного опорного решения на оптимальность.
(8)
(9)Критерий оптимальности
Если среди оценок Dj в задаче максимизации нет отрицательных (в задаче минимизации – положительных), то полученное базисное решение оптимально – задача решена.
5. Определить включаемую в базис переменную.
Включаемой в базис переменной в задаче максимизации соответствует наибольшая по модулю отрицательная оценка (в задаче минимизации – наибольшая положительная). Включаемая в базис переменная соответствует разрешающему столбцу.
6. Определить исключаемую из базиса переменную (условие допустимости).
Для определения исключаемой из базиса переменной в разрешающем столбце среди коэффициентов aij выбрать положительные элементы и найти отношение к ним правых частей ограничений.
(10)S – индекс разрешающего столбца.
Выбрать наименьшее положительное Θ. Этому Θ соответствует исключаемая из базиса переменная и разрешающая строка.
7. Переразрешить задачу относительно измененного базиса и вернуться к п. 4.
Алгоритм спуска на область
1. Выбрать среди правых частей ограничений минимальное отрицательное. В соответствующей ему строке также выбрать минимальный отрицательный элемент. Принять этот столбец за разрешающий. Если таких элементов нет, решения ЗЛП не существует.
2. В разрешающем столбце выбрать элементы, имеющие одинаковый знак с соответствующей правой частью, и найти отношение к ним соответствующих правых частей (Θ). Из этих отношений выбрать минимальное – соответствующая строка будет разрешающей.
3. Переразрешить систему относительно измененного базиса.
4. Повторять до тех пор, пока правые части не станут неотрицательными.
Алгоритм Гомори
Применив симплекс-метод, мы получим некое решение задачи линейного программирования. Оно может содержать нецелые числа. Чтобы получить полностью целочисленное решение, можно применить алгоритм Гомори.
1. Решить задачу симплекс-методом.
2. В столбце правых частей выбрать строку, где правая часть имеет наибольшую дробную часть. На основе этой строки ввести в систему новое ограничение:
(11)3. Переразрешить систему. Повторять до получения целочисленного решения.
Подготовка исходных данных
Перед применением симплекс-метода необходимо привести полученную математическую модель к каноническому виду ЗЛП.
Чтобы знаки всех ограничений совпадали, умножим обе части ограничений (4) – (6) на (-1).
Преобразуем неравенства в равенства путём введения дополнительных переменных:
Таким образом получен базис – переменные (x5) – (x7). Необходимо учесть, что правые части ограничений (4) – (6) отрицательны, следовательно, начальное базисное решение не является опорным.
Решение задачи в Excel
Рисунок №1 – Исходная таблица
Рисунок №2 – Интерфейс решателя ЗЛП
Ответ: оптимальный план – 42 стула, 186 столов, 67 шкафов платяных, 20 шкафов книжных. Прибыль составит 19750 рублей.
Разработка программы для решения ЗЛП симплекс‑методом. Решение задачи
В рамках курсовой работы была разработана программа для решения задач линейного программирования симплекс-методом на языке программирования Python.
В программе реализованы:
непосредственно симплекс-метод;
метод Гомори для целочисленного программирования;
анализ на чувствительность.
Программа решает задачу максимизации, приведенную к каноническому виду, с найденным вручную начальным базисом.
c=[60, 25, 140, 160, 0, 0, 0, 0, 0, 0, 0],
a=[
[5, 1, 12, 15, 1, 0, 0, 0, 0, 0, 0],
[3, 2, 6, 5, 0, 1, 0, 0, 0, 0, 0],
[7, 5, 10, 12, 0, 0, 1, 0, 0, 0, 0],
[-1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
[0, -1, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, -1, 0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1]
],
b=[1500, 1000, 3200, -40, 120, -20, 20],
basis=[5, 6, 7, 8, 9, 10, 11]
Реализация симплекс-метода
Основной алгоритм
Таблица №3 – Структура модуля simplex_basic
| Функция | Описание |
| simplex_basic | Осуществление алгоритма |
| simplex_iterate | Проведение итерации симплекс-метода |
| simplex_is_optimal | Проверка решения на оптимальность путём подсчета оценок Dj |
| simplex_pivot_j | Определение включаемой в базис переменной. Возвращает индекс разрешающего столбца |
| simplex_pivot_i | Определение исключаемой из базиса переменной (условие допустимости). Возвращает индекс разрешающей строки |
| simplex_gauss | Процедура однократного замещения по методу Гаусса-Жордана |
| Алгоритм спуска на область | |
| simplex_bfs_pivot_j | Определение включаемой в базис переменной. Возвращает индекс разрешающего столбца |
| simplex_bfs_pivot_i | Определение исключаемой из базиса переменной (условие допустимости). Возвращает индекс разрешающей строки |
Функция simplex_basic
while not simplex_is_optimal():
simplex_iterate()
До тех пор, пока решение не оптимально, проводить итерации симплекс-метода.
Функция simplex_iterate
# Поиск разрешающих столбца и строки
# Если в столбце B есть отрицательные эл-ты
if has_negatives(s.b):
# базисное решение не опорно -
# поиск по алгоритму спуска на область
p_j = simplex_bfs_pivot_j(s)
p_i = simplex_bfs_pivot_i(s, p_j)
else:
# поиск по стандартной процедуре
p_j = simplex_pivot_j(s)
p_i = simplex_pivot_i(s, p_j)
Фрагмент №1
Если базисное решение не опорно, то производится поиск разрешающих столбца и строки по алгоритму спуска на область.
Если базисное решение опорно, то поиск производится по стандартной процедуре.
# Включение в базис переменной на место исключаемой
s.basis[p_i] = p_j + 1
simplex_gauss(s, p_i, p_j) # Метод Гаусса-Жордана
Фрагмент №2
В итоге, индекс разрешающего столбца соответствует индексу включаемой переменной, а индекс разрешающей строки – индексу исключаемой. Исходя из этих соображений изменяем базис и проводим процедуру однократного замещения во фрагменте (2).
Функция simplex_pivot_j
d_min = 0
d_min_j = None
for j in range(s.n):
if s.d[j] < d_min:
d_min = s.d[j]
d_min_j = j
return d_min_j
Включаемой в базис переменной (разрешающему столбцу) в задаче максимизации соответствует наименьшая по модулю отрицательная оценка Dj. Реализован классический алгоритм поиска минимума в массиве.
Функция simplex_pivot_i
theta_min = 100_000_000
theta_min_i = None
for i in range(s.m):
# Выбрать неотрицательные эл-ты разр. столбца
if s.a[i][p_j] > 0:
# Подсчитать отношение
s.theta[i] = s.b[i] / s.a[i][p_j]
if s.theta[i] < theta_min:
theta_min = s.theta[i]
theta_min_i = i
else:
s.theta[i] = None
return theta_min_i
Исключаемой из базиса переменной (разрешающей строке) соответствует наименьшее положительное отношение Θ. Для каждого неотрицательного элемента разрешающего столбца подсчитывается отношение соответствующей правой части к нему. Реализован классический алгоритм поиска минимума в массиве.
Функция simplex_gauss
p_e = s.a[p_i][p_j] # Разрешающий элемент
# Формирование разрешающей строки
for j in range(s.n):
s.a[p_i][j] /= p_e
s.b[p_i] /= p_e
# Формирование прочих строк
for i in range(s.m):
if i == p_i:
continue
p_a = s.a[i][p_j]
for j in range(s.n):
s.a[i][j] -= p_a * s.a[p_i][j]
s.b[i] -= p_a * s.b[p_i]
Формирование разрешающей строки [2, с. 84]
Новая разрешающая строка = Предыдущая разрешающая строка/ Разрешающий элемент
Формирование прочих строк [2, с. 84]
Новая строка = Предыдущая строка – (Коэффициент разрешающего столбца предыдущей строки) × (Новая разрешающая строка)
Функция simplex_is_optimal
for j in range(s.n):
z = 0
for i in range(s.m):
z += s.a[i][j] * s.c[s.basis[i] - 1]
s.d[j] = z - s.c[j]
# Оптимально, если отрицательных оценок нет
return not has_negatives(s.d)
(8) (9)Функция возвращает истину, если решение оптимально. Если среди оценок Dj в задаче максимизации нет отрицательных, то полученное базисное решение оптимально – задача решена.
Алгоритм спуска на область
Функция simplex_bfs_pivot_j
# Выбор в столбце b минимального
# отрицательного элемента
b_min = 0
b_min_i = None
for i in range(s.m):
if s.b[i] < b_min:
b_min = s.b[i]
b_min_i = i
# Выбор минимального отрицательного
# элемента в соответствующей строке
a_min = 0
a_min_j = None
for j in range(s.m):
if s.a[b_min_i][j] < a_min:
a_min = s.a[b_min_i][j]
a_min_j = j
if a_min_j is None:
raise ValueError('Нет решения ЗЛП')
return a_min_j
Выбрать в столбце b минимальный отрицательный элемент. В соответствующей ему строке также выбрать минимальный отрицательный элемент. Принять этот столбец за разрешающий. Если таких элементов нет, решения ЗЛП не существует.
Функция simplex_bfs_pivot_i
theta_min = 100_000_000
theta_min_i = None
for i in range(s.m):
if sign(s.a[i][p_j], s.b[i]) and s.a[i][p_j] != 0:
s.theta[i] = s.b[i] / s.a[i][p_j]
if s.theta[i] < theta_min:
theta_min = s.theta[i]
theta_min_i = i
else:
s.theta[i] = None
return theta_min_i
В разрешающем столбце выбрать элементы, имеющие одинаковый знак с соответствующей правой частью, и найти отношение к ним соответствующих правых частей (Θ). Из этих отношений выбрать минимальное – соответствующая строка будет разрешающей.
Метод Гомори
Метод Гомори решает задачу целочисленного программирования на основе предварительно решенной симплекс-методом ЗЛП.
Таблица №4 – Структура модуля simplex_gomory
| Функция | Описание |
| simplex_gomory | Осуществление алгоритма |
| gomory_is_integer_plan | Проверка плана на целочисленность |
| gomory_add_constraint | Добавление нового ограничения |
Функция simplex_gomory
while not gomory_is_integer_plan():
gomory_add_constraint()
simplex_iterate()
До тех пор, пока не получен целочисленный план, добавлять в систему по ограничению и переразрешать её симплекс-методом.
Функция gomory_is_integer_plan
for j in range(s.n):
if not is_integer(s.x[j]):
return False
return True
Вернет истину, если план целочисленный, в противном случае - ложь.
Функция gomory_add_constraint
# Поиск наибольшей дробной части в столбце b
bfrac_max = 0
bfrac_max_i = None
for i in range(s.m):
bfrac = modf(s.b[i])
if bfrac >= bfrac_max:
bfrac_max = bfrac
bfrac_max_i = i
# Конструирование нового ограничения
constraint = [0] * (s.n + 1)
for j in range(s.n):
constraint[j] = -modf(s.a[bfrac_max_i][j])
constraint[s.n] = 1
В столбце правых частей выбрать строку, где правая часть имеет наибольшую дробную часть. На основе этой строки ввести в систему новое ограничение:
(11)Решение задачи
В результате были получен следующий оптимальный план – 42 стула, 186 столов, 67 шкафов платяных, 20 шкафов книжных. Прибыль составит 19750 рублей. Полученные результаты соответствуют результатам, полученным в Excel.
В разработанной программе был реализован анализ на чувствительность к правым частям ограничений.
Алгоритм анализа на чувствительность к правым частям ограничений
Для каждого ресурсного ограничения:
1. Увеличить запас ресурса в оригинальной задаче на некое большое значение;
2. Решить измененную задачу симплекс-методом;
3. Найти измененную правую часть: она равна скалярному произведению вектора A оригинальной задачи на вектор X измененной задачи:
(12)4. Найти ΔB – максимальное изменение запаса i-го ресурса: разность измененной правой части и правой части оригинальной задачи:
(13)5. Найти ΔW – максимальное изменение прибыли при изменении i-го ресурса: разность значений целевой функции в измененной и новой задачах:
(14)6. Найти y – теневую цену i-го ресурса: отношение ΔW и ΔB:
(15)Таблица №5 – Анализ чувствительности задачи
| Ресурс | Статус | Максимальное изменение запаса (ΔB) | Максимальное изменение прибыли (ΔW) | Теневая цена |
| 1 | дефицитный | 560.00 | 4044.44 | 7.22 |
| 2 | дефицитный | 431.20 | 3688.44 | 8.55 |
| 3 | недефицитный | -1068.89 | 0.00 | -0.00 |
В таблице №5 представлены результаты анализа на чувствительность, проведенного разработанной программой.
На основе этих результатов можно ответить на второй вопрос задачи: запас какого типа досок следует изменить в первую очередь и насколько для увеличения прибыли?
В первую очередь необходимо увеличить на 560 единиц запас досок I типа. Тогда прибыль составит 23800 рублей.
ЗАКЛЮЧЕНИЕ
Результаты выполнения курсовой работы:
решена задача целочисленного программирования;
рассмотрен универсальный метод решения ЗЛП – симплекс-метод;
рассмотрен метод решения задач целочисленного программирования – метод Гомори;
разработана программа, реализующая вышеуказанные методы, а также анализ на чувствительность.
дан ответ на все вопросы задачи;
Итак, полный ответ на вопросы задачи:
1. Необходимо произвести 42 стула, 186 столов, 67 шкафов платяных, 20 шкафов книжных. Прибыль составит 19750 рублей;
2. В первую очередь необходимо увеличить на 560 единиц запас досок I типа. Тогда прибыль составит 23800 рублей.
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ
Вентцель, Е.С. Исследование операций. – М.: Советское радио, 1972;
Таха, Х. Введение в исследование операций. – Т. 1, –М.: Мир, 1985;