Материал: МО КР1

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Кафедра программного обеспечения информационных технологий

Факультет ФКСиС

Специальность ПОИТ

Контрольная работа №1

по дисциплине «Методы оптимизации»

Тема «Линейная оптимизация. Модели распределения ресурсов. Элементы теории двойственности. Теория игр»

Вариант 4

Выполнил студент: Бордон Е.С.

группа 991051

Зачетная книжка № 99105004

Минск 2021

Задание 1:

1. Составить математическую модель задачи. Объяснить экономический смысл переменных.

2. Составить математическую модель двойственной задачи. Объяснить экономический смысл двойственных переменных.

3. Найти оптимальный план выпуска продукции, обеспечивающий максимальную прибыль.

4. Провести анализ оптимальных решений прямой и двойственной задач, используя отчеты трех типов (по результатам, по устойчивости, по пределам):

а) указать, какая продукция вошла в оптимальный план, и насколько невыгодно производство продукции, не вошедшей в оптимальный план,

б) указать дефицитные и избыточные ресурсы,

в) выписать оптимальное решение двойственной задачи,

г) указать наиболее дефицитный ресурс, исходя из оптимального решения двойственной задачи,

д) указать интервал устойчивости двойственных оценок,

5. Решить двойственную задачу. Сравнить решение с полученным

в пункте 4.

6. Выяснить, как изменится выпуск продукции и значение целевой функции, при изменении каждого из имеющихся ресурсов на единицу. Оценить раздельные и суммарное изменения.

Вариант 4:

На приобретение оборудования для нового производственного участка выделено 30 тыс. ден. ед. И помещение площадью в 45 м кв. Участок может быть оснащен машинами трех типов, характеристики которых приведены в таблице:

Найти оптимальный план приобретения машин, обеспечивающий новому производственному участку максимальную производительность.

Решение:

Обозначим неизвестное количество оборудования М1, М2 и М3 видов соответственно через x1, x2 и x₃.

Функция цели может быть записана следующим образом:

F(x) = 8x₁ + 4x₂+3x₃ (max);

Ограничения по площади:

9x₁ + 4x₂ + 3x₃ ≤ 45;

Ограничения по стоимости:

6x₁ + 3x₂ + 2x₃ ≤ 30;

Ограничения на знак переменных:

x₁ ≥ 0; x₂ ≥ 0; x₃ ≥ 0;

Преобразуем неравенства в равенства добавлением неотрицательных переменных:

8x₁ + 4x₂ + 3x₃ + 0x₄ + 0x₅ → max

9x₁ + 4x₂ + 3x₃ + 1x₄ + 0x₅ = 45

6x₁ + 3x₂ + 2x₃ + 0x₄ + 1x₅ = 30

x₁, x₂, x₃, x₄, x₅ ≥ 0

Матрица коэффициентов A=ǁa_ijǁ системы уравнений имеет вид:

Правая часть ограничений системы уравнений B имеет вид:

Целевая функция C имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последняя строка — это целевая функция, умноженная на −1.

Базисные векторы x₄, x₅, следовательно, все элементы в столбцах x₄, x₅, ниже горизонтальной линии должны быть нулевыми.

Симплекс таблица примет вид:

Таблица 1:

Запишем текущий опорный план:

Х = (0 0 0 45 30)

Значение целевой функции в данной точке:

F = C⋅X = 8⋅0 + 4⋅0 + 3⋅0 + 0⋅45 + 0⋅30 = 0

Данный опорный план не является оптимальным, так как на пересечении строки 3 и столбцов x₁, x₂, x₃, x₄, x₅ есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-8), следовательно в базис входит вектор x₁. Определяем, какой вектор выходит из базиса. Для этого вычисляем min(a_i,0 /a_i,1), при a_i,1>0, i=1,...2. min(45:9, 30:6)=5 соответствует строке 1. Из базиса выходит вектор x₄. Сделаем исключение Гаусса для столбца x₁, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки 2, 3 со строкой 1, умноженной на -2/3, 8/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Таблица 2:

Запишем текущий опорный план:

Х = (5 0 0 0 0)

Значение целевой функции в данной точке:

F = C⋅X = 8⋅5 + 4⋅0 + 3⋅0 + 0⋅0 + 0⋅0 = 40

Данный опорный план не является оптимальным, так как на пересечении строки 3 и столбцов x₁, x₂, x₃, x₄, x₅ есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-4/9), следовательно в базис входит вектор x₂. Определяем, какой вектор выходит из базиса. Для этого вычисляем min(a_i,0 /a_i,2), при a_i,2>0, i=1,...2. min(5:4/9, 0:1/3)=0 соответствует строке 2. Из базиса выходит вектор x₅. Сделаем исключение Гаусса для столбца x₂, учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки 1, 3 со строкой 2, умноженной на -4/3, 4/3, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Таблица 3:

Запишем текущий опорный план:

Х = (5 0 0 0 0)

Значение целевой функции в данной точке:

F = C⋅X = 8⋅5 + 4⋅0 + 3⋅0 + 0⋅0 + 0⋅0 = 40

Данный опорный план не является оптимальным, так как на пересечении строки 3 и столбцов x₁, x₂, x₃, x₄, x₅ есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-1/3), следовательно в базис входит вектор x₃. Определяем, какой вектор выходит из базиса. Для этого вычисляем min(a_i,0 /a_i,3), при a_i,3>0, i=1,...2. min(5:1/3)=15 соответствует строке 1. Из базиса выходит вектор x₁. Сделаем исключение Гаусса для столбца x₃, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 1Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Таблица 4:

Запишем текущий опорный план:

Х = (0 0 15 0 0)

Значение целевой функции в данной точке:

F = C⋅X = 8⋅0 + 4⋅0 + 3⋅15 + 0⋅0 + 0⋅0 = 45

Текущий опорный план является оптимальным, так как в последней строке нет отрицательных элементов.

Решение канонической задачи можно записать так:

Х₀^* = (0 0 15 0 0)

Решение исходной задачи:

Х^* = (0 0 15)

x₁=0, x₂=0, x₃=15

Значение целевой функции в оптимальной точке:

F = C_исх⋅X^∗ = 8⋅0 + 4⋅0 + 3⋅15 = 45

где C_исх − коэффициенты целевой функции исходной задачи.

Ответ: машин М3 – 15шт, производительность равна 45тыс. ед.

Проверка средствами EXCEL:

Исходные данные:

Рис1. Microsoft Excel

Заполним формулы для целевой функции и ограничений:

Рис2. Microsoft Excel

Выполним настройку поиска решения:

Рис3. Microsoft Excel

Полученный результат:

Рис4. Microsoft Excel

Ответ: машин М3 – 15шт, производительность равна 45тыс. ед.

Попробуем изменить каждый имеющийся ресурс на одну единицу:

Увеличиваем Стоимость на 1 единицу и занимаемую площадь на 1 единицу.

Таблица 5:

Решать будем с помощью таблицы Excel.

Исходные данные с учетом изменившихся условий:

Рис5. Microsoft Excel

Данные после обработки:

При увеличении на одну единицу стоимости машин и занимаемой ими площади, а также сохранении производительности и остальных параметров ответ меняется. Становится выгоднее приобрести 3 машины М1 и 3 машины М3 с суммарной производительностью в 33 тыс.ед.

Выводы:

Симплекс-метод позволяет эффективно найти оптимальное решение, избегая простой перебор всех возможных угловых точек. Основной принцип метода: вычисления начинаются с какого-то «стартового» базисного решения, а затем ведется поиск решений, «улучшающих» значение целевой функции. Это возможно только в том случае, если возрастание какой-то переменной приведет к увеличению значения функционала.

Задание 2:

1) Составить математическую модель транспортной задачи;

2) Решить транспортную задачу без учета дополнительных ограничений на перевозки;

3) Решить транспортную задачу с дополнительными ограничениями на перевозки.

4) Сделать выводы.

Вариант 4: