Экономико-математическая модель задачи

Обозначим через Хij количество единиц i-х ресурсов необходимых для удовлетворения j-х потребностей. Задача состоит в определении (m´n) переменных Xij - ых, удовлетворяющих ограничениям:

Экономико-математическая модель задачи - student2.ru

Оптимизируем функцию цели

Экономико-математическая модель задачи - student2.ru (4)

В зависимости от конкретного характера задачи может варьироваться и конкретное содержание, и размерность величин ai, bj, Cij, λij.

Например. Если λij будет представлять число единиц i-го ресурса, затраченных на удовлетворение единицы j-й потребности, тогда уравнения (1) и (2) будут иметь вид:

Экономико-математическая модель задачи - student2.ru

Тогда функция цели будет выглядеть

Экономико-математическая модель задачи - student2.ru

Если Сij означает эффективность, то f(x) → max, если затраты, то функция цели f(x) → min.

Распределительную задачу можно свести к транспортной в следующих случаях:

1) когда все λij при любых i и j =const. Тогда распределительная задача относится к классу простых распределительных задач­­;

2) задачи с однородными ресурсами. В этом случае наблюдается замена λij в модели на λi;

3) задачи с пропорциональными ресурсами. Здесь существует пропорция для различных ресурсов: Экономико-математическая модель задачи - student2.ru

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

1) Простые распределительные задачи

Найти оптимальное распределение 3-х видов механизмов, имеющихся в количестве: а­1 = 45 шт., а2 = 20 шт., а3 = 35 шт.; между 4-мя участками работ, потребности которых соответственно равны: b1 = 10 шт., b2 = 20 шт., b3 = 30 шт., b4 = 40 шт. при следующей матрице производительности (изд./час) каждого из механизмов на каждом из участков:

Нулевые элементы означают, что данный механизм на данном участке работы не может быть использован.
Экономико-математическая модель задачи - student2.ru

Обозначим через Xij­ – количество механизмов i-го на j-ой работе (участке); Экономико-математическая модель задачи - student2.ru - ресурсы (механизмы); Экономико-математическая модель задачи - student2.ru - потребности.

- распределение всех имеющихся механизмов по всем работам - удовлетворение потребности в механизмах по всем работам - условие неотрицательности результата
Экономико-математическая модель задачи - student2.ru

- максимум производительности
Экономико-математическая модель задачи - student2.ru

Тип механизма Участки Наличие
I Х11 Х12 Х13 Х14
II Х21 Х22 Х23 Х24
III Х31 Х32 Х33 Х34
Потребность Экономико-математическая модель задачи - student2.ru


Экономико-математическая модель задачи - student2.ru

Экономико-математическая модель задачи - student2.ru

Функция цели f(x) = 5x11+4х12+5х14+3х21+ 5х22+ 3х23+ 6х32+ 7х33+ 6х34→max

Экономико-математическая модель задачи - student2.ru

Экономико-математическая модель задачи - student2.ru

Рис. 1. Ввод математической модели в Excel

Экономико-математическая модель задачи - student2.ru

Экономико-математическая модель задачи - student2.ru

Рис. 2. Установка ограничений и параметров задачи

Экономико-математическая модель задачи - student2.ru

Рис. 3. Результат решения задачи

План распределения оборудования

Тип механизма Участки Приобретено, шт
I
II
III
Установлено, шт Производительность 565 изд/час

2). Распределительные задачи с однородными ресурсами

Ресурсы ai ( Экономико-математическая модель задачи - student2.ru ) однородные и взаимозаменяемые, потребности bj ( Экономико-математическая модель задачи - student2.ru ) разнородные, числа λij = λj указывают количество единиц j-й потребности, которая может быть удовлетворена единицей любого ресурса. Величины Сij характеризуют эффективность i-го ресурса при удовлетворении им j-й потребности.

Если через Xij обозначим количество единиц i-го ресурса, направляемых для удовлетворения j-й потребности, то мы придём к модели (1) - (4), в которой упростится ограничение (2): Экономико-математическая модель задачи - student2.ru

Ограничение (2) разделим почленно на λj и введем обозначение Экономико-математическая модель задачи - student2.ru .

Получаем следующую систему уравнений:

Экономико-математическая модель задачи - student2.ru

Экономико-математическая модель задачи - student2.ru

К подобным моделям (5) - (8) приводятся и задачи с разнородными, но взаимозаменяемыми ресурсами и однородными потребностями. В этом случае задаются величины λi, характеризующие количество единиц потребности, которая может быть удовлетворена единицей i-го ресурса.

Задача. Ресурсы угля 3-х сортов составляют 300, 800 и 400 тонн. Их теплотворная способность соответственно равна 1800, 2500 и 3000 кал/кг. Суммарные затраты на добычу и доставку каждого сорта угля до каждого из 4-х потребителей в ден. ед. за тонну задаются следующей матрицей

Экономико-математическая модель задачи - student2.ru .

Уголь сжигается в печах, принадлежащих 4-м потребителям, потребность которых составляет 750, 920, 1100 и 800 млн. калорий.

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

Решение. Допустим Хij – количество угля i-го сорта поставляемое j-му потребителю. Тогда:

Экономико-математическая модель задачи - student2.ru

Экономико-математическая модель задачи - student2.ru

Функция цели f(x) = 27x11 +36х12 +18х13+18х14 +30х21+ 25х22+ 15х23+ 20х24 + +36х31+ 30х32+ 24х33 +21х34→ min.

Поскольку в данном виде задача не может быть приведена к транспортному виду, введем переобозначение: Хij – количество тепловой энергии, получаемое от i-го сорта угля в j-й печи. Тогда:

Экономико-математическая модель задачи - student2.ru Σ=3570 (потребность в энергии)

Поскольку предложение превышает спрос, необходимо ввести фиктивного потребителя, спрос которого составит 3740-3570=470 млн. кал (предложение энергии)
Экономико-математическая модель задачи - student2.ru Экономико-математическая модель задачи - student2.ru

Экономико-математическая модель задачи - student2.ru

В итоге получаем задачу транспортного типа:

распределение предложения по потребителям   обеспечение потребности в энергии   минимальные общие затраты
Экономико-математическая модель задачи - student2.ru

Экономико-математическая модель задачи - student2.ru

Экономико-математическая модель задачи - student2.ru

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

Экономико-математическая модель задачи - student2.ru

Рис. 4. Исходные данные для Поиска решения:

Экономико-математическая модель задачи - student2.ru

Рис. 5. Решение задачи транспортного типа в Excel

При обратном переводе поставок в тонны задача имеет уже не целочисленное решение.

Экономико-математическая модель задачи - student2.ru

Рис. 6. Окончательный вид решения задачи

3) Распределительные задачи с пропорциональными

ресурсами

В этой задаче ресурсы Экономико-математическая модель задачи - student2.ru и потребности Экономико-математическая модель задачи - student2.ru неоднородные, но в матрице || λij || элементы, которой устанавливают связь между единицей ресурса и потребности, строки пропорциональны:

Экономико-математическая модель задачи - student2.ru , отсюда Экономико-математическая модель задачи - student2.ru для всех Экономико-математическая модель задачи - student2.ru ,

где ki – индексы i-х ресурсов (или коэффициент пропорциональности); Экономико-математическая модель задачи - student2.ru - величины, относящиеся к ресурсу, выбранному за эталон.

Рассмотрим ограничение (1) задачи (1) – (4):

Экономико-математическая модель задачи - student2.ru .

Умножим левую и правую части этого выражения на ki, получим:

Экономико-математическая модель задачи - student2.ru .

Произведем замену в выражении (2):

Экономико-математическая модель задачи - student2.ru

Разделим левую и правую части этого выражения на λij, получим:

Экономико-математическая модель задачи - student2.ru

Проведем пересчет ресурсов и потребностей в условные единицы. Для этого введем обозначения:

Экономико-математическая модель задачи - student2.ru

Тогда задача примет вид:

Экономико-математическая модель задачи - student2.ru

Экономико-математическая модель задачи - student2.ru

Задача. На предприятии имеется 3 типа оборудования, на котором может вырабатываться четыре вида изделий. Учитывая, что фонд рабочего времени каждой из групп оборудования соответственно равен 90, 210 и 180 станко-часов, составить такой план их загрузки, при котором общая себестоимость выпускаемой продукции являлась бы минимальной. На продукцию предприятия поступили заказы в количестве по типам продукции, соответственно 1200, 900, 1800 и 840 штук. Производительность каждого из типов оборудования и себестоимость изделий приведены в таблице:

Тип станка Производительность станков при изготовлении продукции, шт/час Себестоимость единицы изделий, ден. ед. Фонд времени (станко-час)
План, шт.          

распределение ресурса оборудования по изделиям
Решение. Введем обозначение Хij – время загрузки станков i-го типа изготовлением продукции j-го типа. Тогда модель примет вид:

Распределение фонда времени оборудования по видам продукции
Экономико-математическая модель задачи - student2.ru

выполнение плана выпуска продукции
Экономико-математическая модель задачи - student2.ru

минимизация затрат:

Экономико-математическая модель задачи - student2.ru

Производительность станков пропорциональна (по строкам), следовательно, задачу можно свести к транспортной:

Экономико-математическая модель задачи - student2.ru

Введем переобозначения и произведем замену переменных: Экономико-математическая модель задачи - student2.ru тогда получаем

разделим левую и правую части выражений на величины  
Экономико-математическая модель задачи - student2.ru

Перепишем первую систему ограничений с учетом переобозначений:

Экономико-математическая модель задачи - student2.ru

Функция цели после преобразования примет вид:

Экономико-математическая модель задачи - student2.ru

После необходимых вычислений получим:

Экономико-математическая модель задачи - student2.ru

Экономико-математическая модель задачи - student2.ru

Экономико-математическая модель задачи - student2.ru

Произведем проверку: открытую или закрытую форму имеет данная задача транспортного типа. Для этого сравним суммарный спрос: 90+105+60=255 и суммарное предложение 50+30+100+20=200. Поскольку задача имеет открытую форму, и предложение превышает спрос, введем фиктивный заказ на пятый (дополнительный) вид продукции.

спрос на фиктивный вид продукции, равный разнице между суммарным предложением и суммарным спросом
Экономико-математическая модель задачи - student2.ru

Экономико-математическая модель задачи - student2.ru Экономико-математическая модель задачи - student2.ru

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

Экономико-математическая модель задачи - student2.ru

Решение задачи можно представить в виде матрицы:

или, проведя обратное преобразование, получим
Экономико-математическая модель задачи - student2.ru Экономико-математическая модель задачи - student2.ru

Анализ результатов: на первом станке вырабатывают первые три типа продукции в течение 50, 30 и 10 часов соответственно. На втором станке вырабатываются третий и четвёртый виды продукции, затрачивая соответственно 170 и 40 станко-часов. На третьем станке вырабатывает третий тип продукции в течении 15 часов, кроме того, на третьем станке можно было бы выработать еще дополнительный заказ, если бы он не был фиктивным. При этом остаток недоиспользованного фонда времени третьего станка – 165 часов. Функция цели f(x)= 11250 ден. ед.- минимальная себестоимость всего вырабатываемого объёма продукции.

Наши рекомендации