Закрепление приемов построения моделей

 

Задача 1. Известен выпуск продукции на трёх заводах: 460, 340 и 300 тонн соответственно. Требования четырёх потребителей на эту продукцию составляют: 350, 200, 450 и 100 тонн. Известны также затраты на производство 1 единицы продукции на каждом заводе: 9, 8 и 2 руб. соответственно, а также матрица транспортных расходов на доставку 1 единицы продукции от i -го завода k -му потребителю.

 

 

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

Сравнить с оптимальным планом, построенным из условия минимизации только транспортных расходов.

Решение. Обозначим через x_ik объем поставки продукции от i -того завода k -тому потребителю. Данная транспортная задача является сбалансированной (460+340+300 = 350+200+450+100). Тогда ограничения на выпуск продукции будут выглядеть следующим образом:

(1)

Ограничения на потребление продукции:

(2)

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

 

(3)

 

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

 

(4)

 

Таким образом, целевая функция (4) и ограничения (1-3) представляют собой математическую модель для решения поставленной задачи.

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

(4`)

При этом все ограничения останутся прежними.

Задача 2. Строительный песок добывается в трёх карьерах и доставляется на четыре строительные площадки. Данные о производительности за день (a_i в тоннах), потребностях в песке строительных площадок (b_k в тоннах), затраты на добычу песка (d_i в руб./т) и транспортных расходах (c_ik) приведены в следующей таблице:

 

bk ai					di

 

Недостающее количество песка – 30 т в день – можно обеспечить следующими тремя путями:

I – увеличение производительности первого карьера, что повлечёт за собой дополнительные затраты в 3 руб. на добычу 1 т сверх плана;

II – увеличение производительности второго карьера с дополнительными затратами в 2 руб./т сверх плана;

III – эксплуатация нового карьера с общими запасами 30 тонн, затратами на добычу 5 руб./т и на транспортировку к указанным строительным площадкам: c₄₁ = 2, c₄₂ = 3, c₄₃ = 1, c₄₄ = 2 (руб./т).

Построить модель определения плана закрепления строительных площадок за карьерами и оптимального варианта расширения поставок песка.

Решение. Обозначим через x_ik объем поставки продукции от i -того карьера на k -тую строительную площадку. Данная транспортная задача не является сбалансированной (). Поэтому в задаче без дополнительных условий (I-III) ограничения на выпуск продукции будут выглядеть следующим образом:

 

(1)

 

Ограничения на потребление продукции:

(2)

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

 

. (3)

 

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

 

(4)

 

Варианты расширения поставок фактически необходимы для того, чтобы сбалансировать задачу и обеспечить потребности строительных площадок. Поэтому для того чтобы учесть данные варианты, введем новые переменные и изменим ограничения (1-2) и целевую функцию (4).

Пусть x_4k – объем поставки песка из нового четвертого карьера на k -ую строительную площадку; z₁ – объем дополнительного производства на первом карьере, z₂ – объем дополнительного производства на втором карьере. Тогда ограничения (1) будут заменены на следующие:

(1`)

.

Ограничения (2) на следующие:

 

(2`)

.

 

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

 

. (3`)

 

Целевая функция примет вид:

 

(4`)

 

Задача 3. Первый склад (S₁) имеет сталь двух марок: 3000 т марки «А» и 4000 т марки «Б». Второй склад (S₂) также имеет сталь двух марок: 5000 т марки «А» и 2000 т марки «Б». Сталь должна быть вывезена в два пункта потребления: в пункт P₁ необходимо поставить 2000 т стали марки «А», 3000 т марки «Б» и остальные 2000 т стали любой марки. Аналогично второй пункт потребления P₂ должен получить 6250 т стали, из них 1000 т стали марки «А» и 1500 т стали марки «Б». Известно, что 2000 т стали марки «А» могут быть заменены на 1600т стали марки «Б» (но не наоборот). Стоимость перевозок в рублях за тонну составляет: из пункта S₁ в пункты P₁ и P₂ 1 руб. и 1,5 руб., из пункта S₂ в P₁ и P₂ соответственно 2 руб. и 1 руб.

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

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

 

		в исходных единицах	в единицах стали марки «Б»
Запасы на складе S1	марка «А»
марка «Б»
Запасы на складе S2	марка «А»
марка «Б»
Потребность 1-го пункта потребления	марка «А»
марка «Б»
любой марки		1600*
Потребность 2-го пункта потребления	марка «А»
марка «Б»
любой марки		3000*

* В качестве стали «любой марки» логично выбрать сталь марки «А», которую затем можно заменить на меньшее количество стали марки «Б».

 

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

(1)

Ограничения на потребление стали марки «Б» (т.к. она не заменима маркой «А»):

(2)

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

 

(3)

 

Здесь 6200 и 5300 – общая потребность соответственно 1-го и 2-го пунктов потребления стали обеих марок, выраженная в единицах стали марки «Б» (подробнее – см. таблицу), а – коэффициент перевода стали марки «А» в сталь марки «Б».

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

 

. (4)

 

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

 

. (5)

 

Целевая функция (5) и ограничения (1-4) представляют собой математическую модель для решения поставленной задачи.

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

 

	Сборочная линия
Служащий 1 Служащий 2 Служащий 3 Служащий 4 Служащий 5

 

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

Решение. Введем переменные следующим образом: x_ik = 1, если i -тый служащий назначается на k -тую производственную линию, в противном случае x_ik = 0. Данная задача не является сбалансированной – количество служащих больше количества производственных линий. Тогда ограничения задачи будут выглядеть следующим образом:

(1)

– сотрудник не может быть назначен на две линии одновременно, кроме того, один из сотрудников останется не назначенным;

(2)

– на каждую линию обязательно будет назначен один сотрудник;

 

(3)

 

– ограничение на переменные по условию.

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

 

. (4)

1.3. Упражнения для самостоятельной работы

 

Задача 1. Построить модель формирования плана перевозок из условия доставки груза в кратчайший срок. Известны объёмы ресурсов у трёх поставщиков (30, 35, 40) и потребности в них у пяти потребителей (20, 34, 16, 10, 25), а также матрица

,

где t_ik – время, затрачиваемое на перевозку груза от i -го поставщика в k -тый пункт назначения.

Задача 2. На 3 сахарных завода доставляется сахарная свекла из 4-х совхозов. Максимальные мощности ее производства по первому, второму и четвертому совхозам равны соответственно 250, 300, и 600 тыс. тонн. Минимальное производство сахарной свеклы во втором совхозе составляет 100 тыс. тонн. Себестоимость производства свеклы по совхозам составляет соответственно 15, 20, 35 и 10 руб. за центнер. Стоимость перевозки 1 тонны свеклы на каждый завод задана матрицей:

 

Составить математическую модель оптимального производства сахарной свеклы и ее перевозки на заводы.

Задача 3. На заводах, расположенных в точках h₁ и h₂, из сырья, добываемого в месторождениях i₁ и i₂, изготавливаются два сорта продукции А и В для пунктов потребления j₁ и j₂. Потребности пункта j₁ могут быть удовлетворены при помощи 1500 единиц продукции сорта А, из которых 1000 единиц «заменимы» В, то есть вместо каждой единицы сорта А можно использовать две единицы сорта В. Для пункта j₂ требуется 1200 единиц продукта сорта А, из которых заменимыми В являются 900 единиц.

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

Себестоимость добычи сырья в обоих месторождениях одинакова – 60 руб., а провоз единицы сырья обходится: из пункта i₁ в пункт k₁ – 60 руб., в пункт k₂ – 120 руб.; из i₂ в k₁ – 180 руб., в k₂ – 60 руб.

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

Перевозка готовой продукции обходится в расчёте на единицу продукции (любого сорта): при снабжении заводом k₁ потребителей в j₁ в 30 руб.; при снабжении тех же потребителей заводом k₂ – 60 руб.; при доставке в пункт i₂ продукции из k₁ расходы составляют 50 руб., при доставке в тот же пункт продукции из k₂ соответствующая величина составляет 70 руб.

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

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

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

Задача 4. Нефтяная компания в ходе аукциона получила в свое распоряжение четыре месторождения. Геологоразведочные работы показали, что в районе месторождения М₁ можно было бы пробурить не более 30 скважин, месторождения М₂ – не более 80, М₃ – не более 10, М₄ – не более 20. К сожалению, не существует гарантии, что все пробуренные скважины будут производительны. Вероятности успешного завершения буровых работ на всех месторождениях приведены в таблице:

 

 

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

 

 

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

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

В следующей таблице приведены затраты на транспортировку труб от каждого склада до каждого из месторождений (тыс. руб. за 1 трубу)

 

 

месторождения   склады	М1	М2	М3	М4
S1 S2 S3 S4	0,5 0,01 0,8 0,5	0,3 0,4 0,6 0,7	0,6 0,1 0,6 0,6	0,02 0,4 1,1 0,1

 

 

Компания имеет возможность оплатить расходы, связанные с разработкой всех месторождений.

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

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

 

(тыс. долларов)

проект подрядчик	Р1	Р2	Р3
С1 С2 С3

 

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

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

 

 

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

 

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

Каким образом следует сделать назначения для того, чтобы максимизировать общий потенциальный объём продаж?

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

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

 

Компания	Классы
2 М 3 М 5 М 7 М 8 М 12 М 13 М

 

Распределить по две компании на класс так, чтобы минимизировать суммарное значение «точек ранжирования».

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

Распределительные модели