Задания для выполнения:

1) Организация арендует самолет грузоподъемностью 83 т, на которой предполагает перевозить груз, состоящий из предметов четырех типов. Веса и стоимости предметов равны соответственно 20 т, 20 т, 13т, 11т и 85у.е., 87 у.е., 15у.е., 120у.е. Требуется погрузить на самолет груз максимальной стоимости.

2) Организация арендует автопоезд грузоподъемностью 30т, на которой предполагает перевозить груз, состоящий из предметов четырех типов. Веса и стоимости предметов равны соответственно 10 т, 20 т, 13т, 5 т и 15у.е., 37 у.е., 45у.е., 10 у.е. Требуется погрузить на баржу груз максимальной стоимости.

3) Организация арендует судно грузоподъемностью 1000 т, на которой предполагает перевозить груз, состоящий из предметов четырех типов. Веса и стоимости предметов равны соответственно 100 т, 200 т, 130т, 50 т и 150у.е., 370у.е., 450у.е., 100у.е. Требуется погрузить на баржу груз максимальной стоимости.

Вопросы для самоконтроля:

1. Сформулировать задачу о ранце.

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

3. Основные критерии модели решения задачи о ранце.

Список использованной литературы:

1. О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., «Мир», 1965, 174 с.

2. В. П. Сигорский. Математический аппарат инженера. - К., «Техніка», 1975, 768 с.

3. Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. - М.; Высшая школа, 1980, 300 с., ил.

4. Е. В. Маркова, А. Н. Лисенков. Комбинаторные планы в задачах многофакторного эксперимента. – М., Наука, 1979, 345 с.

Лабораторная работа № 5

Тема лабораторной работы: Оптимизационные задачи линейного программирования с булевыми переменными и их решение средствами Excel.

Цель лабораторной работы: Получение навыков в решении распределительных задач.

Программное обеспечение: Microsoft Excel

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

Использованию методов математического программирования предшествует, пожалуй, самый важный этап – построение математической модели, адекватной физическому смыслу задачи.

Очевидно, базовыми в этом смысле являются задачи линейного программирования (с одноиндексными переменными) и традиционные транспортные задачи (с двухиндексными

переменными), на основе которых строятся модели задач целочисленного, целевого, динамического, детерминированного, стохастического программирования.

Большинство распределительных задач можно представить в виде матриц, приведённых в табл.1.

Таблица 1.

Элементы С_i,j, стоящие в клетках матрицы, соответствуют затратам или доходу, отвечающим выделению, одной единицы ресурса  R_i  на работу J_j . Величины  С_i,j  могут быть независимыми или зависимыми. Так, например, затраты, обусловленные назначением одной автомашины на некоторый маршрут доставки грузов, не зависят от того какие машины назначены на обслуживание других маршрутов. В то же время при распределение средств между подразделениями фирмы доход от затрат определённого количества денег одним её подразделением (скажем производством) обычно зависит от того, какие средства будут затрачены другими подразделениями (скажем отделом сбыта). В теории распределения рассматриваются преимущественно задачи с независимыми затратами и доходами. Это объясняется не тем, что такие задачи более важны, а лишь тем, что для них значительно легче строить модели и получать решения.

Если затраты (или доход), определяемые объёмом  X_i,j ресурса i, выделенного на выполнение работы J_j, ровны  X_{i,j *} C_i,j , то имеем линейную распределительную задачу. Распределительные задачи с независимыми линейными функциями затрат (или дохода) стали объектом, наиболее интенсивных исследований, в виду того что для их решения были развиты эффективные, итеративные методы линейного программирования. Однако имеются также методы решения некоторых нелинейных распределительных задач, в том числе методы основанные на линейной аппроксимации.

Распределение ресурсов для одного периода времени может влиять на распределения ресурсов для последующих периодов, а может не оказывать на них никакого влияния. Если каждое из последовательности распределений не зависит от всех остальных, то такая задача называется статистической, в противном случае имеем  динамическую распределительную задачу. Статистические задачи исследованы в большей степени, чем динамические, но для решения некоторых типов динамических задач успешно применяются методы линейного динамического и динамического программирования. Для решения некоторых динамических задач применяют методы стохастического программирования. В таких задачах принятие решений основано на вероятностных оценках будущих значений параметров, имеющих фиксированное распределение вероятностей.

Основные методы решения распределительных задач, в частности линейного программирования, построены на допущении, что объёмы, имеющихся в наличии ресурсов (b_i), требуемые объёмы (a_j )  и затраты  (C_i,j ) точно известны.

Если общий объём наличных ресурсов Sb_i (i=1...m) равен общей потребности в них Sa_j (j=1...n), то имеет место сбалансированная (закрытая) распределительная задача. Если же Sa_j ¹ Sb_i , то задача называется несбалансированной (открытой).

Пример решения задачи программной среде Microsoft Excel

Задано: На паром загружается три вида контейнеров. В процессе погрузки используются три технологические операции. На рис.1. показана технологическая схема погрузки.

Технологическая схема погрузки

Фонд рабочего времени погрузчиков ограничен следующими предельными значениями: для первой операции - 430 мин; для второй операции - 460 мин; для третьей операции - 420 мин. Изучение рынка сбыта показало, что ожидаемая прибыль от перевозки одного контейнера видов 1, 2 и 3 составляет $300, $200 и $500 соответственно.

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

вида контейнеров.

Решение Пусть х1, х2, х3 – количество контейнеров, тогда затраты времени и ограничения на погрузку на первой, второй, третьей операции составят соответственно:

Рис.1.

При этом х₁, х₂, х₃ ≥ 0.

Прибыль от перевозки контейнеров (целевая функция):

f(x) = 300х₁+200х₂+500х₃ → maх

Реализация решения в Excel

Положим х₁ = х₂ = х₃ = 1 (содержимое ячеек B2, C2, D2). Эти значения будут изменены в

процессе использования встроенного модуля «Поиск решения», поэтому какие значения

выбрать в качестве опорного плана - неважно. Итак, на первом скриншоте представлены

данные по условию задачи.

Рис.2.

Вычислим затраты времени на погрузку по каждому виду операций, т.е.фактически вычисляем левые части системы ограничений при х1=х2=х3=1. Для вычислений используем встроенную в Excel математическую функцию СУММПРОИЗВ, а также применяем абсолютные ссылки в Excel.

Рис.3.

Рис.4.

Итак, теперь в диапазоне B2:D2 – изменяемые значения, в Е4:Е6 – затраты времени на погрузку по операциям, в G4:G6 – ограничения по времени на работу оборудования, в Е7 – прибыль от погрузки контейнеров (целевая функция). Открываем модуль и заполняем его: Сервис \ Поиск решения.

Рис.5.

В окне «Добавление ограничения» пропишем ограничения на переменные и ресурсы:

Рис.6.

Рис.7.

Окончательно окно «Поиск решения» примет вид:

Рис.8.

Заметим, что внесенные данные, в том числе по ограничениям, в любой момент можно изменить или удалить.

Итак, целевая ячейка определена, изменяемые ячейки внесены, ограничения записаны.

Нажмем кнопку «Выполнить».

Рис.9.

В случае, если задача поставлена некорректно или математическая модель составлена неверно (противоречива система ограничений), «Поиск…» выдает соответствующее диалоговое окно «Поиск не может найти решение».

Если все было выполнено верно, в изменяемых и расчетных ячейках окна Excel появится оптимальный результат:

Рис.10.

Таким образом, оптимальное решение: перевозка контейнеров первого типа – нерентабельна, контейнеров второго типа требуется перевезти 10 единиц, контейнеров третьего типа 23 единицы. При этом максимальная прибыль от перевозки груза составит $13500.