МУ ЭММ часть 1
.pdf41
ЗАДАНИЯ
Вариант 1
В соответствии с данными варианта лабораторной работы № 1, необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи; решить задачу линейного программирования в MS Excel и выполнить полный анализ полученных результатов.
Вариант 2
В соответствии с данными варианта лабораторной работы № 1, необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи; решить задачу линейного программирования в MS Excel и выполнить полный анализ полученных результатов.
Вариант 3
В соответствии с данными варианта лабораторной работы № 1, необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи; решить задачу линейного программирования в MS Excel и выполнить полный анализ полученных результатов.
Вариант 4
В соответствии с данными варианта лабораторной работы № 1, необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи; решить задачу линейного программирования в MS Excel и выполнить полный анализ полученных результатов.
Вариант 5
В соответствии с данными варианта лабораторной работы № 1, необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи; решить задачу линейного программирования в MS Excel и выполнить полный анализ полученных результатов.
Вариант 6
В соответствии с данными варианта лабораторной работы № 1, необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи; решить задачу линейного программирования в MS Excel и выполнить полный анализ полученных результатов.
42
Вариант 7
В соответствии с данными варианта лабораторной работы № 1, необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи; решить задачу линейного программирования в MS Excel и выполнить полный анализ полученных результатов.
Вариант 8
В соответствии с данными варианта лабораторной работы № 1, необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи; решить задачу линейного программирования в MS Excel и выполнить полный анализ полученных результатов.
Вариант 9
В соответствии с данными варианта лабораторной работы № 1, необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи; решить задачу линейного программирования в MS Excel и выполнить полный анализ полученных результатов.
Вариант 10
В соответствии с данными варианта лабораторной работы № 1, необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи; решить задачу линейного программирования в MS Excel и выполнить полный анализ полученных результатов.
Контрольные вопросы
1.Раскройте основные понятия двойственного анализа.
2.Сформулируйте правила составления двойственной задачи.
3.Дайте определения теорем двойственного анализа.
4.Как с помощью двойственных оценок задачи линейного программирования оценить целесообразность включения в план новых изделий?
5.Назовите основные этапы решения задачи линейного программирования с помощью Microsoft Excel.
6.Какие таблицы составляют отчет о результатах решения задачи линейного программирования?
7.Как выполнить анализ чувствительности решения к изменению коэффициентов целевой функции?
8.Как выполнить анализ чувствительности решения задачи к изменению запасов сырья?
43
Лабораторная работа № 3
Использование Microsoft Excel для решения транспортной задачи
Цель работы: приобретение практических навыков применения методов линейного программирования для решения транспортной задачи.
Содержание
Изучаются вопросы:
1.Транспортная задача. Общий вид. Основные понятия и определения.
2.Решение транспортной задачи в Microsoft Excel.
Выполняется вариант задания.
Указания
Рассмотрим транспортную задачу по критерию стоимости,
которую можно сформулировать следующим образом.
В m пунктах отправления A1, A2, …, Am, которые в дальнейшем будем называть поставщиками, сосредоточено определенное количество единиц некоторого однородного продукта, которое обозначим аi (i = 1, 2, ..., m). Данный продукт потребляется в n пунктах B1, B2, …, Bn, которые будем называть потребителями; объем потребления обозначим bj (j = = 1, 2, ..., n). Известны расходы на перевозку единицы продукта из пункта Аi в пункт Вj, которые равны cij и приведены в матрице транспортных расходов С = (cij).
Требуется составить такой план прикрепления потребителей к поставщикам, т.е. план перевозок, при котором весь продукт вывозится из пунктов Аi в пункты Вj в соответствии с потребностью и общая величина транспортных издержек будет минимальной.
Обозначим количество продукта, перевозимого из пункта Аi в пункт Вj, через xij. Совокупность всех переменных xij для краткости обозначим
X , тогда целевая функция задачи будет иметь вид
|
|
m |
n |
|
f X |
cij xij min, |
(1) |
||
|
|
i 1 |
j 1 |
|
а ограничения выглядят следующим образом:
m |
bj; |
|
|
|
|
|
xij |
j 1,n ; |
(2) |
||||
i 1 |
|
|
|
|
|
|
n |
ai; |
|
|
|
|
|
xij |
i 1,m; |
(3) |
||||
i 1 |
|
|
|
|
|
|
xij 0.
44
Условия (2) означают полное удовлетворение спроса во всех пунктах потребления; условия (3) определяют полный вывоз продукции от всех поставщиков.
Необходимым и достаточным условием разрешимости задачи (1)
(3) является условие баланса:
m |
n |
|
ai bj . |
(4) |
|
i 1 |
j 1 |
|
Транспортная задача, в которой имеет место равенство (4), называется закрытой и может быть решена, как задача линейного программирования с помощью симплексного метода. Однако благодаря особенностям переменных задачи и системы ограничений разработаны специальные, менее громоздкие методы ее решения.
Для решения транспортной задачи по критерию стоимости используем инструмент Excel Поиск решений.
Для запуска этого инструмента нужно выбрать На вкладке Данные выбираем команду Поиск решения (если команда отсутствует в окне параметров Excel выберете Надстройки Перейти и установите Поиск
решения).
Процедура поиска решения позволяет найти оптимальное значение формулы, содержащейся в ячейке, которая называется целевой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура изменяет значения во влияющих ячейках. Чтобы сузить множество значений, используемых в модели, применяются ограничения. Эти ограничения могут ссылаться на другие влияющие ячейки.
Пример. Рассмотрим задачу оптимизации перевозок строительных материалов с четырех заводов изготовителей на строящиеся объекты.
Имеется четыре пункта производства продукции (Завод 1, Завод 2, Завод 3, Завод 4). Заводы способны ежемесячно произвести продукцию, которая необходима для строящихся объектов, в размере 800, 400, 600 и 500 тыс. т продукции соответственно. Существует три пункта потребления этой продукции: Объект 1, Объект 2, Объект 3. Ежемесячные потребности этих пунктов в продукции составляют соответственно 1100, 700, 500 тыс. т. Для эффективной работы стройки необходимо как минимум 100 тыс. т продукции каждого вида ежемесячно. Стоимость перевозок (в рублях за тыс. т) автомобильным транспортом известна и приведена в табл. 13.
Требуется построить математическую модель для определения такого плана перевозки грузов, с которым были бы связаны наименьшие затраты на перевозку.
|
45 |
|
|
|
|
|
|
|
Таблица 13 |
Пункт назначения |
Строящиеся объекты |
Объем |
||
Пункт отправления |
Объект 1 |
Объект 2 |
Объект 3 |
производства |
Завод 1 |
3,9 |
4,2 |
2,7 |
800 |
Завод 2 |
5 |
6 |
4,1 |
400 |
Завод 3 |
6,4 |
7,1 |
4,1 |
600 |
Завод 4 |
7,4 |
9,4 |
8,3 |
500 |
Ежемесячные потребности объектов |
1100 |
700 |
500 |
2300 |
Минимальное количество продукции |
для каждого вида продукции более 100 тыс. т |
|||
Экономико-математическая модель задачи. Для простоты предположим, что у заводов достаточно ресурсов (рабочей силы, сырья и т. д.), чтобы выполнить все заявки, и что в данный момент отсутствует задел для продажи. Предположим, что можно отправить любое количество груза с каждого завода на любой строящийся объект, т.е. что имеются транспортные пути (железные дороги, шоссе и т.п.), связывающие каждый завод со всеми объектами.
Составим экономико-математическую модель задачи. Для этого составим план перевозок. В качестве параметра управления xij примем количество строительных материалов в тоннах, перевозимого с i-го завода изготовителя на j-й строящийся объект. Ограничения, которые следует учесть при отыскании оптимального плана перевозок, будут двух видов: по перевозке всего количества строительных материалов и готового к перевозке на каждом заводе.
Набор значений переменных xij – это и есть план перевозок. Поскольку переменные имеют по два индекса, то план удобнее записывать не в виде вектора, а в виде матрицы (или гистограммы):
x11 |
x12 |
x13 |
|
x21 |
x22 |
x23 |
|
X x |
x |
x |
. |
31 |
32 |
33 |
|
|
x42 |
x43 |
|
x41 |
|
Математическая модель задачи записывается в следующем виде:
Z= 3,9x11 + 4,2х12 + 2,7х13 + 5х21 + 6х22 + 4,1х23 + 6,4х31 + 7,1х32 +
+4,1х33 + 7,4х41 + 9,4х42 + 8,3х43 min
x11 x12 |
x13 |
800 |
|
|||
x21 x22 |
x23 |
400 |
||||
x |
31 |
x |
x |
600 |
||
|
32 |
33 |
500 |
|||
x |
|
x |
x |
|||
x41 |
x42 |
x43 |
x |
41 |
1100. |
|
11 |
21 |
31 |
|
700 |
||
x12 |
x22 |
x32 |
x42 |
|||
x13 x23 x33 x43 500
x 100
ij
46
В данной задаче сумма грузов, имеющихся во всех пунктах производства (2300 тыс. т), равна сумме потребностей в грузах, имеющихся во всех пунктах потребления (2300 тыс. т). Такая транспортная задача имеет оптимальный план перевозок. А вот если бы оказалось, что суммарный груз в пунктах производства оказался меньше суммарной потребности в пунктах потребления, то задача оказалась бы неразрешимой. Она не имела бы даже допустимых планов, и тем более не имела бы оптимального.
Целевая функция задачи представляет собой сумму произведений стоимостей перевозки 1 т груза на объем перевозки для каждой пары поставщика-потребителя, т.е. общую суммарную стоимость всех перевозок, соответствующих плану Х. Эту суммарную стоимость следует минимизировать при условии, что будут выполнены все ограничения.
Ограничения на перевозки можно разбить на три группы. Первая группа это верхние четыре неравенства. В каждое из них входят переменные с одним и тем же первым индексом, но различными вторыми индексами, т. е. переменные, соответствующие одному и тому же пункту производства, но различным пунктам потребления. Каждое из этих неравенств говорит о том, что суммарный объем всех грузов, вывозимых из одного и того же пункта производства в разные пункты потребления, равен количеству продукции, которое может быть произведено в данном пункте производства. Вторая группа это следующие три равенства. В каждое из них входят переменные с одним и тем же вторым индексом, но разными первыми индексами. Эти переменные соответствуют одному пункту потребления, но разным пунктам производства. Такое равенство утверждает, что объем всего груза, который свозится из разных пунктов производства в один и тот же пункт потребления, равен объему потребности в данном пункте потребления. Третья группа ограничений утверждает, что все объемы перевозок неотрицательны и имеют условие о минимуме потребления продукции.
Для решения поставленной задачи инструментом создадим модель, представленную на рис. 15.
Для запуска инструмента Поиск решения необходимо на вкладке Данные выбирать команду Поиск решения (если команда отсутствует, то в окне параметров Excel выберете Надстройки Перейти и установите
Поиск решения).
В окне установите следующие параметры:
оптимизировать целевую функцию в ячейке $B$15 до Минимум; изменяя ячейки переменных $B$9:$D$12;
метод решения:
47
список ограничений (вводится с помощью кнопки Добавить):
$E$9:$E$12=$F$9:$F$12; $B$13:$D$13<=$B$14:$D$14; $B$9:$D$12=целое; $B$9:$D$12>=100.
Рис. 15. Модель транспортной задачи
Окно Поиска решения с заполненными параметрами представлено на рис. 16.
Рис. 16. Окно Параметры поиска решения
Результат решения задачи приведен в табл. 14.
48
Таблица 14
Затраты на |
Объект 1 |
Объект 2 |
Объект 3 |
|
|
|
перевозку, руб./тыс.т. |
|
|
||||
|
|
|
|
|
||
Завод 1 |
3,9 |
4,2 |
2,7 |
|
|
|
Завод 2 |
5 |
6 |
4,1 |
|
|
|
Завод 3 |
6,4 |
7,1 |
4,1 |
|
|
|
Завод 4 |
7,4 |
9,4 |
8,3 |
|
|
|
Min потребл. |
более 100 тыс. т. для всех перевозок |
|
|
|||
|
|
|
|
|
|
|
Объем перевозок, |
Объект 1 |
Объект 2 |
Объект 3 |
Объем |
Объем |
|
тыс. т |
перевозок |
произод. |
||||
|
|
|
||||
Завод 1 |
300 |
400 |
100 |
800 |
800 |
|
Завод 2 |
200 |
100 |
100 |
400 |
400 |
|
Завод 3 |
300 |
100 |
200 |
600 |
600 |
|
Завод 4 |
300 |
100 |
100 |
500 |
500 |
|
|
|
|
|
|
|
|
Факт. спрос |
1100 |
700 |
500 |
|
|
|
Потребление (спрос) |
1100 |
700 |
500 |
|
|
|
Целевая функция |
12570 |
|
|
|
|
|
Вывод: разработанный оптимальный план обеспечивает минимальные затраты на транспортировку продукции из четырех пунктов производства в три пункта потребления. На основании решения транспортной задачи определены поставки каждого завода на строящиеся объекты, производственные программы по заводам изготовителям и резервы производственных мощностей. Все предприятия свои мощности используют полностью. Обеспечение строящихся объектов происходит в полном объеме.
В результате решения задачи предложен следующий план перевозок продукции с заводов на пункты потребления:
300 |
400 |
100 |
|
|
|
200 |
100 |
100 |
|
матрица перевозок: X |
300 |
100 |
200 |
; |
|
300 |
100 |
100 |
|
|
|
|||
гистограмма плана транспортировки (рис. 17); гистограмма затрат на транспортировку (рис. 18).
Минимальные затраты на транспортировку всех грузов составят 12570 д.е. Затраты на заводах изготовителях и при транспортировке с завода на объект составят 3120, 2010, 3450 и 3990 д.е. соответственно.
49
Рис. 17. Гистограмма плана транспортировки грузов
Рис. 18. Гистограмма затрат на перевозку
50
ЗАДАНИЯ Вариант 1
На оптовом складе имеется три холодильника (А1, А2, А3), вмещающих мороженную рыбу в количествах 320 т, 280 т, 250 т соответственно. Необходимо доставить рыбу в пять магазинов (В1, В2, В3, В4, В5) в количествах 140 т, 110 т, 230 т, 220 т, 150 т соответственно. Стоимости перевозки 1 т рыбы из холодильника в магазин заданы в табл. 15. Для эффективной работы магазина необходимо как минимум 10 т доставки рыба.
Таблица 15
Стоимость перевозок, тыс. руб.
Пункт назначения |
|
|
Магазины |
|
|
Пункт отправления |
В1 |
В2 |
В3 |
В4 |
В5 |
А1 |
20 |
23 |
20 |
15 |
24 |
А2 |
29 |
15 |
16 |
19 |
29 |
А3 |
6 |
11 |
10 |
9 |
8 |
Сформулировать математическую модель задачи и спланировать перевозки так, чтобы их общая стоимость была минимальной.
Вариант 2
Четыре предприятия данного экономического района для производства продукции используют некоторое сырье. Спрос на сырье каждого из предприятий соответственно составляет: 120, 50, 190 и 110 усл. ед. Сырье сосредоточено в трех местах. Предложения поставщиков сырья равны: 160, 140 и 170 усл. ед. На каждое предприятие сырье может завозиться от любого поставщика, но в объеме не менее 5 усл. ед. Стоимость перевозки единицы сырья известны и заданы в табл. 16.
|
Тарифы перевозок, усл. руб. |
Таблица 16 |
||
|
|
|||
Пункт назначения |
|
Предприятия |
|
|
Пункт отправления |
Предприятие 1 |
Предприятие 2 |
Предприятие 3 |
Предприятие 4 |
Поставщик 1 |
7 |
8 |
1 |
2 |
Поставщик 2 |
4 |
5 |
9 |
8 |
Поставщик 3 |
9 |
2 |
3 |
6 |
Требуется составить план перевозок, при котором общая стоимость перевозок минимальна.