Разработка соответствия экономическо-математической модели к задачам об ограничении распределения ресурсов, диете и назначениях

Задание Написать условие и разработать соответствие экономическо-математической модели к задачам. Реализовать модели в электронной таблице Excel, выписать соответствующие ответы.

1. Об ограничении распределения ресурсов (3 задачи) Задача № 1: Исходя из специализации и своих технологических возможностей предприятие может выступать четыре вида продукции. Сбыт любого количества обеспечен. Для изготовления этой продукции используются трудовые ресурсы, полуфабрикаты и станочное оборудование. Общий объём ресурсов, расход каждого ресурса за единицу продукции, приведены в таблице. Требуется определить план выпуска, доставляющий предприятию максимум прибыли.

Таблица 1.

Пусть — объёмы продукции планируемый к выпуску; - сумма ожидаемой выручки. Математическая модель прямой задачи:

Z= max.

Excel 84 000.

Х₃₌₄₀₀

Х₄₌₅₀₀

Х₇₌₂₀₀

Задача № 2: Необходимо оптимальным образом распределить общую площадь засождений кустарников под различные виды, если известен Общий объем производительных ресурсов, Необходимо оптимальным образом распределить общую площадь.

Таблица 2.

Х₁= площадь засождений 1 вида, га Х₂₌ площадь засождений 2 вида, га Х₃₌ площадь засождений 3 вида, га.

Z=10 Х₁+ 8Х₂+ 7Х₃ max.

Excel 440 000.

Х_1=1333,33

Х_2=111,11

Задача № 3: Необходимо оптимальным образом распределить общую площадь посева под различные культуры, если известны общий объем производственных ресурсов, нормы их затрат на один гектар, а также урожайность каждой культуры и ее цена представлены в таблице.

Таблица 3.

Х₁= площадь посева 1 вида, га Х₂₌ площадь посева 2 вида, га Х₃₌ площадь посева 3 вида, га.

Z=10 Х₁+ 8Х₂+ 6Х₃ max.

Excel 3 195 450.

Х₂₌₄₅₀₀

Х₄₌₃₅₀₀

2. О диете (2 задачи) Задача № 1: Для откорма животных используется три вида комбикорма: А, В и С. Каждому животному в сутки требуется не менее 800 г. жиров, 700 г. белков и 900 г. углеводов. Содержание в 1 кг. каждого вида комбикорма жиров белков и углеводов (граммы) приведено в таблице:

Таблица 4.

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

Математическая модель задачи есть:

Х₁, Х₂, Х₃ — количество комбикорма А, В и С. Стоимость смеси есть:

Z=31 Х₁ +23 Х₂ +20Х₃ min.

Ограничения на количество ингредиентов:

Excel 0.

Х₄₌₈₀₀

Х₅₌₇₀₀

Х₆₌₉₀₀

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

Определить какую структуру приготовления блюда которые обеспечивают максимальную прибыль?

Таблица 5.

Х₁= количество блюд 1 вида, в 100 шт Х₂₌ количество блюд 2 вида, в 100 шт Х₃₌ количество блюд 3 вида, в 100 шт.

Z=300 Х₁+ 100Х₂+ 200Х₃ max.

Excel 507 142,86.

Х_2=271,43

Х₃₌₂₄₀₀

Х₄₌₇₀₀

3. О назначениях (2задачи) Задача № 1: Цеху металлообработки нужно выполнить срочный заказ на производство деталей. Каждая деталь обрабатывается на 4-х станках С1, С2, С3 и С4. На каждом станке может работать любой из четырех рабочих Р1, Р2, Р3, Р4, однако, каждый из них имеет на каждом станке различный процент брака. Из документации ОТК имеются данные о проценте брака каждого рабочего на каждом станке:

Таблица 6.

Необходимо так распределить рабочих по станкам, чтобы суммарный процент брака (который равен сумме процентов брака всех 4-х рабочих) был минимален. Чему равен этот процент?

Обозначим за — переменные, которые принимают значения 1, если i-й рабочий работает на j-м станке. Если данное условие не выполняется, то. Целевая функция есть:

Вводим ограничения. Каждый рабочий может работать только на одном станке, то есть.

Excel 4 554 621,23.

Х_21=1235,23

Х_22=2694,2

Х_23=2624,25

Задача № 2: В городе возможно сооружение трех видов, каждый из которых характеризуется определенным количеством двухкомнатных, трехкомнатных и четырехкомнатных квартир, а также разной себестоимостью. Себестоимость количества квартир в каждом доме, а также требуемое количество квартир представлены в таблице. Составить план строительства жилых домов, обеспечивающей минимальную себестоимость всей застройки.

Х₁= количество домов 1 типа Х₂₌ количество домов 2 типа Х₃₌ количество домов 3 типа.

Таблица 7.

Z=350 Х₁+750 Х₂+ 470Х₃ min.

Excel 0.

Х₄₌₁₀₀₀

Х₅₌₈₀₀

Х₆₌₇₀₀

4. Транспортная задача (2 задачи) Задача № 1: Компания «Стройгранит» производит добычу строительной щебенки и имеет на территории региона три карьера. Запасы щебенки на карьерах соответственно равны 800, 900 и 600 тыс. тонн. Четыре строительные организации, проводящие строительные работы на разных объектах этого же региона дали заказ на поставку соответственно 300, 600, 650 и 750 тыс. тонн щебенки. Стоимость перевозки 1 тыс. тонн щебенки с каждого карьера на каждый объект приведены в таблице:

Таблица 8.

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

Данная транспортная задача является закрытой, так как запасы поставщиков 800+900+600=2300 равны спросу потребителей 300+600+650+750=2300. Математическая модель ЗЛП в данном случае имеет вид:

— количество щебенки, перевозимой с i-го карьера на j-й объект. Тогда целевая функция равна.

Ограничения имеют вид.

Excel 2 655 485,23.

X₃₁=2657.

X₃₂=2658.

X₃₄=152.

Задача № 2: Необходимо оптимальным образом распределить три экскаватора для выполнения работ на каждом из двух строительных объектов. Себестоимость земляных работ указана в таблице.

Таблица 9.

Х_ij количество экскаватора на і ом объекте по j ой себестоимости выполненных работ на строительном участке.

Excel 59 822 582.

X₁₁=2652.

X₁₂=2658.

X₃₂=72.

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

Z=12.

Z_A=12.

Excel.

ЦФ=202.

Х₁₌3.

Х₂₌0.

Решение задачи симплексным методом.

Решение не является оптимальным.

Z=202.

Х₁₌3.

Х₂₌0.

Решить транспортную задачу методом потенциалов. Потребителям Б1, Б2,Б3 и Б4 требуется песок в количествах соответственно б1, б2, б3 и б4 тонн. На складах имеется следующее количество песка: А1 = а1 т, А2 = а2 т и А3 = а3 т. Требуемое и имеющееся количество песка приведено в табл.4. Расстояния между поставщиками и получателями песка приведены в табл. 10. Необходимо составить план перевозок песка (план закрепления потребителей за поставщиками) так, чтобы при минимальной транспортной работе были удовлетворены запросы всех потребителей.

Таблица 10.

Таблица 11.

Пусть потребителям Б1, Б2, Б3 и Б4 требуется песок в количествах соответственно 30,70, 40 и 30 тонн. На складах имеется следующее количество песка: А1 = 80 т, А2= 50 т и А3 = 40 т. Расстояния между поставщиками и получателями песка приведены в табл. 11. Необходимо составить план перевозок песка (план закрепления потребителей за поставщиками) так, чтобы при минимальной транспортной работе были удовлетворены запросы всех потребителей.

Таблица 12.

Очевидно, что транспортная работа будет минимальной, если доставлять песок каждому потребителю с ближайшего к нему склада. В таком случае решение было бы очевидным. Однако в рассматриваемой задаче это невозможно, так как для потребителей Б1, Б2 и Б4 с суммарной потребностью в 130 т ближайшим является склад А2, где имеется лишь 50 т песка. Поэтому для полного удовлетворения потребности этих потребителей неизбежны перевозки с других складов. При этом возможны различные варианты. 1. Составление матрицы условий. Запишем условия задачи в форме матрицы (табл. 13).

Таблица 13.

В правых верхних углах клеток, представляющих собой реальные маршруты перевозок, указаны расстояния между соответствующими пунктами. В процессе решения задачи в средней части этих клеток записывают значения хij, которые делятся на основные и не основные. Не основные хij в таблице-матрице не пишутся и считаются равными нулю. К основным относятся все хij >0, а также те из хij =0, которые записываются в матрице. Основные хij записанные в матрице, обычно называют загрузками, а клетки, в которых они находятся, — занятыми. Клетки матрицы без загрузок называют незанятыми. 2. Составление допустимого исходного плана. Решение задачи начинается с составления допустимого плана. Производится это способом минимального элемента по строке следующим образом. Сначала планируем перевозки с первого склада, записывая их в соответствующие клетки первой строки. Производим это следующим образом. Сначала полностью удовлетворяем потребность ближайшего потребителя Б3, записав в клетку с наименьшим расстоянием 40 т. Поскольку в пункте А1 остается еще 40 т, удовлетворяем потребность следующего ближайшего потребителя Б4, записав в соответствующую клетку нужные ему 30 т. Оставшиеся 10 т заносим в клетку А1 Б1 и переходим к следующей строке матрицы. Теперь груз второго отправителя А2 планируем к перевозке ближайшим из еще неудовлетворенных потребителей, записывая соответствующие объемы в клетки второй строки последовательно, начиная с клетки с наименьшим расстоянием, в клетку А2Б1 — 20 т и в клетку А2Б2 — 30 т. Перейдя к третьей строке матрицы, видим, что остался неудовлетворенным только один потребитель Б2. Планируем ему перевозку из А3, записав в клетку А3Б2 40 т. Вычисления закончены. Полученный допустимый план представлен в табл. 14. По этому плану перевозок потребность всех потребителей удовлетворяется полностью, а транспортная работа составит.

Р = 10*9+40*5+30*8+20*4+30*9+40*22 = 1760 тонно-километров.

Таблица 14.

При этом индексы Ui, записывают в клетки вспомогательного столбца, а индексы Vj — в клетки вспомогательной строки (табл. 13). Для определения индексов используют следующие правила:

• 1) индекс первой клетки вспомогательного столбца всегда равен нулю (U1 = 0);
• 2) для каждой занятой клетки матрицы сумма соответствующих ей индексов U и V (записанных против нее сверху и сбоку во вспомогательных клетках) равна расстоянию, указанному в данной клетке. Из последнего правила следует, что если у занятой клетки один из индексов известен, то другой равен разности ее расстояния и известного индекса, т. е.

Ui = Lij — Vj и Vj = Lij — Ui (1).

Запишем в матрицу индекс U1 = 0. Тогда у занятых клеток A1Б1, А1Б3 и А1Б4 один индекс известен и можно, используя равенство (1), определить индексы V1, V2 и V4 (табл. 15):

V1 = L11 — U1 = 9−0=9.

V3 = L13 — U1 = 5−0=5.

V4 = L14 — U1 = 8−0=8.

Теперь у занятой клетки А2Б1 известен индекс V1 и можно найти индекс.

U2= L22 — U2 = 4−9 = -5. После этого определяем индекс V2, а затем индекс U3:

V2=L22 — U2 = 9 — (-5) = -5 и U3 = L32 — V2 = 22 — 14 = 8.

Таблица 15.

• (U1 + V2 = 0 + 14) < (L12 = 15)
• (U2 + V3 = -5 + 5 = 0) < (L23 = 6)
• (U2 + V4 = -5 + 8 = 3) < (L24 = 5)
• (U3 + V1 = 8 + 9 =17) > (L31 = 16)
• (U3 + V3 = 8 + 5 = 13) > (L33 = 10)
• (U3 + V4 = 8 + 8) < (L34 = 18)

Составив цепочку, помечают знаком «+» ее нечетные вершины (считая первой вершину в потенциальной клетке), а четные знаком «—». Наименьшая из четных загрузок определяет величину перемещаемой загрузки. Уменьшив на эту величину объемы перевозок, записанные в клетках со знаком минус, и увеличив на ту же величину объемы клеток со знаком плюс, получают новый вариант плана с меньшей транспортной работой.

В рассматриваемом примере построена цепочка для потенциальной клетки А3Б3 и расставлены знаки (табл. 16).

прибыль стоимость симплексный потенциал.

Таблица 16.

Наименьшая среди четных загрузок (отмеченных знаком минус) равна 20 (в клетке А2Б1). Уменьшив на 20 загрузки клеток А1Б3, А2Б1 и А3Б2 и увеличив также на 20 загрузки клеток А3Б3, А1Б1 и А2Б2, получим новый план, представленный в табл. 17. По этому варианту плана транспортная работа составит 1700 тонно-километров, или на 60 тонно-километров меньше.

Таблица 17.

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

Из табл. 18 видно, что и этот план, как и предыдущий, не является оптимальным. Об этом говорит наличие в матрице потенциальной клетки А1Б2. Изменив уже известным способом загрузки в клетках, отмеченных вершинами вновь построенной цепочки, получаем новый план, представленный в табл. 19. Для его проверки на оптимальность приступаем к расчету индексов и убеждаемся, что все их определить не удается. Причиной этого является так называемое вырождение плана, т. е. уменьшение числа занятых клеток против необходимого. Дело в том, что все индексы могут быть найдены, и притом однозначно, только при строго определенном количестве занятых клеток, равном в общем случае m+n—1, где m—число пунктов отправления, n—число пунктов назначения. В нашей задаче m=3, а n=4. Следовательно, для определения всех индексов нужно иметь в матрице 3+4—1=6 занятых клеток. В табл. их только пять, поэтому индексы U3 V3 не удается определить.

Таблица 18.

Таблица 19.

Вырождение матрицы так же, как и излишнее количество занятых клеток, нарушают нормальную процедуру вычислений и их нужно устранять. Избавиться от вырождения можно путем записи в одной из незанятых клеток матрицы перевозки объемом 0 тонн. В табл. 13 нулевую загрузку можно поставить в одну из клеток А1Б3, А2Б3, А3Б1, А3Б2 и А3Б4. Легко проверить, что только эти клетки, став занятыми нулевой загрузкой, позволят найти недостающие индексы U3 и V3.

Лучше всего поставить нулевую перевозку в клетку с меньшим расстоянием, т. е. в клетку А1Б3. Теперь определив недостающие индексы, убеждаемся, что последний план является оптимальным, поскольку у всех незанятых клеток матрицы расстояния больше суммы соответствующих им индексов (табл. 20). Транспортная работа по этому плану составит 1600 тонно-километров.

Таблица 20.

В случае если число занятых клеток в матрице больше, чем m+n—1, поступают следующим образом. В табл. 16 — семь занятых клеток вместо необходимых шести (m+n-1=3+4—1=6). Наличие лишней занятой клетки приводит к тому, что индексы определяются неоднозначно. В первом случае U2=9—15= - 6, во втором U2=6—5= 1.

Таблица 21.

Уменьшение числа занятых клеток производится следующим образом. В матрице строят замкнутую цепочку из горизонтальных и вертикальных отрезков так, чтобы все ее вершины находились в занятых клетках (см. табл. 16). Такая цепочка в матрице с числом занятых клеток более m+n -1 всегда имеется. На вершинах цепочки, начиная с клетки, имеющей наименьшую загрузку, расставляют попеременно знаки минус и плюс, после чего загрузки со знаком минус уменьшают, а со знаком плюс увеличивают на величину наименьшей из них. В результате число занятых клеток уменьшится не менее чем на одну (табл. 22). При необходимости данную процедуру повторяют столько раз, сколько это необходимо для получения m+n -1 занятых клеток.

Таблица 22.