Методика выполнения в Microsoft Excel. 1. Запустите программу Excel (Пуск ®Программы®Microsoft Excel) и создайте рабочую книгу

1. Запустите программу Excel (Пуск ® Программы ® Microsoft Excel) и создайте рабочую книгу.

2. Создайте новый рабочий лист «Организация производства 2».

3. В ячейки E2, E3, иE4 занесите дневной запас микросхем – числа 500, 400, и 400 соответственно.

4. В ячейки B5, C5 и D5 занесите нули – в дальнейшем значения этих ячеек будут подобраны автоматически.

5. В ячейках диапазона A1:D4 разместите таблицу расхода комплектующих.

6. В ячейках F2:F4 нужно указать формулы для расчета расхода микросхем по типам. В ячейке F2 формула будет иметь вид =$B$5*B2+$C$5*C2+$D$5*D2, а остальные формулы можно получить методом автозаполнения (обратите внимание на использование абсолютных и относительных ссылок).

7. В ячейку F5 занесите формулу, вычисляющую общее количество произведенных приборов: для этого выделите диапазон B5:D5 и щелкните на кнопке Автосумма на стандартной панели инструментов.

8.Дайте команду Сервис®Поиск решения – откроется диалоговое окно Поиск решения.

9. В поле Установить целевую укажите ячейку, содержащую оптимизируемое значение (F5). Установите переключатель Равной максимальному значению (требуется максимальный объем производства).

10. В поле Изменяя ячейки задайте диапазон подбираемых параметров – B5:D5.

11. Необходимо добавить ограничения:

ü Расход микросхем не должен превышать их запас.

ü Количество выпускаемых приборов должно быть целым числом.

ü Число производимых приборов неотрицательно

12. Чтобы определить набор ограничений, щелкните на кнопке Добавить. В диалоговом окне Добавление ограничения в поле Ссылка на ячейку укажите диапазон F2:F4. В качестве условия задайте <=. В поле Ограничение задайте диапазон E2:E4. Это условие указывает, что дневной расход комплектующих не должен превосходить запасов. Щелкните на кнопке ОК.

13. Снова щелкните на кнопке Добавить. В поле Ссылка на ячейку укажите диапазон B5:D5. В качестве условия задайте >=. В поле Ограничение задайте число 0. Это условие указывает, что число производимых приборов неотрицательно. Щелкните на кнопке ОК.

14. Снова щелкните на кнопке Добавить. В поле Ссылка на ячейку укажите диапазон B5:D5. В качестве условия выберите пункт цел. Это условие не позволяет производить доли приборов. Щелкните на кнопке ОК.

15. Щелкните на кнопке Выполнить. По завершении оптимизации откроется диалоговое окно Результаты поиска решения.

16. Установите переключатель Сохранить найденное решение, после чего щелкните на кнопке ОК.

17. Проанализируйте полученное решение. Кажется ли оно очевидным? Проверьте его оптимальность, экспериментируя со значениями ячеек B5:D5. Чтобы восстановить оптимальные значения, можно в любой момент повторить операцию поиска решения.

18. Сохраните рабочую книгу.

Глава 2. Транспортная задача

Под термином "транспортные задачи" понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов.

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

· прикрепление потребителей ресурса к производителям;

· привязка пунктов отправления к пунктам назначения;

· взаимная привязка грузопотоков прямого и обратного направлений;

· отдельные задачи оптимальной загрузки промышленного оборудования;

· оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.

Цели

В данном разделе рассматривается задача транспортировки продукта, который в определенных количествах предлагается различными производителями. Известны потребности нескольких потребителей в этом продукте. Требуется определить, от каких производителей и в каких объемах должны получать продукт потребители. Поставки должны осуществляться таким образом, чтобы совокупные издержки на транспортировку продукта были минимальными.

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

• замкнутую и открытую транспортные задачи;

• транспортную задачу с запретами;

• транспортную задачу с фиксированными перевозками;

• транспортную задачу с ограничениями на пропускную способность;

• транспортную задачу с фиксированными доплатами;

Модели

Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения.

Имеются m пунктов отправления груза А₁, А₂,..., А_m и объемы отправления по каждому пункту a₁, a₂,..., a_m.

Известна потребность в грузах b₁, b₂,...,b_n по каждому из n пунктов назначения B₁, B₂,..., B_n.

Задана также матрица стоимостей с_ij, (i=1,...,m, j=1,...,n) доставки груза из пункта i в пункт j.

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

В общем виде исходные данные представлены в табл. 1.

Таблица 1

Исходные данные

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

Если такого равенства нет (потребности выше запасов или наоборот), задачу называют открытой.

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

, где i=1,…,m

Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме:

, где j=1,…,n

Из экономических соображений должно выполняться также условие неотрицательности переменных:

i=1,…,m; j=1,…,n

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

Таким образом, математическая формализация простейшей транспортной задачи закрытого типа имеет следующий вид:

где i=1,2,…,m; j=1,2,…,n

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

· потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;

· запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.

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

1. Общая модель транспортной задачи:

(11)

, где i=1,2,…,m (12)

, где j=1,2,…,n (13)

где i=1,2,…,m; j=1,2,…,n (14)

Здесь (11) – целевая функция (минимум затрат на транспортировку продукта);

(12) – ограничения по величине предложения в каждом пункте производства;

(13) – ограничения по величине спроса в каждом пункте потребления;

(14) – условия неотрицательности объемов перевозок.

2. Замкнутая транспортная задача. Общее предложение равно общему спросу:

Это необходимое и достаточное условие существования допустимого плана значения.

3. Открытая транспортная задача.

a. – излишек продукта.

Способ сведения к замкнутой задаче. Пусть b_n+1 – величина избытка продукции, то есть ; c_i,n+1 – штраф за единицу продукта, не реализованного в пункте i; y_i – количество продукта, не реализованного в пункте i.

Замкнутая транспортная задача имеет вид:

, где i=1,2,…,m

, где j=1,2,…,n

i=1,2,…,m; j=1,2,…,n

b. – дефицит продукта.

Способ сведения к замкнутой задаче. Пусть a_m+1 – величина дефицита продукции, то есть ; c_m+1,j – штраф за единицу продукта, недопоставленного в пункт j; y_j – количество продукта, не реализованного в пункте j.

Замкнутая транспортная задача имеет вид:

, где i=1,…,m

, где j=1,…,n

i=1,…,m; j=1,…,n

4. Транспортная задача с запретами. Пусть E – Множество пар индексов (i,j), таких, что из пункта i в пункт j допускается транспортировка продукта. Между любыми другими двумя пунктами транспортировка не допускается

Пусть М – большое число, например

М= max(c_ij ) max , i=1,…,m; j=1,…,n.

В оптимальном плане транспортной задачи при ограничениях (12)–(1

4) x_ij =0, если (i,j) Ï E.

5. Транспортная задача с фиксированными перевозками. Если объем перевозок между пунктами i и j задан, то в задаче (11)–(14) вводится дополнительное ограничение: x_ij=v_ij, где v_ij – заданный объем перевозок.

6. Транспортная задача с ограничениями на пропускную способность. Если объем перевозок из пункта i в пункт j ограничен величиной w_ij, то в задаче (11)–(14) вводится дополнительное ограничение: x_ij £ w_ij.

7. Транспортная задача с фиксированными доплатами. Предположим, что в открытой транспортной задаче имеет место дефи цит продукта и для его устранения в пунктах i=m+ 1,..., k возможно создание новых мощностей d_i.

Пусть переменные z_i =1, если в пункте i (i=m +1,..., k) вводятся мощности d_i,и z_i=0, если в пункте i мощности не вводятся. Издержки на ввод мощностей d_i в пункте i (i=m +1,..., k) составляют u_{i .}

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

(15)

, где i=1,…,m (16)

, где i=m +1,..., k (17)

, где j=1,…,n (18)

где i=1,…,k; j=1,…,n (19)

Здесь (15) – целевая функция (минимум затрат на транспортировку и ввод мощностей);

(16) – ограничения по величине предложения в каждом существующем пункте производства;

(17) – ограничения по величине предложения в каждом новом пункте производства;

(18) – ограничения по величине спроса в каждом пункте потребления;

(19) – условия неотрицательности объемов перевозок.

Помимо непрерывных переменных x_ij в модель включены булевы переменные z_i. Задача (15)–(19) является задачей линейного программирования со «смешанными» переменными.

Транспортным задачам присущи следующие особенности:

o распределению подлежат однородные ресурсы;

o условия задачи описываются только уравнениями;

o все переменные выражаются в одинаковых единицах измерения;

o во всех уравнениях коэффициенты при неизвестных равны единице;

o каждая неизвестная встречается только в двух уравнениях системы ограничений.

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

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

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

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

Поиск по сайту: