Книги по разным темам Pages:     | 1 | 2 | 3 | 4 | 5 |   ...   | 6 |

+ xx + x31 11 + xx + x32 12 (2) + xx + x33 13 + xx + x34 14 Неотрицательностьобъемов поставок:

,0 ix = 1..3,k = 1..ik (3) Задача состоит в минимизации суммарных расходов на производство и перевозку. Поэтому в качестве целевой функции получим следующее выражение:

( + xx11 12 + x13 + x14 )+ 32 (x21 + x22 + + xx23 24 )+ (x31 + x32 + x33 + x34 )+ 34 xx +++ x13 + 52 x14 + 11 ++ xx + + 46 xx + 21 22 23 ++ 53 xx 9x33 ++ 4x34 min 31 (4) Варианты расширения поставок фактически необходимы для того, чтобы сбалансировать задачу и обеспечить потребности строительных площадок. Поэтому для того чтобы учестьданные варианты, введем новые переменные и изменим ограничения (1-2) и целевую функцию (4).

Пустьx4k - объем поставки песка из нового четвертого карьера на k-ую строительную площадку; z1 - объем дополнительного производства на первом карьере, z2 - объем дополнительного производства на втором карьере.

Тогда ограничения (1) будут заменены на следующие:

+ xx + x13 + x14 46 + z11 + xx + x23 + x24 34 + z21 (1`) + xx + x33 + x34 31 + xx + x43 + x44 41 Ограничения (2) на следующие:

+ xx + x31 = 11 + xx + x32 = 12 (2`) + xx + x33 = 13 + xx + x34 = 14 Неотрицательностьобъемов поставок:

,0 ix = 1..4, k = 1..4; z, z21 ik (3`) Целевая функция примет вид:

( + xx11 12 + x13 + x14 )+ 52 z1 + 3(x21 + x22 + x23 + x24 )+ 5z2 + (x31 + x32 + + xx33 34 )+ ++ 34 xx + 2x13 + 5x14 + 11 ++ xx + + 46 xx + 21 22 23 ++ 53 xx 9 ++ 4xx + 31 32 33 ++ 32 xx + x43 + 2x44 min 41 (4`) Задача 3. Первый склад (S1) имеет сталь двух марок: 3000 т марки А и 4000 т марки Б. Второй склад (S2) также имеет стальдвух марок: 5000 т марки А и 2000 т марки Б. Сталь должна быть вывезена в два пункта потребления: в пункт P1 необходимо поставить 2000 т стали марки А, т марки Б и остальные 2000 т стали любой марки. Аналогично второй пункт потребления P2 должен получить 6250 т стали, из них 1000 т стали марки А и 1500 т стали марки Б. Известно, что 2000 т стали марки А могут бытьзаменены на 1600т стали марки Б (но не наоборот). Стоимость перевозок в рублях за тонну составляет: из пункта S1 в пункты P1 и P2 1 руб.

и 1,5 руб., из пункта S2 в P1 и P2 соответственно 2 руб. и 1 руб.

Составитьмодельоптимального плана перевозок.

g Решение. Обозначим через xik объем поставки стали g-той марки из i-того склада на k-тый пункт потребления. Подобные задачи (со взаимозаменяемыми ресурсами) решаются путем выражения объемов одного ресурса в единицах другого. Например, в данной задаче выпишем все ограничения в единицах стали марки Б. В таблице приведены основные параметры задачи, выраженные в единицах стали марки Б:

в исходных в единицах стали единицах марки Б марка А 3000 Запасы на складе Sмарка Б 4000 марка А 5000 Запасы на складе Sмарка Б 2000 марка А 2000 Потребность 1-го пункта марка Б 3000 потребления любой марки 2000 1600* марка А 1000 Потребность 2-го пункта марка Б 1500 потребления любой марки 3750 3000* * В качестве стали любой марки логично выбрать сталь марки А, которую затем можно заменитьна меньшее количество стали марки Б.

Как видим, общая потребность в стали обоих пунктов потребления составляет 11500 тонн (в единицах стали марки Б), в то время как общий запас (обоих складов) составляет 12400 тонн. Задача не является сбалансированной. Тогда ограничения на наличие ресурсов будут выглядеть следующим образом:

AA xx + 11 BB xx + 11 (1) AA xx + 21 BB xx + 21 Ограничения на потребление стали марки Б (т.к. она не заменима маркой А):

BB xx + 11 (2) BB xx + 12 Cталь марки А, как и остаток любой марки, могут быть заменены сталью марки Б, поэтому к ограничениям (2) для каждого склада необходимо добавитьограничения на общее количество поставляемой стали всех марок, выраженное в единицах стали марки Б:

AA B B,0 8( xx11 21)++ (x11 + x21)= (3) AA B B,0 8( xx12 22)++ (x12 + x22)= Здесь 6200 и 5300 - общая потребность соответственно 1-го и 2-го пунктов потребления стали обеих марок, выраженная в единицах стали марки Б (подробнее - см. таблицу), а,0 8 = - коэффициент перевода стали марки А в сталь марки Б.

Неотрицательностьобъемов поставок:

g,0 ix = 1..2,k = 1..2, g {"А "," Б"} ik (4) Задача состоит в минимизации суммарных расходов на производство и перевозку. Поэтому в качестве целевой функции получим следующее выражение:

BA A B A B A B ( xx11 11)++,1 5(x12 + x12)+ 2(x21 + x21)+(x22 + x22) min (5) Целевая функция (5) и ограничения (1-4) представляют собой математическую модель для решения поставленной задачи.

Задача 4. Компания Beta Motor Company имеет 4 различных сборочных линии на своём главном заводе. Управляющий производством имеет служащих и желает назначить по одному служащему к каждой из сборочных линий. Каждый из этих служащих может работать на любой сборочной линии, но с различными затратами, связанными с индивидуальным опытом и мастерством. Эти затраты приведены в таблице:

Сборочная линия 1 2 3 Служащий 1 23 19 22 Служащий 2 18 22 20 Служащий 3 25 20 22 Служащий 4 20 24 24 Служащий 5 16 18 20 Каким образом следует управляющему производством прикрепить служащих к сборочным линиям с тем, чтобы минимизировать общие затраты Решение. Введем переменные xik {,0 1} следующим образом: xik = 1, если iтый служащий назначается на k-тую производственную линию, в противном случае xik = 0. Данная задача не является сбалансированной - количество служащих больше количества производственных линий. Тогда ограничения задачи будут выглядеть следующим образом:

,1 ix = 1.. ik k =(1) - сотрудник не может бытьназначен на две линии одновременно, кроме того, один из сотрудников останется неназначенным;

,1 kx == 1.. ik i=(2) - на каждую линию обязательно будет назначен один сотрудник;

xik {,0 1} (3) - ограничение на переменные по условию.

Задача состоит в минимизации общих затрат на производство. Поэтому в качестве целевой функции получим следующее выражение:

23 +19xx11 12 13 14 + + 22 + 27xx 18 ++ 22xx + 20x23 + 18x24 + 21 25 ++ 20xx + 22x33 + 30x34 + 31 20 ++ 24xx + 24x43 + 28x41 16 ++ 18xx + 20x53 + 25x54 min 51 (4) 2.3. Упражнения для самостоятельной работы 1. Построить модель формирования плана перевозок из условия доставки груза в кратчайший срок. Известны объёмы ресурсов у трёх поставщиков (30, 35, 40) и потребности в них у пяти потребителей (20, 34, 16, 10, 25), а также матрица 62 3 4 (tT )== 651 9 7, ik 43 1 6 где tik - время, затрачиваемое на перевозку груза от i-го поставщика в k-тый пункт назначения.

2.У трёх поставщиков есть цемент нескольких видов и марок.

Коэффициент Марки Количество Поставщик Виды цемента перевода в цемента цемента, кг марку л400 500 2560 1,Портландцемент 400 4000 1,А400 5000 1,Шлакопортландцемент 300 1800 0,Портландцемент 400 1000 1,А2 400 1000 1,Шлакопортландцемент 300 1210 0,Портландцемент 500 3240 1,АШлакопортландцемент 400 5000 1,Известен спрос потребителей на цемент по видам спроса.

Потре- Вид спроса Объём бители спроса, кг Портландцемент марки 500 Портландцемент марок 400 или 500 ВЦемент любого вида и марки Потре- Вид спроса Объём бители спроса, кг Портландцемент марок 400 или В2 Портландцемент или шлакопортландцемент марок 400 или Портландцемент марки 500 В Цемент любого вида и марки Затраты на перевозку одной тонны цемента (любого вида) от каждого поставщика до каждого потребителя:

потребители В1 В2 Впоставщики А1 12 35 А2 20 25 А3 18 9 Составить модель формирования плана перевозки цемента, минимизирующего транспортные расходы на перевозку.

3. На 3 сахарных завода доставляется сахарная свекла из 4-х совхозов.

Максимальные мощности ее производства по первому, второму и четвертому совхозам равны соответственно 250, 300, и 600 тыс. тонн.

Минимальное производство сахарной свеклы во втором совхозе составляет 100 тыс. тонн. Себестоимостьпроизводства свеклы по совхозам составляет соответственно 15, 20, 35 и 10 руб. за центнер. Стоимостьперевозки 1 тонны свеклы на каждый завод задана матрицей:

97 102 C = 53 15 17 Составить математическую модель оптимального производства сахарной свеклы и ее перевозки на заводы.

4. На заводах, расположенных в точках h1 и h2, из сырья, добываемого вместорождениях i1 и i2, изготавливаются два сорта продукции А и В для пунктов потребления j1 и j2. Потребности пункта j1 могут быть удовлетворены при помощи 1500 единиц продукции сорта А, из которых 1000 единиц заменимы В, то естьвместо каждой единицы сорта А можно использовать две единицы сорта В. Для пункта j2 требуется 1200 единиц продукта сорта А, из которых заменимыми В являются 900 единиц.

Из единицы сырья может бытьполучено или две единицы продукта А, или четыре единицы продукта В.

Себестоимость добычи сырья в обоих месторождениях одинакова - руб., а провозединицы сырья обходится: из пункта i1 в пункт k1 - 60 руб., в пункт k2 - 120 руб.; из i2 в k1 - 180 руб., в k2 - 60 руб.

Расходы по изготовлению единицы продукции сорта А на заводах k1 и k2 составляют (без расходов по добыче и доставке сырья) соответственно руб. и 60 руб. Расходы по изготовлению единицы продукции сорта В и на заводе k1, и на заводе k2 составляют 15 руб.

Перевозка готовой продукции обходится в расчёте на единицу продукции (любого сорта): при снабжении заводом k1 потребителей в j1 в руб.; при снабжении тех же потребителей заводом k2 - 60 руб.; при доставке в пункт i2 продукции из k1 расходы составляют 50 руб., при доставке в тот же пункт продукции из k2 соответствующая величина составляет 70 руб.

Максимально возможный объём добычи сырья в месторождении i1 - 500 ед., i2 - 1000 ед.

Верхние границы возможных масштабов производства готовой продукции составляют для завода k1: 800 единиц продукции сорта А и единиц сорта В, для завода k2 - 700 единиц по сорту А и 1600 единиц по сорту В. При этом производственная программа для завода k1 должна предусматривать производство не менее 600 единиц продукции сорта А.

Требуется составитькомплексный план добычи сырья в пунктах i1 и i2, переработки его на заводах k1 и k2 и доставки готовой продукции потребителям в j1 и j2, который обеспечил бы полное удовлетворение потребностей при наименьших производственных и транспортных расходах.

5. Нефтяная компания в ходе аукциона получила в свое распоряжение четыре месторождения. Геологоразведочные работы показали, что в районе месторождения М1 можно было бы пробурить не более 30 скважин, месторождения М2 - не более 80, М3 - не более 10, М4 - не более 20. К сожалению, не существует гарантии, что все пробуренные скважины будут производительны. Вероятности успешного завершения буровых работ на всех месторождениях приведены в таблице:

Вероятность Стоимостьбурения Количество Месторождения успешного одной скважины, обсадных труб на завершения бурения млн. руб. одну скважину М1 50% 12 М2 90% 5 М3 60% 10 М4 80% 8 В данной таблице также приведена полная стоимость бурения одной скважины, а также количество обсадных труб, необходимых для одной скважины. Обсадные трубы требуются для подготовки скважины к эксплуатации, поэтому они используются только в случае успешного бурения.

Компания имеет собственные запасы обсадных труб, которые находятся на двух складах компании S1, S2 и S2 в количествах 1500, 850 и 2000 штук соответственно. Кроме того, в случае необходимости трубы могут бытьзакуплены у производителя, имеющего собственный склад S4 по цене тыс. руб. за штуку в количестве не более 2500.

В следующей таблице приведены затраты на транспортировку труб от каждого склада до каждого из месторождений (тыс. руб. за 1 трубу) месторождения М1 М2 М3 Мсклады S1 0,5 0,3 0,6 0,S2 0,01 0,4 0,1 0,S3 0,8 0,6 0,6 1,S4 0,5 0,7 0,6 0,Компания имеет возможность оплатить расходы, связанные с разработкой всех месторождений.

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

6. Инспектор компании Отеда имеет 3 различных проекта строительства дорог каждый из которых был рассчитан на всё лето. Инспектор, хочет, чтобы проекты были завершены к концу лета и средства на эти проекты изыскивались на месте. В результате были найдены три подрядчика, каждый из которых предлагал цену на каждые из трёх проектов, которая показана в следующей таблице.

(тыс. долларов) проект Р1 Р2 Рподрядчик С1 14 16 С2 18 14 С3 19 17 Необходимо распределить контракты таким образом, чтобы минимизироватьобщие затраты по всем проектам, предполагая, что каждый подрядчик может выполнить ровно один проект.

7. Компания имеет 5 новых районов продаж и 6 коммивояжёров, пригодных, чтобы назначить их в эти районы. Эти районы продаж достаточно малы, так что для каждого района требуется только один человек.

Данные относительно этих районов продаж и коммивояжёров даны ниже.

Район продаж А1 А2 А3 А4 АГодовой объём потенциальных 5,2 7,0 6,4 4,8 5,продаж (в 10000 долл.) Коммивояжёры 1 2 3 4 5 Оценка степени 75 60 55 80 50 захвата риска (%) Проценты представляют оценку доли потенциальных продаж каждым коммивояжёром, если бы они работали в одинаковых условиях. Проценты отражают различия в способностях коммивояжеров осуществлятьпродажи.

Каким образом следует сделать назначения для того, чтобы максимизироватьобщий потенциальный объём продаж 8. 7 классов школы бизнеса собираются посетить 14 местных компаний. Каждый класс будет разделён на 2 группы и каждая группа посетит одну компанию. Задача заключается в том, чтобы распределить компании между группами таким образом, чтобы наилучшим образом отразитьжелание входящих в них студентов.

В каждой группе было проведено голосование и опрос для того, чтобы разработать перечень предпочтений для 14 компаний: л1 означает наиболее предпочтительна, л14 - наименее предпочтительна.

Предпочтения каждого из семи классов приведены в таблице ниже:

Классы Компания 1 2 3 4 5 6 1 11 10 11 14 13 6 2 М 5 4 3 4 6 4 3 М 2 2 4 3 3 7 4 14 13 12 10 14 12 5 М 1 1 1 2 1 1 6 9 12 7 6 11 9 7 М 6 7 9 7 2 5 8 М 10 14 8 9 8 11 9 13 11 13 12 12 13 10 12 8 14 13 10 14 11 4 6 2 1 7 3 12 М 3 3 6 5 4 2 13 М 7 9 5 8 5 8 14 8 5 10 11 9 10 Распределить по две компании на класс так, чтобы минимизировать суммарное значение точек ранжирования.

Используя тот же самый метод, переделатьраспределение так, чтобы каждому классу досталось по одной промышленной компании (обозначенной М в приведённой таблице) и одной компании, занятой в сфере услуг.

Pages:     | 1 | 2 | 3 | 4 | 5 |   ...   | 6 |    Книги по разным темам