ОПИСАНИЕ И ПОСТРОЕНИЕ МОДЕЛИ

Целочисленное линейное программирование

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

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

В некоторых задачах целочисленные значения могут быть равны только 0 или 1, тогда такие задачи называются задачами с булевыми переменными.

Обоснование выбранного подхода к моделированию

В соответствии с заданием был выбран подход ЦЛП – целочисленное линейное программирование, т.к. задача сводится к нахождению экстремума целевой функции(ЦФ) при целочисленных коэффициентах ЦФ, констант и переменных ограничений. В задаче возможно использование и нецелочисленного метода, но тем самым усложняется процесс вычисления, т.к. возникает необходимость их округления. Причём округление необходимо производить в сторону целого числа вниз, т.е. такое значение 3,5 будет округляться до 3,0. Если же округление производить вверх, то возможно нарушение ограничений ЦФ и выход за рамки её вычисления. Поэтому был выбран целочисленный метод.

Описание концептуальной модели.

Словесное описание:

1. Предприятие располагает двумя видами ресурсов, из которых производится два вида продукции (с различными затратами сырья).
2. Сырье перерабатывается аппаратами двух типов, условно называемыми машинами и агрегатами; каждый тип имеет ограничение по времени работы за некоторый период.
3. На рынке определяется стоимость продукта 1 и продукта 2.
4. Увеличение объема выпуска продукции за счет приобретения нового оборудования и за счет сверхурочных часов работы.
5. Запуск процесса производства с использованием технологических процессов.
6. Реализация продукции, получение прибыли.

Описание элементов и ограничений решаемой задачи.

Основные элементы при решении задачи:

1. х₁ – объем производства продукта 1, целочисленное
2. х₂ – объем производства продукта 2, целочисленное
3. y₁ – количество приобретаемых машин, целочисленное
4. y₂ – количество часов сверхурочной работы, целочисленное
5. 10*x₁ + 8*x₂ – 10*y₁ – 2*y₂ – целевая функция

Ограничения при решении задачи:

1. 4*x1 + 3*x2 – 8*y1 – (5 + y1)*y2 ≤ 40 – ограничение по времени на переработку сырья первого вида.
2. 9*x1 + 3*x2 – 25*y2 ≤ 200 – ограничение по времени на переработку сырья второго вида
3. y2 ≤ 8 – ограничение по количеству часов сверхурочной работы
4. x1, x2, y1, y2 ≥ 0 – искомые значения неотрицательны

РЕШЕНИЕ ЗАДАЧИ

Блок-схема алгоритма решения задачи

Рисунок 2. Блок-схема алгоритма решения задачи.

Ввод данных.

1. Ввод значений «Доход от единицы продукции» (для продуктов 1 и 2).
2. Ввод значения «Дополнительные затраты, связанные с приобретением одной машины».
3. Ввод значения «Доплата за час сверхурочной работы».
4. Ввод значения «Время на переработку сырья» (каждого из двух видов сырья для производства продуктов 1 и 2 соответственно).
5. Ввод значений «Количество аппаратов для переработки сырья» (количество «машин» и «агрегатов»).

Установка ограничений.

Ограничения устанавливаются на основании введенных исходных данных. Например, для данных:

устанавливаются следующие ограничения:

1. Математическая запись

1.1. 4*x1 + 3*x2 – 8*y1 – (5 + y1)*y2 ≤ 40 – ограничение по времени на переработку сырья первого вида.

1.2. 9*x1 + 3*x2 – 25*y2 ≤ 200 – ограничение по времени на переработку сырья второго вида

1.3. y2 ≤ 8 – ограничение по количеству часов сверхурочной работы

2. Запись в EXCEL

Ввод целевой функции.

Коэффициенты целевой функции представлены исходными данными задачи

Целевая функция имеет следующий вид:

где мах – направление расчёта, поиск максимально оптимального решения.

Поиск решения.

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

Цикл ввода исходных данных и поиска решения повторяется для 5 вариантов исходных данных.

Изменяется исходное значение «Доход за единицу продукта 1», чтобы выявить зависимости результатов от этого значения.