Практикум по учебной дисциплине «Математические методы в программировании»


Рис. 2 Программирование целевой ячейки



страница2/2
Дата06.06.2016
Размер0.7 Mb.
ТипПрактикум
1   2

Рис. 2 Программирование целевой ячейки


Примечание: для вызова встроенной функции СУММПРОИЗВ необходимо выполнить последовательность действий:

  1. установить курсор в нужную ячейку (в нашем примере – в ячейку Е4);

  2. вызвать «Мастер функций» (кнопка fx), далее «Математические» и выбрать «СУММПРОИЗВ»;

  3. в появившейся экранной форме (рис. 3) установить курсор в «Массив 1» и выделить на листе Excel диапазон зарезервированных для значений переменных ячеек, поставив им абсолютные адреса ($C$3:$D$3) нажатием функциональной клавиши F4; перевести курсор в «Массив 2» и выделить диапазон ячеек, в которых записаны коэффициенты при переменных в целевой функции (C4:D4), после чего нажать «ОК».

Рис. 3 Вызов функции СУММПРОИЗВ

Таким образом, после завершения всех подготовительных операций выбираем в «Сервис» процедуру «Поиск решения» (рис. 4). В появившейся экранной форме (рис 5) устанавливаем целевую ячейку - $Е$4, затем отмечаем флажком тип оптимизации (исходя из условий задачи) – максимизация; переводим курсор в «Изменяя ячейки» и выделяем на листе Excel диапазон зарезервированных для значений переменных ячеек ($C$3:$D$3); после чего, установив курсор в «Ограничения», нажимаем «Добавить» и в появившейся экранной форме (рис. 6) отмечаем диапазон ячеек:



  1. «Ссылка на ячейку» - $Е$6:$Е$9 (здесь записаны результаты суммирования левых частей неравенств в системе ограничений);

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

  3. «Ограничение:» - $G$6:$G$9 (здесь записаны правые части неравенств в системе ограничений модели).

Рис. 4 Вызов процедуры «Поиск решения»

Рис. 5 Экранная форма «Поиск решения»

По нажатию «ОК» возвращаемся к экранной форме «Поиск решения». Выбираем пункт «Параметры», где отмечаем флажком «Линейная модель» и «Неотрицательные значения» (рис. 7), затем по нажатию «ОК» возвращаемся к экранной форме «Поиск решения».


Рис. 6 Экранная форма «Добавление ограничения»

Рис. 7 Экранная форма «Параметры»



После выбора опции «Выполнить» Excel проводит расчеты и результаты вычислений заносятся в ячейки C3:D3 и Е4, которые были зарезервированы для значений искомых переменных и оптимального значения целевой функции.

Окончательно лист Excel будет иметь вид (рис. 8):

Рис. 8 Результаты работы процедуры «Поиск решения»




Замечание. Если «Поиск решения» закончил работу конфликтно, то возможны следующие ситуации:

  1. целевая функция не ограничена на множестве допустимых решений сверху (снизу) для задачи максимизации (минимизации); в этом случае

  2. неправильно введены формулы в ячейки либо допущена ошибка при заполнении формы «Поиск решения»; в данной ситуации необходимо перепроверить правильность введенных формул и вновь запустить «Поиск решения».

Таким образом, в результате использования встроенного инструмента «Поиск решения» было найдено оптимальное решение исходной задачи, а именно:

Итак, оптимальный план производства предусматривает выпуск 10/3тонн краски Е и 4/3тонн краски I, прибыль от реализации которой будет максимальной и составит тыс. у.е.


2. Индивидуальные задания

Построить математическую модель задачи. Решить задачу с использованием процедуры «Поиск решения». Сделать выводы в терминах постановки задачи:

Задача 1. На заводе используется сталь трёх марок А, В, С, запасы которых соответственно равны 10, 16 и 12 единиц. Завод выпускает два вида изделий. Для изделия I требуется по одной единице стали всех марок. Для изделия II требуется 2 единицы стали марки В, 1 единица стали марки С и не требуется сталь марки А. От реализации единицы изделия вида I завод получает 3 условные единицы, вида II – 2 условные единицы. Составить план выпуска продукции, дающий наибольшую прибыль.

Задача 2. Для изготовления столов и шкафов употребляются два вида древесины. Расход древесины каждого вида на каждое изделие задан таблицей:

Вид изделия



Древесина

Вида I

Вида II

Стол

0,15

0,2

Шкаф

0,2

0.1

Доход мастерской от производства одного стола составляет 12 ден. ед., а шкафа – 15 ден. ед.

Определить, сколько столов и сколько шкафов должна изготовить мастерская, чтобы прибыль мастерской была наибольшей, если в её распоряжении имеется 60 куб. м. древесины вида I и 40 куб. м. древесины вида II.



Задача 3. Хозяйство располагает следующими ресурсами: площадь – 100 единиц, труд – 120 единиц, тяга - 80 единиц. Затраты на 1 единицу четырёх видов продукции П1, П2, П3, П4 и доход хозяйства от производства этих видов продукции даны в таблице:


Вид продукции

Затраты на 1 единицу продукции

Денежный доход

Площадь

Труд

Тяга

П1

2

2

2

1

П2

3

1

2,6

4

П3

4

2

1

3

П4

5

4

1

5

Составить план, дающий наибольшую прибыль.

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

I вида – 72 куб. м., II вида – 56 куб. м. Расход каждого вида древесины на каждое изделие – в таблице:



Изделие

Древесина

Вид I

Вид II

Стол

0,18

0,08

Тумбочка

0,09

0,28

От производства одного стола мастерская получает 1,1 ден. ед. прибыли, от одной тумбочки – 0,70 ден. ед. прибыли.

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



Задача 5. Завод выпускает изделия двух видов А и В. При этом используется сырьё четырёх видов I, II, III, IV, запасы которых равны соответственно 21, 4, 6, 10 единиц. Для изделия А требуется: 2 единицы сырья I, 1 единицы сырья II, 2 единицы сырья IV и не используется сырьё III.

Для изделия В требуется: 3 единицы сырья I, 1 единица сырья III, 1 единица сырья IV и не используется сырьё II. Выпуск одного изделия А приносит 3 ден. ед. прибыли, одного изделия В – 2 ден. ед. прибыли.

Составить план производства, обеспечивающий наибольшую прибыль.

Задача 6. Фирма производит два продукта А и В, рынок сбыта которых неограничен. Каждый продукт должен быть обработан каждой из машин I, II, III. Время обработки в часах для каждого из изделий А и В приведено ниже:





А

В

I

0.5

0.25

II

0.4

0.3

III

0,2

0.4

Время работы машин I, II, III, соответственно, 40, 36 и 36 часов в неделю. Прибыль от изделий А и В составляет, соответственно, 5 и 3 долл.

Фирме надо определить недельные нормы выпуска изделий А и В, максимизирующие прибыль.

В отчёте представить:


  • постановку задачи;

  • математическую модель с необходимыми комментариями по ее элементам;

  • краткое описание компьютерной информационной технологии

получения решения с фрагментом листа Excel, содержащего результаты решения;

  • анализ полученных результатов;

  • ответить на контрольные вопросы.

Контрольные вопросы:

  1. Что представляют собой задачи оптимизации и в чем особенность

задач линейного программирования?

  1. Какие методы применяют для решения 3ЛП?

  2. В каком случае ЗЛП называется разрешимой?

  3. С помощью какого диалогового окна в Excel можно решить задачу

линейного программирования?
Практическая работа №5 (2 часа)

Тема: Решение комплексных задач линейного программирования

Цель работы: закрепить навыки использования математических методов, а также методов с применением ЭВМ для решения задач линейного программирования.

Оборудование: компьютер, пакет Microsoft Office

Задание

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


Варианты индивидуальных заданий
Задача 1. Чаеразвесочная фабрика выпускает чай сорта А и В, смешивая три ингредиента: индийский, грузинский и краснодарский чай. В таблице приведены нормы расхода ингредиентов, объем запасов каждого ингредиента и прибыль от реализации 1 тонны чая сорта А и В.

Ингредиенты

Нормы расхода (т/т)

Объем запасов (т)

Индийский чай

0,5

0,2

600

Грузинский чай

0,2

0,6

870

Краснодарский чай

0,3

0,2

430

Прибыль от реализации 1 тонны продукции (ден.ед)

320

290




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

Задача 2. Небольшая фирма производит два типа подшипников А и В, каждый из которых должен быть обработан на трех станках, а именно токарном, шлифовальном и сверлильном. Время, требуемое для каждой из стадий производственного процесса, приведено в таблице:


Тип подшипника

Прибыль от продажи 1 подшипника

Время обработки, ч

Токарный станок

Шлифовальный станок

Сверлильный станок

А

80

0,01

0,02

0,04

В

125

0,02

0,01

0,01

Полное возможное время работы в неделю




120

15

150

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

Задача 3. Фирма производит три вида продукции, используя для этого два вида ресурсов. Технологическая матрица задана в виде таблицы:




Продукт 1

Продукт 2

Продукт 3

Ресурс 1

1

2

0

Ресурс 2

2

3

1

Фирма имеет в своём распоряжении 20 единиц 1-го ресурса и 25 единиц 2-го ресурса; цены, по которым предполагает реализовать свою продукцию фирма, равны 15, 20, 30 тыс. руб. за 1-й, 2-й и 3-й товар, соответственно. Фирма желает получить максимальный доход.

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

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



Ресурсы

Нормы затрат ресурсов на одно изделие

Общее количество ресурсов

стол

шкаф

Древесина (м3):










I вида

0,2

0.1

40

II вида

0.1

0,3

60

Трудоемкость (человеко-час)

1,2

1,5

371,4

Прибыль от реализации одного изделия (у.е.)

6

8





В отчёте представить:

  • постановку задачи;

  • математическую модель с необходимыми комментариями по её элементам;

  • полное описание хода решения задачи с помощью симплекс-таблиц;

  • фрагмент листа EXCEL, содержащего результаты решения;

  • анализ полученных результатов.


Практическая работа №6 (2 часа)

Тема: Решение транспортной задачи различными методами

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

1. Теоретические сведения

1.1. Общие понятия транспортной задачи

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

Задачи транспортного типа широко распространены в практике. К ним сводятся многие задачи линейного программирования – задачи о назначениях, сетевые, календарного планирования и др.

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

Стандартная ТЗ формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) Аi…,Аm, в которых сосредоточены запасы однородных продуктов в количестве a1,...,аm единиц. Имеется n пунктов назначения (или пунктов потребления) В1,..., Вm, потребность которых в указанных продуктах составляет b1, ..., bn единиц. Известны также транспортные расходы Сij, связанные с перевозкой единицы продукта из пункта. Ai в пункт Вj, i image64691,2…, m;  = 1,2..., n.

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

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

→ min (1.1)

Таким образом, целевая функция ТЗ представляет собой транспортные расходы на осуществление всех перевозок в целом.

Математическая модель ТЗ содержит также две группы ограничений.

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

. , где i = 1. …., m (1.2)

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



, где j = 1. …., n (1.3)

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



xij image64430, i image64691, ..., m; j image64691, ..., n. (1.4)

Из (1.2), (1.3) следует, что сумма запасов продукции во всех пунктах отправления должна равняться суммарной потребности во всех пунктах потребления, то есть



(1.5)

Если условие (1.5) выполняется, то ТЗ называется сбалансированной (замкнутая модель), в противном случае – несбалансированной (открытая модель). Поскольку ограничения модели ТЗ (1.2), (1.3) могут быть выполнены только при сбалансированной ТЗ, то при построении транспортной модели необходимо проверять условие баланса (1.5). В случае, когда суммарные запасы превышают суммарные потребности, необходим дополнительный фиктивный пункт потребления, который будет формально потреблять существующий излишек запасов, то есть



(1.6)

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



(1.7)

Введение фиктивного потребителя или отправителя повлечет необходимость формального задания фиктивных тарифов (реально не существующих) для фиктивных перевозок.

Так как нас интересует суммарная стоимость всех перевозок, можно принять величину фиктивного тарифа равной нулю =0, что не изменит значение искомой целевой функции.

1. 2. Пример решения транспортной задачи

Рассмотрим процедуру решения транспортной задачи на конкретном примере.



Задача: Четыре предприятия данного экономического района для производства продукции используют некоторое сырьё. Спрос на сырьё каждого из предприятий соответственно составляет 120, 50, 190 и 110 у.е. Сырьё сосредоточено в трех местах. Предложения поставщиков сырья равны 160, 140 и 170 у.е.. На каждое предприятие сырьё может завозиться от любого поставщика. Тарифы перевозок известны и задаются матрицей:
7 8 1 2

С= 4 5 9 8

9 2 3 6

В i-ой строке и j-ом столбце матрицы С стоит тариф на перевозку сырья от i-го поставщика j-му потребителю. Под тарифом понимается стоимость перевозки единицы сырья.



Требуется составить план перевозок, при котором общая стоимость перевозок минимальна.

Решение:

Представим задачу в виде таблицы:






1

2

3

4

Предложение

1

7

8

1

2

160

2

4

9

9

8

140

3

9

2

3

6

170

Спрос

120

50

190

110

//////////////////////

Проверим задачу на сбалансированность.

120 + 50 + 190 + 110 = 160 + 140 +170 = 470, т.е. спрос равен предложению.

Рассмотрим два метода построения начального опорного плана задачи.



1) Метод «северо-западного угла»



1

2

3

4

Предложение

1

7

120


8

40


1

2

160

2

4

9

10


9

130


8

140

3

9

2

3

60


6

110



170

Спрос

120

50

190

110

/////////////////////

Начинаем заполнение таблицы с первой верхней клетки. В неё помещают x11 = min (160, 120) = 120. Спрос первого потребителя полностью удовлетворен, первый столбец вычеркиваем. Остаток сырья в первом пункте составляет 160 – 120 = 40 у.е. Двигаемся по первой строке вправо: x12 = min (160 – 120, 50) = 40. Предложение поставщика исчерпано, первая строка вычеркивается. Второму потребителю не хватает 50 – 40 = 10 у.е. Двигаемся по второму столбцу вниз: x22 = min (50 – 40, 140) = 10. Второй столбец вычеркиваем. Двигаемся по второй строке вправо: x23 = min (190, 140) = 150. Вторая строка вычеркивается. Двигаемся по третьему столбцу вниз: x33 = min (190 – 130, 170) = 60. Спрос третьего потребителя удовлетворен. Двигаемся по третьей строке вправо: x34 = min (170 – 60, 110) = 110.

Начальный план перевозок имеет вид:

x11 = 120 x12 = 40 x13 = 0 x14 = 0

Х1 = x21 = 0 x22 = 10 x23 = 130 x24 = 0

x31 = 0 x32 = 0 x33 = 60 x34 = 110


Стоимость перевозок по этому плану:

S1 = 120 * 7 + 40 * 8 + 5 * 9 + 9 * 130 + 3 * 60 + 6 * 110 = 3220 у.е.



2) Метод минимального элемента



1

2

3

4

Предложение

1

7

8

1

160


2

160

2

4

120


5

9

8

20


140

3

9

2

50


3

30


6

90


170

Спрос

120

50

190

110

//////////////////////

Заполняем таблицу с клетки с наименьшим тарифом. Минимальный тариф: c13 = 1, x13 = min (160, 190) = 160. Первую строку вычеркиваем. Минимальный тариф для оставшихся клеток: c32 = 2, x32 = min (50, 170) = 50. Второй столбец вычеркиваем. Для оставшихся клеток минимальный тариф:

c33 = 3, x33 = min (190 – 160, 170 – 50) = 30. Третий столбец вычеркиваем. Для оставшихся клеток минимальный тариф: c21 = 4, x21 = min (120, 140) = 120. Первый столбец вычеркиваем. Для оставшихся клеток минимальный тариф: c34 = 6, x34 = min (170 – 50 – 30, 110) = 90.

x24 = min (140 – 120, 110 – 90) = 20.

План перевозок имеет вид:

x11 = 0 x12 = 0 x13 = 160 x14 = 0

Х1 = x21 = 120 x22 = 0 x23 = 0 x24 = 20

x31 = 0 x32 = 50 x33 = 30 x34 = 90

Стоимость перевозок по этому плану:

S1 = 160 * 1 + 120 * 4 + 20 * 8 + 50 * 2 + 30 * 3 + 90 * 6 = 1530 у.е.

Для определения оптимальности полученного плана воспользуемся методом потенциалов.

Проверим на оптимальность план, полученный методом минимального элемента.





1

2

3

4

Предложение

1

7

8

160 1

+

2

160

2

120 4

5

9

20

8

140

3

9

50 2

30 + 3

90

6

170

Спрос

120

50

190

110

//////////////////////

Число заполненных клеток равно 4 + 3 – 1 = 6, т. е. план невырожденный.

По заполненным клеткам таблицы определим потенциалы производителей и потребителей:

U2 + ‍‍V1 = 4 U1 = 0 ‍‍V1 = 0

U1 + ‍‍V3 = 1 U2 = 4 ‍‍V2 = 0

U3 + ‍‍V2 = 2 U3 = 2 ‍‍V3 = 1

U3 + ‍‍V3 = 3 ‍‍V4 = 4

U2 + ‍‍V4 = 8

U3 + ‍‍V3 = 6

Для всех пустых клеток составим разность: Δij = Ui + ‍‍Vj – Cij.

Δ11 = U1 + ‍‍V1 – C11 = 0 + 0 – 7 = –7

Δ12 = U1 + ‍‍V2 – C12 = 0 + 0 – 8 = –8



Δ14 = 2>0

Δ22 = –1

Δ23 = –4

Δ31 = –7

Так как Δ14 = 2 > 0, условие оптимальности не выполняется. Улучшим план с помощью цикла пересчёта.

Строим цикл (1,4) - (3,4) - (3,3) - (1,3) - (1,4). Перераспределяем продукцию по циклу. Минимальное значение для клеток со знаком « – » x34 = 90. Отнимем 90 от 160 и прибавим к 30. А в пустую клетку со знаком «+» поставим 90.

Получим новый план перевозок:



1

2

3

4

Предложение

1

7

8

70 1

90 + 2

160

2

120 4

+ 5

9

20 8

140

3

9

50 - 2

120 + 3

6

170

Спрос

120

50

190

110

//////////////////////

Определим потенциалы производителей и потребителей:

U1 + ‍‍V3 = 1 U1 = 0 ‍‍V1 = –2

U1 + ‍‍V4 = 2 U2 = 6 ‍‍V2 = 0

U2 + ‍‍V1 = 4 U3 = 2 ‍‍V3 = 1

U2 + ‍‍V4 = 8 ‍‍V4 = 2

U3 + ‍‍V2 = 2

U3 + ‍‍V3 = 3

Для всех пустых клеток:

Δ11 = –9

Δ12 = –8



Δ22 = 1 > 0

Δ23 = –2

Δ31 = –9

Δ34 = –2

Так как Δ22 = 1 > 0, условие оптимальности не выполняется. Улучшим план с помощью цикла пересчёта.

Строим цикл (2,2) - (2,4) - (1,4) - (1,3) - (3,3) - (3,2) - (2,2)





1

2

3

4

Предложение

1

7

8

50 1

110 2

160

2

120 4

20 5

9

8

140

3

9

30 2

140 3

6

170

Спрос

120

50

190

110

//////////////////////

Проверив полученный план, убеждаемся, что он оптимален.
Ответ: План перевозок x11 = 0 x12 = 0 x13 = 50 x14 = 110

Х = x21 = 120 x22 = 20 x23 = 0 x24 = 0

x31 = 0 x32 = 30 x33 = 140 x34 = 0

Стоимость перевозки S = 1330 у.е.



2. Индивидуальные задания

Решить транспортную задачу методом потенциалов, составив опорный план: а) методом «северо-западного угла»; б) методом минимального элемента:

1 вариант

Заводы


Потребители

Предложение

1

2

3

4

I

2

4

5

1

60

II

2

3

9

4

70

III

3

4

2

5

20

Спрос

40

30

30

50



Составить оптимальный план доставки станков.


2 вариант

Песчаные карьеры


Участки дороги

Наличие песка,

тыс. т


1

2

3

4




I

1

8

2

3

30

II

4

7

5

1

50

III

5

3

4

4

20

Потребность в песке, тыс.т

15

15

40

30




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



3 вариант

Склады


Магазины

Предложение

1

2

3

4

5




I

2

6

3

4

6

40

II

1

5

6

9

7

30

III

3

4

1

6

10

35

Спрос

20

34

16

10

25



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



4 вариант

Хранилище

Потребители

Предложение

1

2

3

4

I

2

7

3

6

45

II

9

4

5

7

35

III

5

7

6

2

60

Спрос

20

35

40

45



Составить оптимальный план обслуживания при минимальных расходах на транспортировку.



5 вариант

Поставщики


Потребители

Запасы

1

2

3

4

I

1

2

5

3

60

II

1

6

5

2

120

III

6

3

7

4

100

Потребность

20

110

40

110



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



6 вариант

Элеваторы


С/х предприятия

Предложение

1

2

3

4




A

6

4

4

5

200

B

6

9

5

8

300

C

8

2

10

6

100

Спрос

450

250

100

100



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



В отчёте представить:

  • построение начального плана перевозок методом минимального элемента и методом «северо-западного угла»;

  • решение задачи методом потенциалов;

  • полный ответ;

  • ответить на контрольные вопросы.

Контрольные вопросы:

  1. Что представляет собой транспортная задача?

  2. Какие методы применяют для решения транспортной задачи?

  3. В каком случае транспортная задача называется сбалансированной?

  4. Какой метод применяется для определения оптимальности начального плана?

Практическая работа №7 (2 часа)

Тема: Решение транспортной задачи с помощью Microsoft Excel

Цель работы: получить практические навыки использования функций «Поиск решения» в электронной таблице Excel при решении транспортной задачи.

Оборудование: компьютер, пакет Microsoft Office

1. Пример решения задачи

Задача: Крупная оптовая фирма занимается поставкой некоего товара в магазины города. Товар поставляется из трех складов, месячные запасы которых составляют 1500, 1300 и 1600 единиц товара соответственно. Товар нужно развести по трем магазинам, месячные потребности которых равны 2100, 1600 и 1000 единиц товара соответственно. Транспортные расходы по доставке единицы товара из соответствующего склада в соответствующий магазин приведены в табл.1.1. Необходимо определить оптимальные по транспортным расходам способы доставки товара со складов в магазины.

Таблица 1.1

Магазины

Склады

Магазин 1

Магазин 2

Магазин 3

Склад 1

80

200

70

Склад 2

100

105

120

Склад 3

120

70

90


Решение:

Составим в MS Excel транспортную матрицу для решения задачи, рис.1.11



Рис.1.11 Транспортная матрица задачи в MS Excel


Проверяем баланс ТЗ.

Суммарные запасы составляют = 4400 шт. товара, суммарная потребность = 4700 шт.

Транспортная задача не сбалансирована – спрос превышает предложение. Приведем ТЗ к сбалансированной, добавив еще один фиктивный склад, стоимость перевозки товара в который будет равна нулю.

Определим количество товара на фиктивном складе = 4700 – 4400 = 300 шт. и внесем изменения в лист книги MS Excel.



Рис.1.12 Сбалансированная транспортная матрица

Сбалансированность транспортной матрицы легко проверить средствами Excel, последовательно вычислив суммы ячеек В8:D8 и Е4:Е7. Суммы должны быть одинаковыми.

Создадим экранную форму решения ТЗ, для чего выделим на листе книги все ячейки транспортной матрицы, создадим ее копию и внесем в копию необходимые исправления. За начальные условия перевозимого количества товара примем нули, рис.1.13.


Рис.1.13 Транспортная матрица и экранная форма решения ТЗ


Заполним полученную экранную форму необходимыми формулами. Для этого удобно воспользоваться встроенными в Excel математическими формулами СУММ() и СУММПРОИЗВ(), рис.1.14.

Рис.1.14 Экранная форма решения ТЗ с введенными формулами


Ячейка Е19 содержит формулу для вычисления значения целевой функции – суммарной стоимости всех транспортных перевозок.

Выберем в меню СЕРВИС команду ПОИСК РЕШЕНИЯ и установим в диалоговом окне формы «Поиск решения» целевую ячейку, требуемый вид зависимости целевой функции, диапазон ячеек переменных и ограничения в соответствии с условиями решаемой ТЗ, рис.1.15.


Рис.1.15 Окно форма «Поиск решения» ТЗ

Нажмем кнопку «Параметры» и в открывшемся диалоговом окне формы «Параметры поиска решения» отметим галочкой «Линейная модель», так как решаемая нами ТЗ является задачей линейного программирования.

После выполнения процедуры поиска решения на рабочем листе книги получим решение ТЗ, рис.1.16.


Рис.1.16 Результат решения ТЗ на листе книги MS Excel


Ответ: Стоимость перевозки составляет 352000 у.е.; план перевозки имеет вид Х=
2. Индивидуальные задания

Решить транспортную задачу с помощью Microsoft Excel:

Задача 1.

Поставщики

Мощность

поставщиков



Потребители и их спрос

1

2

3

4

450

250

100

100

1

200

6

4

4

5

2

300

6

9

5

8

3

100

8

2

9

6



Задача 2. Имеются два поставщика с ресурсами 150 и 90, три пункта доставки. Необходимо доставить в соответствующие пункты 60, 70 и 110 единиц. Стоимость перевозки из А1 в В1- 6 у.е., в В2- 6 у.е., в В3-4 у.е., из А2 в В1- 12 у.е., в В2-2 у.е., в В3-8 у.е. Стоимость перевозки должна быть минимальной.

Задача 3.

Поставщики

Мощность

поставщиков



Потребители и их спрос

1

2

3

4

45

15

20

20

1

25

9

5

3

10

2

55

6

3

8

2

3

20

3

8

4

8


Задача 4.

Поставщики

Мощность

поставщиков



Потребители и их спрос

1

2

3

4

50

50

40

60

1

30

5

4

6

3

2

70

4

5

5

8

3

70

7

3

4

7


Задача 5.

Поставщики

Мощность

поставщиков



Потребители и их спрос

1

2

3

4

20

110

40

110

1

60

1

2

5

3

2

120

1

6

5

2

3

100

6

3

7

4


Задача 6.

Поставщики

Мощность

поставщиков



Потребители и их спрос

1

2

3

60

60

50

1

50

2

3

2

2

70

2

4

5

3

60

6

5

7


В отчёте представить:

  • условие задачи;

  • краткое описание компьютерной информационной технологии

получения решения с фрагментом листа Excel, содержащего результаты решения;

  • анализ полученных результатов;

  • полный ответ.

Контрольные вопросы:

  1. Что представляют собой задачи оптимизации и в чем особенность транспортной задачи?

  2. Какие методы применяют для решения транспортной задачи?

  3. В каком случае транспортная задача называется сбалансированной?

  4. С помощью какого диалогового окна в Excel можно решить транспортную задачу?


Список рекомендуемой литературы


  1. Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Высшая школа, 2008. – 192 с.

  2. Исследование операций в экономике: Учеб. пособие для вузов /Н.Ш. Кремер, БА. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. — М.: ЮНИТИ, 2005. — 407 с.

  3. Филимонова Е.В. Математика: Учебное пособие для средних специальных учебных заведений. / Е.В. Филимонова. – 2-е изд., доп. и перераб. – Ростов-на- Дону.: Феникс, 2008. - 576 с.

  4. Хазанова Л. Х. Математические методы в экономике. – Москва, Волтерс Клувер, 2005 г.- 144 с.

  5. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. - М.: Высшая школа, 2011.-352 с.

  6. Л. В. Рудикова «Microsoft Excel для студента», Санкт – Петербург, БХВ-Петербург, 2005.

Каталог: upload -> 2014
2014 -> «Матрицы и определители» для студентов специальностей
2014 -> Учебно-методическое пособие для бакалавров и специалистов технического вуза Нижний Новгород Издательство фбоу впо «вгавт» 2013 удк п 21
2014 -> Интегрированный урок физика, математика, биология тема урока «Звуковые волны»
2014 -> Контрольные вопросы по освоению курса, терминологический словарь. Для студентам вузов и ссузов, начинающих преподавателей, а также всех интересующихся вопросами культуры
2014 -> 1. Характеристика жанров советской хоровой литературы Массовая песня в 1920-1930 годы ст
2014 -> Урока по дисциплине «Литература (по пьесе А. Н. Островского
2014 -> Краеведение


Поделитесь с Вашими друзьями:
1   2


База данных защищена авторским правом ©uverenniy.ru 2019
обратиться к администрации

    Главная страница