Пример 2.3. Задача о раскрое (о минимизации обрезков)

ОБЩАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Экономико-математическая постановка и модель общей задачи линейного программирования записывается в виде:

(2.1)

При ограничениях-неравенствах или равенствах:

(2.2)

и условиях

(2.3)

Стандартной задачей линейного программирования называется зада­ча, в которой требуется определить максимальное (минимальное) значе­ние целевой функции (2.1) при ограничениях неравенствах (2.2) и усло­виях (2.3).

Канонической (или основной) задачей линейного программирования называется задача, которая заключается в определении максимального значения целевой функции (2.1) при выполнении ограничений-уравне­ний (2.2).

В системе из т уравнений с я независимыми переменными х_к базис­ными (основными) называются любые т переменные, если соответст­вующий им определитель матрицы коэффициентов отличен от нуля, а остальные (п-т) переменные называются свободными.

В базисном решении все {п-т) свободные переменные равны нулю.

Допустимым базисным решением (опорным планом) называется та­кой план, в котором содержатся только неотрицательные переменные и свободные равны нулю. Допустимое базисное решение является невыро­жденным, если все базисные переменные строго положительны, а выро­жденным — в противном случае.

Совокупность независимых переменных X = (x₁ х₂,..., х_n), удовлетво­ряющих ограничениям (2.2) и условиям (2.3) задачи, называется допус­тимым решением (или в экономических задачах — планом). Совокуп­ность допустимых решений — ОДР.

План Х' = (х'₁, х'₂, ..., х'_п), при котором целевая функция задачи при­нимает экстремальное значение, называется оптимальным.

Рассмотрим некоторые примеры составления математических мо­делей.

Пример 2.1. Задача о выпуске продукции (об использовании сырья)

Пусть предприятие выпускает два вида продукции Р1 и Р2 для прода­жи. Для производства продукции используется три вида сырья S₁ S₂, S₃ Расход сырья на каждый вид продукции, стоимость единицы продукции и запасы сырья представлены в таблице 2.1.

Таблица 2.1

Какое количество каждого вида продукции необходимо предпри­ятию, чтобы прибыль от продажи ее была максимальной?

Решение

Обозначим х₁ — объем выпуска первого вида продукции, х₂ — ко­личество продукции второго вида, тогда математическая модель имеет вид:

Пример 2.2. Задача составления смесей (о диете)

Пусть диетолог составляет диету, согласно которой пациент должен получать не менее 18 единиц питательного вещества S₁ не менее 25 еди­ниц вещества S₂ и не менее 32 единиц вещества S₃. Диета состоит из двух составляющих Д₁и Д₂. Содержание количества единиц питательных ве­ществ в единице веса каждой составляющей диеты и стоимость продук­тов приведены в табл. 2.2.

Таблица 2.2

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

Решение

Для составления математической модели обозначим x₁ — количество единиц питательных веществ в продуктах первого вида, а х₂ — количе­ство единиц питательных веществ в продуктах второго вида, тогда мате­матическая модель имеет вид:

Пример 2.3. Задача о раскрое (о минимизации обрезков)

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

Например, строительная фирма заказала изготовить заготовки двух видов: 2 м и 1,5 м из досок длиной 5 м. причем заготовки каждого вида должны быть получены не менее 70 и 100 штук соответственно.

Каждая доска длиной 5 м может быть распилена несколькими спосо­бами:

1) на 2 заготовки по 2 м;

2) на 1 заготовку длиной 2 м и две заготовки 1,5 м;

3) на 3 заготовки по 1,5 м.

Обозначим через x_1, x₂, х₃ количество досок, распиливаемых первым, вторым и третьим способами соответственно. Тогда математическая мо­дель может быть записана в виде:

при ограничениях и условиях:

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

Вопросы

1. Как формулируется задача линейного программирования?

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

3. Какие решения называются базисными, опорными и оптимальными?

4. Какие решения задач линейного программирования называются вырож­денными и невырожденными?

5. Как переходят от общей задачи линейного программирования в канони­ческой?

6. В чем отличие задач о сырье и диете?

Задачи 2.1-2.9

Задача 2.1

Торговое предприятие реализует четыре группы товаров: I, II, III и IV. Нормы расходов ресурсов на каждую группу товаров, запасы ресурсов, а также прибыль от единицы каждого вида продукции заданы в табл.

Определить объем продаж товаров, чтобы прибыль торгового пред­приятия была максимальной.

Задача 2.2

Предприятие планирует три вида технологических процессов П,, П2, П3 при этом объем выпускаемой продукции по этим планам равен 200, 250 и 300 единиц соответственно. Издержки по разным технологиям со­ответствующих факторов в единицу времени указаны в табл. Нормы рас­ходов ресурсов на каждую группу товаров, запасы ресурсов, а также при­быль от единицы каждого вида продукции заданы в табл.

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

Задача 2.3

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

Плановый фонд ресурсов имеет следующие значения: затраты на при­готовление блюд не должно превышать 900 чел.-час, на доставку потре­бителям — 500 чел.-час, накладные расходы могут быть не более 3000 руб. и план товарооборота равен 8000 руб. Требуется определить, какое коли­чество каждого вида блюд необходимо выпускать, чтобы обеспечить мак­симальную прибыль ресторана.

Задача 2.4

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

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

Задача 2.5

Диетолог разработал диету, состоящую из сливочного масла, мяса, хлеба и фруктов. Содержание калорий, белков, жиров, углеводов и холе­стерина (в 100 г продукта), нормы потребления (в сутки) и цена 100 г со­ответствующего продукта указаны в табл.

Составить математическую модель задачи.

Задача 2.6

Магазин строительных материалов заказывает изготовить из 200 штук досок размером: шириной 120 мм, длиной 6,0 м и толщиной 25 мм и 100 штук длиной 4 м, шириной 120 мм и толщиной 25 мм три комплекта отделоч­ной доски (вагонки): две детали длиной 2 м и одна длиной 1,5 м. Рассчи­тать как распилить доски, чтобы изготовить, а затем максимальное ко­личество продать.

Задача 2.7

Торговое предприятие, располагающее материально-денежными ресурсами, реализует три группы товаров: I, II, III. Плановые нормати­вы затрат ресурсов на тыс. руб. товарооборота, а также объем ресурсов задан в табл.

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

Задача 2.8

Торговое предприятие реализует товар нескольких групп: А, В, С. Составить оптимальный план товарооборота по критерию max доходаn , если известны a_ik и b_i

Задача 2.9

Торговое предприятие реализует товар нескольких групп: А, В, С. Составить оптимальный план товарооборота по критерию max дохода , если известны a_ik и b_i.

Не нашли, что искали? Воспользуйтесь поиском по сайту: