Методы оптимальных решений

Размещено на http://www.allbest.ru/

Вариант 3

Ситуация 1

Построить математическую модель задачи оптимизации производства.

Фабрика выпускает 3 вида тканей, причём суточное плановое задание составляет не менее 90м тканей 1-го вида, 70м- 2, 60м- 3. Суточные ресурсы следующие: 780 единиц производственного оборудования, 850 единиц сырья и 790 единиц электроэнергии, расход которых на 1м представлен в таблице. Цена за 1м равна 80уе.-1 вид, 70-2й, 60-3й. Определить сколько метров ткани каждого вида следует выпускать, чтобы общая стоимость выпускаемой продукции была максимальной.

Решение:

Для составления математической модели необходимо ответить на три вопроса:

1. Что является переменными задачи?

2. Какова цель задачи?

3. Какие условия являются ограничениями?

Ответим на эти вопросы:

1. В данной задаче необходимо найти объемы видов производимых тканей, следовательно, неизвестными являются количества тканей 1-го, 2-го и 3-го видов - соответственно обозначаемые х₁, х₂, х₃.

2. Целью является максимизация прибыли от реализации продукции, следовательно, зная прибыль (80, 70, 60 уе, от реализации продукции х₁, х₂, х₃ соответственно) и объемы производимых тканей, можно составить целевую функцию:

3. Условиями ограничений является то, что для выпуска каждого вида ткани требуется определённый размер суточных ресурсов, а также их расход на 1 м для каждого вида тканей (см. табл.). Также известно, что по плану необходимо выпускать не менее 90 м ткани первого типа, 70 метров ткани второго типа и 60 метров ткани третьего типа. Отсюда можно записать систему функциональных ограничений:

Значения f(x) и будут следующими (cм. скриншот и исходный xlsx файл):

Следовательно, что для получения максимальной прибыли 19075 уе. необходимо производить 112,5 м ткани I вида,70 м ткани II вида и 86,25 м ткани III вида. Возможности оборудования и электроэнергия будут потрачены полностью, из 850 ед. сырья будет использовано 823,75 ед.

Ситуация 2

Построить математическую модель задачи. Составить задачу, двойственную к исходной.

Предприятию предложен на выбор выпуск 3 новых изделий, за счёт которых можно было бы расширить номенклатуру продукции предприятия при тех же запасах ресурсов. Нормы затрат ресурсов и прибыль от реализации единицы продукции для этих изделий представлены в таблице. Определить из предложенных видов изделия, выгодные для выпуска предприятием математический задача транспортный

Решение:

Для составления математической модели необходимо ответить на три вопроса:

1. Что является переменными задачи?

2. Какова цель задачи?

3. Какие условия являются ограничениями?

Ответим на эти вопросы:

1. В данной задаче необходимо найти наиболее выгодные виды изделия для выпуска, следовательно, неизвестными являются количество изделий вида А, Б и В - соответственно обозначаемые х₁, х₂, х₃.

2. Целью является максимизация прибыли от реализации продукции, следовательно, зная прибыль (80, 70, 45 денежных единиц, от реализации продукции х₁, х₂, х₃ соответственно) и объемы производимых изделий, можно составить целевую функцию:

3. Условиями ограничений является то, что для выпуска каждого вида продукции требуется определённый размер ресурсов, а также их расход на изделие для каждого вида продукции (см. табл.). Отсюда можно записать систему функциональных ограничений:

- целые.

Значения f(x) и будут следующими (cм. скриншот и исходный xlsx файл):

Следовательно, что для получения максимальной прибыли 740 денежных единиц, необходимо производить 8 изделий вида Б и 4 вида В, изделие вида А не выгодно для выпуска предприятием. Возможности труда и сырья будут потрачены полностью, из 20 ед. оборудования будет использовано 16 ед.

Составление задачи, двойственной к исходной:

По системе функциональных ограничений и целевой функции состави расширенную матрицу A₁:

Транспонируем матрицу A₁ для получение матрицы A^T₁:

Определим целевую функцию и систему ограничений:

- целые.

Ситуация 3

Решить транспортную задачу с использованием вычислительных средств Excel

Имеются n пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции с i- го пункта производства в j-й центр распределения Сij приведена в таблице, где под строкой понимается пункт производства, а под столбцом - пункт распределения. Кроме того, в этой таблице в i-й строке указан объем производства в i- м пункте производства, а в j-м столбце указан спрос в j-м центре распределения. Необходимо составить план перевозок по доставке требуемой продукции в пункты распределения, минимизирующий суммарные транспортные расходы.

Решение:

Переменными x_ij обозначим количество продукции перевозимой с i-го пункта производства в j-ый пункт потребления, с_i,j - стоимость перевозки единицы продукции. Векторы A и B - запасы и потребности в продукции соответственно.

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

Решим задачу с помощью средств Excel. Вводим матрицу коэффициентов целевой функции, элементами которой являются стоимости перевозки единицы груза из одного пункта в другой в диапазон B6:F9. Далее отводим диапазон ячеек под неизвестные нашей задачи, то есть под матрицу объемов перевозки грузов, которая и составит оптимальный план задачи перевозок B14:F17. Можно ввести первоначальные опорные значения объемов перевозки, а можно оставить эти ячейки пустыми. В ячейку B20 вводим формулу целевой функции: =СУММПРОИЗВ(B6:F9;B14:F17). В ячейки I13:I17 вводим ограничения по объемам производства, являющиеся левыми частями ограничений:

=СУММ(B14:F14)

=СУММ(B15:F15)

=СУММ(B16:F16)

=СУММ(B17:F17)

В ячейки L14:L18 вводим ограничения по потребностям, являющиеся левыми частями следующей группы ограничений, включая потребности фиктивного пункта:

=СУММ(B14:B17)

=СУММ(C14:C17)

=СУММ(D14:D17)

=СУММ(E14:E17)

=СУММ(F14:F17)

Рядом вводим числовые значения правых частей ограничений

Вызываем окно Поиск решения и заполняем:

После выполнения получим:

Решение дает матрицу распределения перевозок:

Наличие поставки в фиктивный пункт 25 единиц продукции означает, что в пункте производства А останутся излишки в размере 20 единиц, в пункте В - 5. Остальная продукция будет развезена в соответствии с полученным планом, все потребности будут удовлетворены. Транспортные расходы составят 340 денежных единиц

Ситуация 4

Решить задачу о назначениях преподавателей на проведение занятий в соответствии с заданной таблицей.

Решение:

Заметим, что данная модель не сбалансирована, поскольку преподавателей больше, чем видов занятий. Следовательно, решения этой задачи, в модели надо ввести фиктивную задачу.

Подготовим данные на листе Excel, как показано на рисунке.

В ячейках H6:L10 расположим неизвестные.

В ячейку A15 запишем целевую функцию =СУММ ПРОИЗВ (B6:F10;H6:L10) - стоимость выполнения всех занятий.

В ячейках M6:M10 запишем левые части ограничений, выражающих количество проведения занятий на одного преподавателя

=СУММ(H6:L6)

=СУММ(H7:L7)

=СУММ(H8:L8)

=СУММ(H9:L9)

=СУММ(H10:L10)

В ячейках N6:N10 запишем правые части ограничений, указывающие на то, что каждый преподаватель проводит одно занятие.

В ячейках H11:L11 запишем левые части ограничений, выражающих количество преподавателей, проводящих одно задание.

=СУММ(H6:H10)

=СУММ(I6:I10)

=СУММ(J6:J10)

=СУММ(K6:K10)

=СУММ(L6:L10)

В ячейках H12:L12 запишем правые части ограничений, выражающих тот факт, что каждое занятие проводит один преподаватель.

Вызовем «Поиск решения» и заполним окно следующим образом:

После выполнения получим решение:

Решение задачи дает следующий график выполнения работ:

Преподаватель 1 не проводит занятий.

Преподаватель 2 проводит занятие 2.

Преподаватель 3 проводит занятие 3.

Преподаватель 4 проводит занятие 1.

Преподаватель 5 проводит занятие 4.

Также получено, что, Преподаватель 1 проводит фиктивное занятие. Это означает, что этот преподаватель свободен и ему можно назначить проведение другого занятия, либо сократить штат.

Для проведения всех видов занятий потребуется 950 денежных единиц.

Размещено на Allbest.ru