Введение

Планирование перевозок (транспортная задача). Цель данного планирования заключается в минимизации транспортных затрат.

Предположим, что некоторая фирма имеет 4 фабрики и 5 центров распределения ее товаров. Фабрики фирмы располагаются в разных городах и условно обозначены как «Фабрика 1», «Фабрика 2», «Фабрика 3» и «Фабрика 4». Объемы ежедневного производства товаров фабрик приведены в таблице 5.

Таблица 5

Центры распределения товаров фирмы располагаются в другой группе городов и их ежедневные потребности приведены в таблице 6.

Таблица 6

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

Таблица 7. Транспортные расходы

Необходимо так спланировать перевозки, чтобы минимизировать суммарные транспортные расходы.

Построим математическую модель данной задачи. Неизвестными в данной задаче являются объемы перевозок. Пусть x _ij – объем перевозок с i -й фабрики в j – й центр распределения. Функция цели – это суммарные транспортные расходы, т.е.

4 5

Z = ∑ ∑ c_ij x_ij

i=1 j=1

Где с _ij – стоимость перевозки единицы продукции с i -й фабрики в j – й центр распределения.

Неизвестные в данной задаче должны удовлетворять следующим ограничениям:

· Объемы перевозок не могут быть отрицательными

· Так как модель сбалансирована (суммарный объем произведенной продукции равен суммарному объему потребностей в ней), то вся продукция должна быть вывезена с фабрик, а потребности всех центров распределения должны быть полностью удовлетворены.

В результате имеем следующую модель:

Минимизировать:

4 5

Z = ∑ ∑ c_ij x_ij

i=1 j=1

При ограничениях:

∑ x_ij =b_j, j Є [1,5]

i=1

∑ x_ij =a_i, i Є [1,4]

j=1

x_ij ≥ 0_j, i Є [1,4], j Є [1,5]

где a_i – объем производства на i – й фабрике, bj – спрос в j – м центре распределения.

Для решения этой задачи с помощью средства Поиск решения введем данные, как показано ниже (рис. 32).

Рис. 32

В ячейки В3:F6 введены стоимость перевозок. Ячейки B10:F13 отведены под значения неизвестных (объемы перевозок). В ячейки G3:G6 введены объемы производства на фабриках, а в ячейки B7:F7 введены потребности в продукции в пунктах распределения. В ячейку G14 введена целевая функция =СУММПРОИЗВ(B3:F6;B10:F13)

В ячейки B14:F14 введены формулы, определяющие объем продукции, доставляемой в центры распределения.

В ячейки G10:G13 введены формулы, вычисляющие объем продукции, вывозимой с фабрик.

Теперь нужно выбрать команду Сервис ► Поиск решения и заполнить открывшееся диалоговое окно как показано на рис. 33.

Рис. 33.

С помощью кнопки Параметры следует вызвать диалоговое окно Параметры поиска решения и установить в нем флажок Линейная модель. Программа Поиска решения находит оптимальный план поставок продукции и соответствующие этому плану транспортные расходы (см. рис. 34).

Рис. 34.

Задачи на оптимизацию для самостоятельного решения.

Задача1.

Завод производит электронные приборы трех видов (прибор А, прибор В и прибор С), используя при сборке микросхемы трех типов (тип 1, тип 2 и тип 3). Расход микросхем задается следующей таблицей:8

Таблица 8.

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

Ежедневно на склад завода поступает 400 микросхем типа 1 и по 500 микросхем типов 2 и 3. Каково оптимальное соотношение дневного производства приборов каждого типа, если производственные мощности завода позволяют использовать запас поступивших микросхем полностью?

Сохраните найденное решение в виде сценария.

Продолжение предыдущей задачи.

Найдите оптимальное соотношение дневного производства приборов каждого типа, если стоимости приборов не одинаковы и составляют соответственно: Прибор А - 20ед., Прибор В – 40ед., Прибор С – 25ед. Сохраните найденное решение в виде сценария.

Продолжение предыдущей задачи.

Решите эту задачу, если имеются ограничения по сбыту приборов: Прибор А – 100шт., Прибор В – 80шт., Прибор С – 200шт. Сохраните найденное решение в виде сценария.

Задача2.

Фирма выпускает два типа деталей (А и Б). Для этого она закупает литье, подвергаемое токарной обработке, сверловке и шлифовке. Данные, характеризующие производительность станочного парка фирмы, приведены в таблице 9.

Таблица 9.

Каждая отливка, из которой изготавливают деталь А, стоит 20 рублей. Стоимость отливки для детали Б – 30 рублей. Продажная цена деталей равна, соответственно, 50 и 60 рублей. Стоимость часа станочного времени составляет по трем типам используемых станков 200, 140 и 175 рублей, соответственно. Предполагая, что можно выпускать для продажи любую комбинацию деталей А и Б, составить план выпуска продукции, обеспечивающий максимальную прибыль.

Задача 3.

В некотором регионе имеется 4 карьера по добыче и производству гравия для бетонных заводов и 5 заводов по производству бетона.

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

Производственные возможности карьеров по производству гравия (в условных единицах) приведены в таблице 10.

Таблица 10.

Потребности бетонных заводов в гравии (в условных единицах) приведены в таблице 11.

Таблица 11.

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

Таблица 12

[1] Суть этого метода легче всего пояснить на примере. Для имущества стоимостью 50000 руб. и сроком эксплуатации 5 лет при любой остаточной стоимости, меньшей 18000 руб., амортизация за первый год составит 50000/5*2, или 20000 руб., за второй год – (50000-20000)/5*2, или 12000 руб. То есть на самом деле амортизация равна удвоенной величине текущей балансовой стоимости имущества. В случае других значений коэффициента вместо 2 нужно подставлять соответствующее значение коэффициента.

[2] Подробнее параметры поиска рассмотрены в параграфе Параметры программы Поиск решения

[3] Если команда Поиск решения не активна, нужно произвести установку программы Поиск решения, для чего нужно выполнить команду Сервис ► Надстройки и в появившемся диалоговом окне установить флажок Поиск решения.

Введение

В науке, технике и экономике используются математические модели, которые общепринятым, формальным способом описывают характерные особенности систем и позволяют осуществлять достаточно надежное прогнозирование их поведения. Простейшими моделями могут выступать таблицы или графики связывающие величины воздействия на систему с величинами, отражающими ее реакцию на эти воздействия. Более высокий уровень моделей – уравнения, отражающие подобную связь (алгебраические, дифференциальные, интегральные и пр.). Свойства сложной системы отражают совокупностью различных уравнений. Для отражения конкретных условий функционирования систем используются условия однозначности (начальные условия при исследовании динамики систем и граничные условия, когда системы распределены в пространстве).

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

Имея математическую модель системы можно проводить прогнозирование ее поведения в различных ситуациях (проводить математическое моделирование системы или, как часто говорят, проводить вычислительный эксперимент). Разработка и исследование вычислительных алгоритмов, и их применение к решению кон­кретных задач составляет содержание огромного раздела современной математики — вычислительной математики.

Вычислительную математику определяют в широком смысле этого термина как раздел математики, включающий круг вопросов, связанных с использованием ПЭВМ, и в узком смысле — как теорию численных методов и алгоритмов решения поставленных математических задач.

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

Универсальность численных методов и развитие средств вычислительной техники привело к появлению большого количества алгоритмов и программ, ориентированных на решение конкретных вычислительных задач. Поэтому современному пользователю ПЭВМ чаще всего нет необходимости в самостоятельной разработке алгоритма и программы, а имеет смысл использовать готовый программный продукт разработанный на профессиональном уровне. Такого рода программные продукты оформляются в виде предопределенных процедур (подпрограмм) и хранятся в библиотеках, откуда их можно вызвать по имени и вставить в свою программу. Для обмена значениями данных между программой пользователя и подпрограммой используется аппарат формальных и фактических параметров. Таким образом, в программе пользователя зачастую оригинальным является только ввод исходных данных и вывод результатов счета в желаемой форме, а основные вычисления проводятся по библиотечным подпрограммам. Для грамотного выбора необходимой предопределенной процедуры пользователю необходимо разбираться в основных численных методах и алгоритмах, уметь оценивать точность получаемого решения и потребные ресурсы ПЭВМ.