МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ВЫПОЛНЕНИЯ ПРАКТИЧЕСКОЙ РАБОТЫ ПО ТЕМЕ «ТРАНСПОРТНАЯ ЗАДАЧА»


Н.А. Ершова, преподаватель математики,
А.А. Мардамшина, преподаватель информационных дисциплин,
ОГБОУ СПО «Ульяновский авиационный колледж», г. Ульяновск
МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ВЫПОЛНЕНИЯ ПРАКТИЧЕСКОЙ РАБОТЫ ПО ТЕМЕ «ТРАНСПОРТНАЯ ЗАДАЧА»
Научно-технический прогресс в настоящее время изменяет характер профессиональной деятельности специалиста и саму профессионально-квалификационную структуру труда. Основы профессионального развития личности специалиста закладываются в любом профессиональном образовательном учреждении, начиная с первых лет обучения, в процессе усвоения специальных, общепрофессиональных, образовательных и естественно-научных предметов.
Учебная дисциплина «Математика» на специальности 210420 «Техническая эксплуатация транспортного радиоэлектронного оборудования» в ОГБОУ СПО «Ульяновский авиационный колледж» изучается на первом году обучения. Причем в этот период студенты осваивают курс полного среднего образования, что не только развивает логическое мышление наших студентов, но и снабжает их необходимой базой знаний для их дальнейшей работы (точность расчета, планирование и обработка результатов эксперимента, построение и исследование математических моделей различных процессов). В третьем семестре студенты уже изучают учебную дисциплину «Прикладная математика», которая дает преподавателю широкие возможности для формирования профессиональных качеств личности техника.
Для решения различных профессиональных задач будущему специалисту необходимы знания основ математического моделирования технических систем, методов расчета и анализа параметров схемы замещения системы электроснабжения и рабочего режима, решения оптимизационных задач, современного программного обеспечения персональных компьютеров.
Как правило, математические методы не разрабатываются для решения конкретных задач. Именно поэтому формулировка любой технической задачи должна быть переведена на формальный математический язык, т.е. записана с помощью определенных математических выражений. Будущий специалист должен знать математические методы, предназначенные для решения обобщенных инженерных задач и уметь выбрать целесообразный метод для решения конкретной технической задачи.
Решение задач небольшой размерности можно выполнить традиционными вычислениями с помощью калькулятора. Решение же реальных задач, размерность которых может быть достаточно большой, возможно лишь с помощью ЭВМ. Поэтому будущий специалист должен знать программное обеспечение современных персональных компьютеров и уметь пользоваться этим обеспечением.
Предлагаем методические указания к практическому занятию по теме «Транспортная задача» по учебной дисциплине «Прикладная математика», разработанные в соответствии с ФГОС СПО по специальности 210420 «Техническая эксплуатация транспортного радиоэлектронного оборудования (по видам транспорта)» базовой подготовки.
Практическое занятие рассчитано на 4 академических часа и включает в себя два этапа проведения:
1 этап. Решение транспортной задачи непосредственным вычислением;
2 этап. Решение транспортной задачи с помощью инструментальных сред MS Excel и MathCAD.
Результатом практического занятия является отчет студента о выполнении заданий. Отчет оформляется на листах формата А4 со штампом, в котором указывается шифр практической работы, ФИО студента и дата сдачи работы, ФИО преподавателя, проверяющего работу. Отчет включает в себя условие решаемой задачи, математическую модель задачи, решение транспортной задачи непосредственным вычислением, распечатку результатов решения транспортной задачи в MS Excel и MathCAD, включая фрагмент эл.листа с условием задачи и отчет по результатам.
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №6-7
ТРАНСПОРТНАЯ ЗАДАЧА
(4 часа)
ЦЕЛЬ РАБОТЫ:
Формирование навыков составления математических моделей транспортных задач;
Формирование навыков определения опорных планов транспортных задач методами северо-западного угла, минимальной стоимости и аппроксимации Фогеля;
Формирование навыков оптимизации опорных планов транспортных задач;
Формирование навыков решения транспортных задач в MS Excel с использованием надстройки «Поиск решения»;
Формирование навыков решения транспортных задач в MathCAD с использованием функции Minimize.
СОДЕРЖАНИЕ РАБОТЫ:
Ознакомьтесь с теоретическим материалом;
Выполните задания из пункта 4;
Ответьте на контрольные вопросы.
ПЕРЕЧЕНЬ ОБОРУДОВАНИЯ И ПО:
ПК, принтер;
MS Office 2007;
MS Excel 2007с надстройкой «Поиск решения»;
MathCAD.
ВЫПОЛНЕНИЕ:
Ознакомьтесь с условием транспортной задачи. Составьте ее математическую модель.
Определите опорный план транспортной задачи тремя методами: Северо-западного угла; Минимальной стоимости; Аппроксимации Фогеля. Для каждого плана вычислите значение целевой функции.
Выберите из найденных опорных планов тот, который дает лучший результат и проверьте его на оптимальности. Если план не оптимален, то оптимизируйте его.
Решите транспортную задачу, используя утилиту «Поиск решения» в MS Excel.
Решите транспортную задачу в MathCAD с использованием функции Minimize.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ:
Транспортной задачей линейного программирования называется задача, которая состоит в определении минимального значения функции
F=i=1mj=1ncijxij (1)при условиях
i=1mxij=bj, j=1,n (2)j=1nxij=ai, i=1,m (3)xij≥0, i=1,m, j=1,n (4)где cij, ai, bj – заданные постоянные величины.
Модель транспортной задачи называется закрытой, если выполняется равенство i=1mai=j=1nbj.
Опорный план транспортной задачи называется невырожденным, если содержит ровно n+m-1 ненулевое значение.
При заполнении выбранной ячейки таблицы модели транспортной задачи используют правило:
Сравниваются количества запасов и потребностей. То количество, которое меньше, записывается в рассматриваемую ячейку. Если это запасы, то из рассмотрения убирается строка, в противном случае убирается столбец. Оставшаяся величина уменьшается на количество, записанное в рассматриваемую ячейку.
В соответствии с методом северо-западного угла для заполнения выбирается ячейка в левом верхнем углу невычеркнутой части таблицы.
В соответствии с методом минимальной стоимости для заполнения выбирается ячейка, тариф перевозок в которой является наименьшим.
В соответствии с методом аппроксимации Фогеля в каждом столбце и каждой строке вычисляются разности между двумя максимальными тарифами. Среди вычисленных разностей выбирается минимальная. В соответствующем элементе таблицы выбирается минимальный тариф – эта ячейка и заполняется.
Задание 1.
По условию задачи Вашего варианта:
Установите количество переменных.
Составьте целевую функцию. Если по условию задачи требуется определить максимальное значение целевой функции, то используя правила работы с условиями ЗЛП преобразуйте ее так, чтобы она стремилась к минимуму.
Составьте и запишите систему ограничений.
Запишите условие транспортной задачи в виде таблицы. Определите форму записи модели открытая или закрытая. Если модель является открытой, то измените таблицу так, чтобы модель стала закрытой.
Определите опорный план в соответствии с методом северо-западного угла.
Проверьте его на не вырожденность.
Вычислите значение целевой функции для найденного плана.
Определите опорный план в соответствии с методом минимальной стоимости.
Проверьте его на не вырожденность.
Вычислите значение целевой функции для найденного плана.
Определите опорный план в соответствии с методом аппроксимации Фогеля.
Проверьте его на не вырожденность.
Вычислите значение целевой функции для найденного плана.
Установите, какой из найденных планов дает лучший результат.
Проверьте его на оптимальность методом потенциалов.
Если план не оптимален, то постройте цикл и проведите операцию сдвига по циклу.
Вновь полученный план проверьте на оптимальность.
Проведите решения до получения оптимального плана. Для него вычислите значение целевой функции.
Задание 2.
Для условия задачи Вашего варианта проверьте ее в инструментальной среде MS Excel 2007 с надстройкой “Поиск решения». Для этого выполните следующие шаги:
1. В ячейку А1 введите «Практическая работа №7», в ячейку С2 введите свои фамилию и имя, в ячейку F1 введите шифр группы.
2. Объедините ячейки А3-А5 и введите «Электростанции». Объедините ячейки В3-В5 и введите «Мощность электростанций и населенных пунктов». Объедините ячейки С3-F3 и введите «Населенные пункты». В ячейки А6, А7, А8 введите «A1», «A2», «A3». В ячейки С4, D4, Е4 и F4 введите «В1», «В2», «В3» и «В4».
3. В ячейки В6, В7, В8 … впишите значения A1, A2, A3 … Выделите их голубым цветом.
4. В ячейки С4, D4, Е4, F4… впишите значения В1, В2, В3, В4…. Выделите их голубым цветом.
5. В блок B6:F8 (последняя ячейка соответствует примеру) внесите значения стоимостей передачи электроэнергии.6. В конце цветного столбца «Мощность электростанций и населенных пунктов» и цветной строки создайте формулы из суммы переменных цветных столбца и строки. Выделите их зеленым цветом.
7. В ячейку А10 введите «Баланс:». В ячейке В10 создайте формулу «=ЕСЛИ(B9=G5;"Баланс есть";"Баланса нет")». Выделите ее цветом. Если при решении задачи появится «Баланса нет», то модель задачи привести к закрытой форме записи.
8. Объедините ячейки А13-А15 и введите «Электростанции». Объедините ячейки В13-В15 и введите «Мощность электростанций и населенных пунктов». Объедините ячейки С13-F13 и введите «Населенные пункты». В ячейки А16, А17, А18 введите «A1», «A2», «A3». В ячейки С14, D14, Е14 и F14 введите «В1», «В2», «В3» и «В4».
9. В ячейках В16, В17, В18 … создайте формулы сумм значений переменных в ячейках С16-F16, С17-F17, С18-F18… Выделите их голубым цветом.
10. В ячейках С14, D14, Е14, F14… создайте формулы сумм значений переменных в ячейках С16-С18, D16-D18, E16-E18, F16-F18… Выделите их голубым цветом.
11. В блок B16:F18 (последняя ячейка соответствует примеру) внесите значения 0.12. В ячейку А19 введите «Затраты». В ячейку В19 внесите формулу, полученную как сумму произведений ячеек C6:F8 на значения ячеек C16:F18. Выделите ее желтым цветом.
13. Перейдите к утилите «Поиск решения» (Данные - Поиск решения).
14. Заполните разделы окна «Поиск решения» согласно рисунку 1.

Рисунок 1. Окно «Поиск решения».
Нажмите кнопку «Выполнить». В появившемся окне выберите «Сохранить найденные значения», Тип отчета «Результаты» и нажмите кнопку «ОК» (см. рисунок 2).

Рисунок 2. Окно «Результаты поиска решения».
15. Скопируйте и распечатайте фрагмент эл.листа с условием задачи и отчет по результатам.
Задание 3.
Для условия задачи Вашего варианта проверьте ее в MathCAD с использованием функции Minimize. Для этого выполните следующие шаги:
Специальной переменной ORIGIN присвойте значение 1
(ORIGIN:=1).
Задайте начальные значения х(i:=1..12, xi:=0).
Задайте общие затраты на передачу электроэнергии
(F(x):= c11∙x1+c12∙x2+c13∙x3+c14∙x4+c21∙x5+c22∙x6++c23∙x7+c24∙x8+c31∙x9+c32∙x10+c33∙x11+c34∙x12,
где cij - стоимость передачи электроэнергии).
Задайте условия
(GIVEN c11∙x1+c12∙x2+c13∙x3+c14∙x4=a1,
c21∙x5+c22∙x6+c23∙x7+c24∙x8=a2,
c31∙x9+c32∙x10+c33∙x11+c34∙x12=a3,
c11∙x1+c21∙x5+c31∙x9=b1,
c12∙x2+c22∙x6+c32∙x10=b2,
c13∙x3+c23∙x7+c33∙x11=b3,
c14∙x4+c24∙x8+c34∙x12=b4
x1≥0, x2≥0, x3≥0, x4≥0, x5≥0, x6≥0,
x7≥0, x8≥0, x9≥0, x10≥0, x11≥0, x12≥0).
5. Используя встроенную функцию Minimize, найдите минимальные значения х1, …, х12.
6. Вычислите минимальную стоимость общих затрат.
ОТЧЕТ ДОЛЖЕН СОДЕРЖАТЬ:
Номер практической работы, ее название, номер выполняемого варианта.
Номер задания.
Условие решаемой задачи.
Математическая модель задачи.
Решение транспортной задачи в ручную.
Распечатка результата решения транспортной задачи в Excel, включающая фрагмент эл.листа с условием задачи и отчет по результатам.
Распечатка результата решения транспортной задачи в MathCAD, включающая фрагмент листа с условием задачи и отчет по результатам.
КОНТРОЛЬНЫЕ ВОПРОСЫ:
Определение транспортной задачи.
Математическая модель транспортной задачи.
Методы поиска опорного плана транспортной задачи.
Метод проверки опорного плана транспортной задачи на оптимальность.
Цикл. Правило сдвига по циклу.
ПРИМЕР ОТЧЕТА ПО ПРАКТИЧЕСКОМУ ЗАНЯТИЮ №6-7.
Практическая работа №6-7. Транспортная задача.
Задача 1. Непосредственное вычисление. От трех электростанций мощностью 22 МВт, 23 МВт и 48 МВт энергию потребляют четыре населенных пункта с объемами потребления 11 МВт, 17 МВт, 33 МВт и 32 МВт. Составьте такой план электрических сетей, чтобы все населенные пункты были обеспечены электроэнергией, а общие затраты на передачу электроэнергии были минимальны. Стоимость передачи электроэнергии от первой электростанции до каждого населенного пункта составляет 15, 20, 7, 5 тыс.рублей, от второй электростанции – 10, 4, 12, 18 тыс.рублей, от третьей электростанции – 3, 2, 12, 13 тыс.рублей.
Решение:
Количество переменных: 3х4=12.
Целевая функция: Fx=15∙x1+20∙x2+7∙x3+5∙x4+10∙x5+4∙x6+12∙x7+18∙x8+3∙x9+2∙x10+12∙x11+13∙x12.
По условию задачи Fx→min.
Система ограничений:
15∙x1+20∙x2+7∙x3+5∙x4≤2210∙x5+4∙x6+12∙x7+18∙x8≤233∙x9+2∙x10+12∙x11+13∙x12≤4815∙x1+10∙x5+3∙x9≤1120∙x2+4∙x6+2∙x10≤177∙x3+12∙x7+12∙x11≤335∙x4+18∙x8+13∙x12≤32xi≥0, i=1,2,..,12.
Запишем в виде таблицы:
Электростанции Населенные пункты
B1B2B3B411 17 33 32
A122 15
20
7
5
A223 10
4
12
18
A348 3
2
12
13
Определим форму записи модели:
i=13ai=22+23+48=93
j=14bj=11+17+33+32=93, модель закрытая.
Определим опорный план.
Метод северо-западного угла:
Электростанции Населенные пункты
B1B2B3B411 17 33 32
A122 15
11 20
11 7
0 5
0
A223 10
0 4
6 12
17 18
0
A348 3
0 2
0 12
16 13
32
x1=min22;11=11→x2=min11;17=11→ первая строка закрыта (x3=0, x4=0); первый столбец закрыт (x5=0, x9=0);
x6=min23;6=6→x7=min17;33=17→ вторая строка закрыта (x8=0); второй столбец закрыт (x10=0);
x11=min48;16=16→x12=min32;32=32→ третья строка закрыта.
Значение целевой функции для найденного плана:
Fx=15∙11+20∙11+7∙0+5∙0+10∙0+4∙6+12∙17+18∙0+
+3∙0+2∙0+12∙16+13∙32=165+220+24+204+182+416=
=1211 тыс.рублей.
Метод минимальной стоимости:
Электростанции Населенные пункты
B1B2B3B411 17 33 32
A122 15
0 20
0 7
0 5
22
A223 10
0 4
0 12
13 18
10
A348 3
11 2
17 12
20 13
0
mincij=c32=2→x10=min48;17=17→x9=min31;11=11→
x10=min20;33=20→ третья строка закрыта (x12=0); первый столбец закрыт (x1=0, x5=0); второй столбец закрыт (x2=0, x6=0);
min(c13, c14,c23, c24)=c14=5→x4=min22;32=22→ первая строка закрыта ( x3=0);
minc23, c24=c23=18→x7=min23;13=13→
x8=min10;10=10→ вторая строка закрыта.
Значение целевой функции для найденного плана:
Fx=15∙0+20∙0+7∙0+5∙22+10∙0+4∙0+12∙13+18∙10+
+3∙11+2∙17+12∙20+13∙0=110+156+180+33+34+240=
=753 тыс.рублей.
Метод аппроксимации Фогеля:
Электро-
станции Населенные пункты B1B2B3B411 17 33 32 A122 15
0 20
0 7
0 5
22 5 8 - -
A223 10
0 4
0 12
23 18
0 6 6 6 6
A348 3
11 2
17 12
10 13
10 1 1 1 1
5 16 5 5 5 - 5 5 7 - 0 5 - - 0 5 max5,16,6,1=16→ выбираем второй столбец →min2,4,20=2→
x10=min48,17=17→ второй столбец закрыт (x2=0, x6=0);
max5,8,6,1=8→ выбираем первую строку →min15,7,5=5→
x4=min22,32=22→ первая строка закрыта (x1=0, x3=0);
max7,5,6,1,0=7→ выбираем первый столбец →min3,10=3→
x9=min31,11=11→ первый столбец закрыт (x5=0);
max5,6,1,0=6→ выбираем вторую строку →min12,18=12→
x7=min23,33=23→ вторая строка закрыта (x85=0);
min12,13=12→x11=min20,10=10→ третий столбец закрыт; x12=min10,10=10.
Значение целевой функции для найденного плана:
Fx=15∙0+20∙0+7∙0+5∙22+10∙0+4∙0+12∙23+18∙0+
+3∙11+2∙17+12∙10+13∙10=110+276+33+34+120+130=
=703 тыс.рублей.
Лучший результат: Fx=703 тыс.рублей.
Проверим его на оптимальность методом потенциалов.
Составим систему уравнений для каждой заполненной клетки:
β4-α1=5, β3-α2=12, β1-α3=3,
β2-α3=2, β3-α3=12, β4-α3=13.
Пусть α1=0, тогда β4=5, α3=-8, β3=4, β2=-6, β1=-5, α2=-8.
Для каждой свободной клетки вычислим αij.
α11=β1-α1-c11=-5-0-15=-20,
α12=β2-α1-c12=-6-0-20=-26,
α13=β3-α1-c13=4-0-7=-3,
α21=β1-α2-c21=-5+8-10=-7,
α22=β2-α2-c22=-6+8-4=-2,
α24=β4-α2-c24=5+8-18=-5.
Так как все найденные αij≤0, то найденный план является оптимальным.
Ответ: Fx=15∙0+20∙0+7∙0+5∙22+10∙0+4∙0+12∙23++18∙0+3∙11+2∙17+12∙10+13∙10=703 тыс.рублей.
Задача 2. Решение задачи в MS Excel 2007.

Рисунок 3. Фрагмент эл.листа с условием и решением задачи.


Рисунок 4. Отчет по результатам решения.
Задача 3. Решение задачи в MathCAD.



Рисунок 5. Решение транспортной задачи в MathCAD.
Список литературы
Лунгу К. Н. Линейное программирование. Руководство к решению задач. - М.: Физматлит, 2005. - 128 с.
Данко П.Е., Попов А.Г., Кожевников Т.Я. Высшая математика в упражнениях и задачах. (В 2-х частях)- М.: Высш.шк, 1986. ч.2 – 416 с.
Истомин Л.А., Степин В.П. Математическое программирование. Методические указания и варианты контрольных работ. Факультет сокращенной подготовки - Екатеринбург: Изд-во Уральский гос. экономич. ун-т, 2003. - 27 с.
Плотников А.Д. Математическое программирование: экспресс-курс - 2-е изд., стер. - Минск : Новое знание,. 2007. - 171 с.
Грешилов А.А. Прикладные задачи математического программирования: Учебное пособие – 2-е изд. – М.: Логос, 2006. – 288 с.
Солодовников А.С. Введение в линейную алгебру и линейное программирование. – М.: Просвещение, 1966. – 184 с.

Приложенные файлы


Добавить комментарий