|
|
Примеры задач линейного программирования1. Задача об использовании ресурсов (задача планирования производства). Для изготовления двух видов продукции Р, и Рз используют четыре вида ресурсов: S1, S2, S3 и S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице 5.1.1 (цифры условные).
Таблица 5.1.1
Прибыль, получаемая от единицы продукции P1 и P2, соответственно 2 и 3 рубля. Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной. Решение. Составим экономико-математическую модель задачи. Обозначим x1, x2 - число единиц продукции соответственно P1 и Р2, запланированных к производству. Для их изготовления (см. таблице 1.1) потребуется
По смыслу задачи переменные x1 ³ 0, х2 ³ 0. (5.1.8)
Суммарная прибыль F составит 2 х руб. от реализации продукции PI и 3x руб. - от реализации продукции P2, т.е.
F= 2х1 + 3х2. (5.1.9)
Итак, экономико-математическая модель задачи: найти такой план выпуска продукции X = (х1, х2), удовлетворяющий системе (5.1.7) и условию (5.1.8), при котором функция (5.1.9) принимает максимальное значение. Задачу легко обобщить на случай выпуска n видов продукции с использованием m видов ресурсов. Обозначим Хi (i=1, 2, …, m) – запас ресурса S1; aij – число единиц ресурса Si, затрачиваемого на изготовление единицы продукции Pj (числа aij – коэффициенты прямых затрат, которые часто называются технологическими коэффициентами); cj – прибыль от реализации единицы продукции Pj. Тогда экономико-математическая модель задачи об использовании ресурсов в общей постановке примет вид: найти такой план Х = (х1, х2, …, хn) выпуска продукции, удовлетворяющий системе
и условию
при котором функция
принимает максимальное значение. 2. Задача составления рациона (задача о диете, задача о смесях). Имеются два вида корма I и II, содержащие питательные вещества в 1 кг каждого вида корма и необходимый минимум питательных веществ, которые приведены в таблице 5.1.2 (цифры условные). Стоимость 1 кг вида корма I и II соответственно равна 4 и 6 руб. Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела. Решение. Составим экономико-математическую модель задачи. Таблица 5.1.2
Обозначим х1, х2 – количество кормов I и II, входящих в дневной рацион. Тогда этот рацион (таблице 1.2) будет включать
Кроме того, переменные
Общая стоимость рациона составит (в руб.) F = 4х1 + 6х2. (5.1.15)
Итак, экономико-математическая модель задачи: составить дневной рацион Х = (х1, х2), удовлетворяющий системе (5.1.13) и условию (5.1.14), при котором функция (5.1.15) принимает минимальное значение. Для формулировки задачи в общей постановке обозначим: xj (j = 1, 2, …, n) – число единиц корма n-го вида; bi (I = 1, 2, …, m) – необходимый минимум содержания в рационе питательных веществ Si в единице корма j-го вида; cj – стоимость единицы корма j-го вида. Тогда экономико-математическая модель задачи примет вид: найти такой рацион X = (x1, x2, …, xj, …, xn), удовлетворяющий системе
и условию
при котором функция
принимает минимальное значение. 3. Задача об использовании мощностей (задача о загрузке оборудования). Предприятию задан план производства продукции по времени и номенклатуре: требуется за время Т выпустить n1, n2 …, nk единиц продукции Р1, Р2, …, Рk. Продукция производится на станках S1, S2, … Sm. Для каждого станка известны производительность aij (т.е. число единиц продукции Pj, которое можно произвести на станке Si) и затраты bij на изготовление продукции Pj на станке Si в единицу времени. Необходимо составить такой план работы станков (т.е. так распределить выпуск продукции между станками), чтобы затраты на производство всей продукции были минимальными. Составим экономико-математическую модель задачи. Обозначим xij – время, в течение которого станок Si будет занят изготовлением продукции Pj, i = 1, 2, …, m; j = 1, 2, …, k. Так как время работы каждого станка ограничено и не превышает Т, то справедливы неравенства:
Для реализации выпуска по номенклатуре необходимо, чтобы выполнялись следующие равенства:
(5.1.20) Кроме того,
(5.1.21) Затраты на производство всей продукции выразятся функцией
(5.1.22) Экономико-математическая модель задачи об использовании мощностей примет вид: найти такое решение Х = (х11, х12, …, хmk), удовлетворяющее системам (5.1.19) и (5.1.20) и условию (5.1.21), при котором функция (5.1.22) принимает минимальное значение.
4. Задача о раскрое материалов. На раскрой (распил, обработку) поступает материал одного образца в количестве a единиц. Требуется изготовить из него единицу разных комплектующих изделий в количествах, пропорциональных числам b1, b2, …, bi (условие комплектности). Каждая единица материала может быть раскроена n различными способами, причём использование i-го способа (i = 1, 2, …, n) даёт aik единиц k-го изделия (k = 1, 2, …, l). Необходимо найти план раскроя, обеспечивающий максимальное число комплектов. Составим экономико-математическую модель задачи. Обозначим xi – число единиц материала, раскраиваемых i-м способом, и х – число изготавливаемых комплектов изделий. Так как общее количество материала равно сумме его единиц, раскраиваемых различными способами, то
(5.1.23)
Требование комплектности выразится уравнением
Очевидно, что
Экономико-математическая модель задачи: найти такое решение Х = (х1, х2, …, хj, …, xn), удовлетворяющее системе уравнение (5.1.23) – (5.1.24) и условию (5.1.25), при котором функция F = x принимает максимальное значение. Рассмотрим пример. Для изготовления брусьев длиной 1,2 м, 3 м и 5 м в соотношении 2:1:3 на распил поступают 195 брёвен длиной 6 м. Определить план распила, обеспечивающий максимальное число комплектов. Составить экономико-математическую модель задачи. Решение. Прежде всего определим всевозможные способы распила брёвен, указав соответствующее число получаемых при этом брусьев (таблице 5.1.3).
Таблица 5.1.3
Обозначим: xi – число брёвен, распиленных i-м способом (i = 1, 2, 3, 4); х – число комплектов брусьев. Учитывая, что все брёвна должны быть распилены, а число брусьев каждого размера должно удовлетворять условию комплектности, экономико-математическая модель задачи примет вид
при ограничениях:
Задачу о раскрое легко обобщить на случай m раскраиваемых материалов. Пусть каждая единица j-го материала (j = 1, 2, …, m) может быть раскроена n различными способами, причём использование i-го способа (i = 1, 2, …, n) даёт aijk единиц k-го изделия (k = 1, 2, …, l), а запас j-го материала равен aj единиц. Обозначим xij – число единиц j-го материала раскрываемого i-м способом. Экономико-математическая модель задачи о раскрое в общей постановке примет вид: найти такое решение Х = (х11, х12, …, xnm), удовлетворяющее системе и условию xij ³ 0, при котором функция F = x принимает максимальное значение.
  Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...  ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
единиц ресурса 
единиц ресурса S2; 
единиц ресурса S3 и Зх1 единиц ресурса S4. Так как потребление ресурсов S1, S2, S3 и S4 не должно превышать их запасов соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запасами выразится системой неравенств:
(5.1.7)
(5.1.10)
(5.1.11)
(5.1.12)
единиц питательных веществ S1, 
- единиц вещества S2 и 
- единиц питательного вещества S3. Так как содержание питательных веществ S1, S2 и S3 в рационе должно быть не менее соответственно 9, 8 и 12 единиц, то получим систему неравенств
(5.1.13)
(5.1.14)
(5.1.16)
(5.1.17)
(5.1.18)
(5.1.19)
(5.1.24)
(5.1.25)
