МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ ЯРОСЛАВА МУДРОГО МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ВЫПОЛНЕНИЯ ЛАБОРАТОРНЫХ РАБОТ ПО КУРСУ ЭКОНОМИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ ДЛЯ СТУДЕНТОВ СПЕЦИАЛЬНОСТИ 311000 ЗЕМЕЛЬНЫЙ КАДАСТР ВЕЛИКИЙ НОВГОРОД 2001
Варенцов Ведение. Целью проведения лабораторных работ по курсу Экономико-математические модели и методы является закрепление теоретических знаний, полученных студентами при изучении теоретической части курса, и приложение этих знаний для решения конкретных задач. При выполнении работ студенты должны научиться работать с двумя программными пакетами ПЛП-88 и Microsoft Excel , а при выполнении итоговой расчетно-графической работы щ и справочной литературой.
После выполнения каждой лабораторной работы студент пишет отчт, в котором должна содержаться подробная информация о проделанной работе. Все отчты студент должен защитить преподавателю, после чего он получает допуск к экзамену по данному предмету. Лабораторная работа 1 Изучение пакета ПЛП-88. Целью проведения данной работы является знакомство с пакетом линейного программирования ПЛП-88. В ходе выполнения данной работы студенты должны выполнить следующие задачи 1.
Прочитать файл plp88.txt . 2. Ознакомиться с функциональными меню и функциональными клавишами каждого меню программы. 3. Научиться запускать программу, вводить задачу в программу, сохранять е на диске, вызывать сохраннную задачу . 1.Общие сведения о программе ПЛП-88. ПЛП-88 – это программа, работающая на IВМ-совместимых персональных компьютерах Искра-1030, EC-1841, IBMPC XTAT под управлением операционной системы
MS DOS. ПЛП-88 позволяет решать задачи линейного программирования ЛП, содержащие до 510 ограничений и 2510 переменных. В этом пакете программ применен модифицированный симплекс-алгоритм. Программа ПЛП 88 позволяет хранить в памяти задачу, управлять ходом вычислений и получать распечатанные выходные данные или направлять их в файл для последующего использования.
Возможен интерактивный и пакетный режим работы. В интерактивном режиме управление процессом выполнения программы осуществляется при помощи клавиш F1,F2 F10. В пакетном режиме роль клавиш выполняют простые команды. Набор числовой экономико-математической модели осуществляется при помощи экранного редактора, встроенного в ПЛП-88, с визуальным контролем на мониторе дисплее.
Задачи ЛП вводятся в таком виде, как они сформулированы, т.е. приведение к канонической форме не требуется. Обозначения переменных и ограничений можно задать или присвоить по умолчанию. Размерность задачи MN можно увеличить или уменьшить во время их ввода или редактирования набора. Матрицу задачи ЛП можно хранить на дискетах или жестком диске винчестере, а также распечатать. Все арифметические операции производятся с двойной точностью.
В процессе решения пользователь может изменить формулировку задачи, а также объемы ограничений, коэффициенты и знаки отношений . 2.Запуск программы. Программа ПЛП-88 находится в поддиректории PLP88, войдя в который выберем файл plp88.exe с помощью курсора. Пуск программы осуществляется при включенном принтере после накрытия файла plp88.exe подсветкой курсором и нажатия клавиши Enter. После загрузки программы на экране монитора появляется листинг вариантов меню
MASTER MENU- главное меню SETUP MENU – меню установки EXECUTION MENU – меню исполнения OUTPUT MENU – меню вывода. Под каждым из четырех меню записан вид работы, который можно выполнять при нажатии одной из функциональных клавиш Fi. Управление ходом вычислений осуществляется также в диалоге с компьютером, то есть в форме ответов на вопросы машины. Для вывода результатов на экран нужно набрать слово
CON, т.е. консоль. Рабочие массивы можно не именовать. Имя для запоминания задачи на жестком диске выбирает пользователь. Если вместо CON будет набрано другое имя, результаты будут записаны в файл. 3. Установка задачи ЛП набор матрицы. Ввод исходных данных или корректировка матрицы ранее подготовленной задачи производятся в setup menu. Для перехода в это меню из главного меню нужно нажать клавишу
F1. SETUP MENU. Экран очищается. Нажмите клавишу F2 NEW PROBLEM новая задача или клавишу F6 OULD PROBLEM – старая задача. При вводе новой задачи F2 высвечиваются вопросы Имя новой задачи PRIMER Целевая функция MIN или MAX Количество ограничений Количество основных переменных После ввода каждого ответа нужно нажимать на клавишу ввод
Ehter. Здесь слово PRIMER -это имя задачи образца. Далее нажимают клавишу F3 ITOR для вывода экранного редактора. В 23-й строке экрана внизу будет запрос имени строки и столбца. Нажмите клавишу Ehter два раза, если Вас устроит имя строки Y.iи имя столбца X.i. Обозначаются 15 строк и 10 столбцов, но это не значит, что
Вы не сможете ввести большее количество строк и столбцов. Используйте клавиши Ins и Del для увеличения числа столбцов, а клавиши PgUp и PgDn для увеличения числа строк. Далее работа заключается в простом заполнении пустых клеток на пересечении столбцов Х и строк Y цифровыми значениями коэффициентов матрицы задачи ЛП. Незаполненные клетки считаются нулевыми. Знаки или устанавливаются перед символами которые отображаются
на экране. Курсор перемещается по экрану с помощью клавиш, отмеченных стрелками вправо, вверх, влево, вниз. 4. Запись сформированной задачи в память. Убедитесь еще раз, что система находится под управлением SETUP MENU. Затем нажмите клавишу F4 SAVE PROBLEM записать задачу. ПЛП88 запрашивает имя файла для запоминания задачи. Придумав и набрав имя задачи латинскими буквами, подтвердите набор нажатием клавиши
Enter. Вам дается шанс изменить имя задачи в вопросе Имя для запоминания задачи PRIMER. PRIMER запоминается как PRIMER YN Ответив Yes Вы подтверждаете имя. Ответив No Вы можете выбрать новое имя. Файл с расширением LP запишите на жесткий диск в поддиректорий PLP88.
Это позволит в следующий раз вызвать задачу в полном объеме, не набирая ее заново. 5. Поиск задачи на диске. Загрузив ПЛП-88, так как это описано в пунктах 2.2 и 2.3, нажмите клавишу F1 для перехода в SETUP MENU, а затем клавишу F6 OLD PROBLEM и имя записанной ранее задачи PRIMER без расширения. Ваша задача становится текущей. Для вывода ее на экран нажмите клавишу
F3 DISPLAY EDITOR и клавишу Enter два раза. 6. Решение задачи ЛП. Для решения задачи симплекс-методом вернитесь в MASTER MENU главное меню. Нажмите функциональную клавишу F9 MASTER MENU. Убедитесь, что в строке определения функциональных клавиш появилось главное меню MASTER MENU, и нажмите клавишу F2 SOLVE PROBLEM решить задачу.
7.Получение отчетов. Работая в MASTER MENU нажмите клавишу F8 OUTPUT MENU меню вывода. Затем нажмите клавишу F1 PRIMAL VALUES прямые значения. ПЛП88 напечатает таблицу основного решения задачи. В этом режиме, кроме того, можно напечатать двойственные оценки DUAL VALUES, провести анализ чувствительности модели и др.
Все эти функции подробно описаны в Руководстве пользователя к пакету линейного программирования ПЛП88. 8.Завершение работы. Ввернитесь в Master menu по клавише F9 и еще раз нажмите эту клавишу F9 END SESSION конец сеанса. ПЛП88 попросит Вас подтвердить конец сеанса. Желаете закончить сеанс YN Y . По Y управление переходит к MS DOS. Лабораторная работа 2
Решение задач линейного программирования в программе ПЛП-88. Целью проведения данной работы является закрепление студентами знаний о программе ПЛП-88. Основной задачей данной работы является получение студентами навыков решения задач линейного программирования с помощью программы ПЛП-88. Рассмотрим на примере процесс решения задачи в данном программном продукте. Задача. Найти минимальное значение целевой функции
Z3X3Х при ограничениях Х-0,5Х0 Х-5Х-5 2Х 3Х7 . Порядок решения задачи следующий 1. Запускаем файл plp88.exe 2. На запрос программы вводим имя файла под которым будет сохранена данная задача например zadacha 3. На следующие запросы просто нажимаем клавишу Enter , и все параметры установятся по как по умолчанию 4. Нажимаем функциональную клавишу F1 и попадаем в MASTER
MENU 5. Для ввода новой задачи нажимаем функциональную клавишу F2 SETUP MENU, в форме диалога отвечаем на поставленные программой вопросы о решаемой задаче. В данном примере Имя новой задачи zadacha Целевая функция minmax min Количество ограничений 3 Количество переменных 2 6. Закончив ввод данных о задаче ,переходим к вводу непосредственно самой задачи.
Нажимаем функциональную клавишу F3 переходим в EXECUTION MENU . Здесь решаемая задача представлена в виде матрицы в ячейки которой необходимо ввести коэффициенты при соответствующих переменных, знаки неравенства и правые части ограничений . 7. Закончив ввод, возвращаемся в MASTER MENU F9 . 8. Нажимаем функциональную клавишу F2 дам команду решить задачу 9.
На появившийся вопрос просто нажимаем Enter 2 раза. 10. Появляется окно решения Это краткое отображение решения задачи ЛП. Параллельно оно посылается на принтер или в файл,если это было предусмотрено при первоначальной установке. Итак, здесь X11,538 X2 1,308. Целевая функция принимает максимальное значение с именем COST 8,53846. В случае некорректной постановки задачи сообщение будет другим .
Символами отображаются искусственные переменные в базисе в промежуточные фазы решения задачи симплекс-методом. Стоит отметить особенность ввода задачи большой размерности 10 переменных и 15 ограничений . Так как на одном экране отображается матрица 10X15 , то для ввода, например, задачи 25Х20 необходимо будет изменить номера переменных 1-10 на 11-20 , потом 21-25 , снова изменить их на 1-10 , и таким же образом ввести ограничения 11-20, изменив номера 1-10 ограничений.
Лабораторная работа 3. Решение задач линейного программирования в программе MICROSOFT EXCEL. Целью проведения данной работы является знакомство с программой электронных таблиц как средством решения задач линейного программирования . В ходе выполнения данной работы студенты должны выполнить следующие задачи 1. Научиться вводить задачи в поле листа таблиц. 2. Уметь проводить настройку параметров решения задач 3.
Получить решение задачи. Программа Excel из состава MS Office может быть использована для решения задач линейного программирования благодаря имеющейся в ней надстройки Поиск решения в меню Сервис. Количество вводимых переменных и ограничений здесь ограничивается лишь размерами самой таблицы. Рассмотрим процесс решения задач на примере, который мы использовали в прошлый раз Задача. Найти минимальное значение целевой функции
Z3X3Х при ограничениях Х-0,5Х0 Х-5Х-5 2Х 3Х7 . 1. Открываем программу – в меню Пуск , Программы выбираем Microsoft Excel. 2. Сразу же сохраняем будущий файл под каким-либо именем Файл , Сохранить как . Например ЭММ. 3. Для наглядного отображения задачи необходимо сделать шаблон под вводимые значения в ячейке А1 напишем Решение задачи на минимум , в ячейке А2 Х1 , в ячейке В2 Х2 . 4. Ячейки А3 и В3 оставляем под значения переменных, которые будут получены
в результате решения задачи. 5. Далее, в ячейки А4-А7 , В4- В7 вводим по порядку коэффициенты при Х1 и Х2 в целевой функции и ограничениях соответственно. 6. В ячейки С5-С7 записываем знаки ограничений, в D5-D7 правые части ограничений. 7. Делаем активной ячейку, в которой будет прописана целевая функция например- G4, в панели инструментов выбираем пункт вставка функции .
В категории функции выбираем математические , функцию сумма произведений . В качестве первого массива выбираем массив А3В3 массив переменных, в качестве второго массив коэффициентов целевой функции- А4-В4 .Нажимаем кнопку OK . В ячейке G4 появилась цифра ноль . 8. Аналогично прописываем ограничения в ячейках G5-G7 как сумму произведений массива переменных и коэффициентов ограничений.
9. В меню Сервис выбираем пункт- Поиск решения . В открывшемся окне устанавливаем целевой ячейку G4 по умолчанию обозначена та ячейка, на которой стоит курсор. Нажимаем кнопку Добавить и вводим ограничения ссылаясь на ячейки с коэффициентами при Х, знаками ограничений, правыми частями. 10. Нажимаем кнопку Параметры, в новом окне устанавливаем галочки на пунктах
Линейная модель и Неотрицательные значения , OK. возвращаемся в предыдущее окно 11. Нажимаем кнопку Выполнить . Если все данные были введены правильно, то получится оптимальное решение Выбираем необходимый нам тип отчта по результатам, по устойчивости, или по пределам. Нажимаем кнопку OK. В ячейках А3 и В3 появились значения переменных, в ячейке G4- значение целевой функции при этих значениях. Лабораторная работа 4.
Основы анализа оптимальных решений по отношению к правым частям ограничений. Целью проведения данной работы является приобретение студентами знаний по проведению анализа полученных оптимальных решений по отношению к правым частям ограничений. В ходе выполнения данной работы студенты должны выполнить следующие задачи 1. Разделить имеющиеся в задаче ограничения на дефицитные и не дефицитные.
2. Определить пределы изменения дефицитных ресурсов. 3. Подтвердить полученное решение с помощью программы ЛП. 4. Определить двойственные оценки. Выполнение выше названных задач покажем на примере, использованном в Лр. 3 . Задача. Найти минимальное значение целевой функции Z3X3Х при ограничениях Х-0,5Х0 Х-5Х-5 2Х 3Х7 . Все задачи, в которых число переменных равно двум имеют
очень наглядное графическое решение. Каждое из ограничений представляет собой формулу некой линии, которая делит плоскость на две полуплоскости, а совместное пересечение получившихся линий даст область решения задачи. График целевой функции, проходя через какую-то точку точки данной области, будет давать конкретное решение координаты этой точки. Чтобы узнать, какая из полуплоскостей является решением ограничения нужно подставить в неравенство координаты любой точки из этой полуплоскости, если неравенство выполняется
то, следовательно, вся полуплоскость является решением, если не выполняется – то решением будет другая полуплоскость. Построим графики каждого из ограничений. Так как ограничения представляют собой график линейной зависимости, то для построения достаточно получить координаты двух точек. В качестве одной из них , для удобства , будем использовать начало координат. 1 Х-0,5Х0 2 Х-5Х-5 3 2Х 3Х7 . Х-0,5Х0 Х-5Х-5 2Х 3Х7 .
Х0 , Х0 Х0 , Х1 Х0 , Х73 Х1 , Х2 Х0 , Х-5 Х0 , Х 7 2 Как видно из графика, решение образуется пересечением 2-го и 3-го ограничения. Таким образом, 2-ое и 3-е ограничения дефицитные, т.е. их изменение влияет на положение точки решения. Координаты точки решения А можно найти решив систему из двух уравнений Х-5Х-5 2Х 3Х7 Х20131,5384 Х17131,3077 Z8,5385 Выполним вторую поставленную задачу определим пределы
изменения дефицитных ресурсов, т.е. проверим до каких величин можно уменьшать и увеличивать правые части ограничений, чтобы они при этом оставались дефицитными. Из графика видно, что перемещение вправо точки решения ничем не ограничивается, поэтому возможно бесконечное увеличение правой части 3-го ограничения. Нижний предел дадут координаты точки В решаем систему уравнений 1-го и 2-го ограничений.
Второе ограничение, перемещаясь вверх, перестат быть дефицитным после точки пересечения 1-го и 3-го ограничений. Подставив координаты этой точки в формулу второго ограничения, получим верхний предел изменения этого ограничения. Решаем систему уравнений 1-го и 3-го ограничений. Нижний предел ограничения дадут координаты точки 720 , дальнейшее уменьшение приведт к тому, что точка решения будет перемещаться вправо по оси Х1. Итак, для второго ограничения -7.875B3.5
Для третьего ограничения 4.444 B Подтверждение нашего решения можно получить в программах линейного программирования ПЛП-88 и Microsoft Excel. Во второй из указанных программ отчт по устойчивости можно получить в результате решения задачи в одного из итоговых отчтов. Microsoft Excel 8.0 Отчет по устойчивостиРабочий лист ЭММ.xlsЛист1Отчет создан 15.11.01 232238Изменяемые ячейкиРезульт.
Нормир.ЦелевойДопустимоеДо пустимоеЯчейкаИмязначениестоимостьКоэффи циентУвеличениеУменьшениеA3X11,538461538 031E301B3X21,307692308031,518Ограничения Результ.ТеневаяОграничениеДопустимоеДопу стимоеЯчейкаИмязначениеЦенаПравая частьУвеличениеУменьшениеG5Огранич.10,88 4615385000,8846153851E30G6Огранич.2-50,2 30769231-58,52,875G7Огранич.371,38461538 571E302,56 Последней нашей задачей в этой лабораторной работе является нахождение двойственных оценок отношения приращения целевой функции к приращению дефицитных ресурсов. Двойственная оценка находится по формуле Z – Zmax
Y B-B Знаменатель представляет собой разность двух возможных значений правых частей ограничений, а числитель разность значений целевой функции при этих значениях правых частей ограничений. В нашем случае, для второго ограничения Х-5Х-5 , при B0 B3,5 и соответствеено Z 9,6923 и Zmax10,5 , Y0.2307 Для третьего ограничения 2Х 3Х7 , при B5 B7 и соответствеено
Z5,7692 и Zmax8,5385 , Y1,3846. В отчте по устойчивости значения двойственных оценок можно найти в графе Теневая цена. Лабораторная работа 5. Анализ оптимальных решений по отношению к коэффициентам целевой функции. Целью проведения данной работы является приобретение студентами знаний по проведению анализа полученных оптимальных решений по отношению к коэффициентам целевой функции. В ходе выполнения данной работы студенты должны выполнить следующие задачи 1.
Найти оптимальное решение для имеющейся задачи. 2. Определить дефицитные ресурсы. 3. Найти допустимые пределы изменения коэффициентов целевой функции. При изменении коэффициентов целевой функции происходит е поворот вокруг точки оптимального решения, в связи с чем, возникает проблема сохранения устойчивости. Решение будет устойчивым до совпадения графика целевой функции с графиком любого дефицитного ресурса.
Рассмотрим на примере весь процесс выполнения назначенных задач. Задача. Найти минимальное значение целевой функции Z 6X 5X , при ограничениях 4Х3Х60 2ХX24 X2X20 X18 X25. Решение выполним графически. 1 4Х3Х60 2 2ХX24 3 X2X20 Z 6X 5X Х0 X20 Х 0 X24 Х0 X10 X0 X0 X0 Х15 X0 Х12 X0
Х20 X6 Х-5 На схематическом графике видно, что точкой решения задачи будет точка А. Е координаты найдм из решения системы уравнений 2-го и 3-го ограничений 2ХX24 X2X20 Х 283 X163 Z 2483 Теперь нам необходимо узнать какие значения могут принимать коэффициенты целевой функции. Для этого нужно решить две системы уравнений, первое состоящее из целевой функции и 2-го ограничения, второе из целевой функции и3-го ограничения. Причм коэффициенты целевой функции мы поочердно заменяем
переменными С и С. Второй неизвестной будет выступать величина Z. СX 5XZ 2ХX24 Разделим первое уравнение на 5, получим С5X XZ5 2ХX24 Следовательно С52 , С10 и Z524 , Z120. 6X СXZ 2ХX24 Умножим второе уравнение на 3, получим 6X СXZ 6Х3X72 С3 , Z72 . СX 5XZ X2X20 Первое уравнение умножим на 2 , а второе на 5 2СX 10X2Z 5X10X100 2С5
, С52 2Z100 , Z50. 6X СXZ Х2X20 Второе уравнение умножим на 6 6X СXZ 6Х12X120 С12 , Z120. В итоге имеем – для С 2,5С10 , 50Z120 для С 3С12 , 72Z120. При большом количестве переменных провести анализ в ручную очень тяжело, т.к. графическое решение на плоскости возможно только для двух переменных. Такой анализ поводится на компьютере. Задаются новые значения коэффициентов целевой функции и определяются
граничные значения по изменению координат точки решения и оценки. Лабораторная работа 6. Симплексный метод решения задач линейного программирования. Целью проведения данной работы является приобретение студентами знаний по проведению анализа полученных оптимальных решений по отношению к коэффициентам целевой функции. В ходе выполнения данной работы студенты должны выполнить следующие задачи 1.
Определить каким способом решается предложенная преподавателем задача. 2. Выполнить решение задачи в виде таблиц. При решении задач линейного программирования с большим числом переменных невозможно применение графического метода. Решение проводится аналитическим методом симплексным, с любым количеством переменных и ограничений. Наиболее удобно представление этого метода в табличной форме.
Все возможные задачи, решаемые симплексным методом сводятся к двум разновидностям – в зависимости от вида ограничений. Первый – симплексный метод с естественным базисом, второй с искусственным. Первым методом решаются задачи с ограничениями вида . Следует отметить также, что ограничения типа могут быть приведены к типу умножением на 1 всего уравнения, но также важно знать, что правые части ограничений всегда должны быть неотрицательны.
Второй метод применяется для решения задач с ограничениями содержащими и знак равенства. Частным случаем этого метода является метод решения задач с ограничениями различного вида, позволяющий примерно вдвое сократить объм вычислений. Рассмотрим два примера отдельно для каждого случая. Задача 1. Найти максимальное значение целевой функции Z -XX3Х, при ограничениях 2X-XX1 4X-2XX -2 3XX 5. Умножив на -1 целевую функцию и 2-ое ограничение,
мы сведм решение задачи к решению на минимум, и правая часть второго ограничения станет положительной. Получаем F X-X-3Х min 2X-XX1 -4X2X-X2 3XX 5. Для того чтобы перейти от неравенств к равенствам необходимо ввести дополнительные переменные базисные. В ограничениях вида они будут естественными, в других случаях они будут искусственными. 2X-XXX1 -4X2X-XX2 3XX X5 Обязательно должно выполняться условие, чтобы в каждом ограничении было по одной переменной не входящей
в другие ограничения. Эти переменные вводим в целевую функцию с нулевыми коэффициентами F X-X-3Х0 X0 X0 X min Для составления симплексной таблицы нужно получить первое решение следующим образом XXX0 , X1 , X2 , X5. п.п. Базис оценка Св. член1 X1-1 X2-3 X30 X40 X50 X61X4012-111002X502-42-10103X605301001M1 0-113000 По индексной строке мы судим об оптимальности получившегося решения.
Для задач на минимум показатель оптимального решения отсутствие положительных значений. Как правило, первое решение далеко не оптимальное, что мы и имеем в данном случае. Для дальнейшего решения задачи необходимо найти разрешающий элемент. Чтобы его найти в индексной строке выбираем максимальное положительное число в данном случае 3. Мы нашли разрешающий столбец. Теперь в этом столбце находим разрешающий элемент, как минимальное отношение
величины из графы свободный член, к величине из данного столбца, исключая отрицательные значения Biximin, xi 0. Разрешающим элементом будет число 1. Ту переменную, которая находится в базисе напротив разрешающего элемента мы выводим из базиса, на е место вводится переменная из разрешающего столбца. Х4 меняем на Х3. Оценка новой базисной переменной находится в этом же разрешающем столбце.
Следующую симплексную таблицу составляем по следующим правилам 1. Вместо разрешающего элемента пишем число 1. 2. Все значения разрешающего столбца равны 0. 3. Все элементы разрешающей строки делим на разрешающий элемент. 4. Все остальные значения рассчитываем следующим образом. Ячейка разрешающего элемента и ячейка искомого значения образуют собой сторону или диагональ прямоугольника.
Находим произведение разрешающего элемента и диагонального ему элемента по главной диагонали, и произведение двух других элементов по побочной диагонали. Теперь находим разность между получившимися значениями и делим е на разрешающий элемент. п.п. Базис оценка Св. член1 X1-1 X2-3 X30 X40 X50 X61X3-312-111002X503-2101103X6041-10-101 M1-3-740-300 Как видно из индексной строки решение не является оптимальным, возможно дальнейшее улучшение
результата. Проделываем все операции снова. Получаем новую таблицу п.п. Базис оценка Св. член1 X1-1 X2-3 X30 X40 X50 X61X3-3-40012102X2-13-2101103X601300-2-1 1M1-15100-7-4-13 В индексной строке имеется одно положительное значение, продолжаем наше решение п.п. Базис оценка Св. член1 X1-1 X2-3 X30 X40 X50 X61X3-3-40012102X2-13 230102 131 23233X1113300-23-1313M1-15 130-130-6 23-3 23-13 Наконец мы получаем конечное решение в индексной строке нет положительных оценок.
Переменные, которые находятся в базисе получили значения X113 , Х23 23 , Х3-3 , F-15 13 , все остальные переменные равны нулю. Рассмотрим теперь процесс решения задачи с искусственным базисом. Задача 2 . Найти максимальное значение целевой функции Z-5X-3X-4XX , при ограничениях Х3Х2Х2Х3 , 2Х2ХХ3 .
Так как ограничения уже представляют собой уравнения, вводимые переменные будут искусственными. Х3Х2Х2ХX3 2Х2ХХХX3 . Z -5X-3X-4ХX0 X0 X max Умножив на -1 целевую функцию сводим решение задачи к решению на минимум. Нулевые коэффициенты при искусственных переменных изменятся на некоторые большие числа М. Z 5X3X4Х-XМ XМ X min Получаем первое возможное решение XXХX0, X3, X3. Составляем симплексную таблицу п.п.БазисОценкаСв. член5
Х13 Х24 Х3-1 Х4М Х5М Х61Х5М31322102Х6М3221101М1 М20 6-5 3-3 5-4 31 30 00 0 В методе решения с искусственным базисом в таблице заполняется две индексные строки. Они заполняются по следующей формуле n,m Zj Cj Ai,j Cij Ci i,j1 Проще говоря находим сумму произведений столбца переменной и столбца оценки, коэффициент при М записываем в строку М2 , а свободный член в М1 строку.
В строке М2 находим максимальное положительное число и в этом столбце разрешающий элемент. Дальнейший ход решения аналогичен методу с естественным базисом. Когда все оценки в строке М2 перестанут быть положительными, в следующей таблице начинаем работать со строкой М1, так же добиваемся отсутствия положительных оценок. п.п.БазисОценкаСв. член5 Х13 Х24 Х3-1 Х4М Х5М Х61Х23113123231302Х6М1430-13-13-231М1
М23 1-4 430 0-2 -133 -131 -530 0 п.п.БазисОценкаСв. член5 Х13 Х24 Х3-1 Х41Х23340134342Х153410-14-14М1 М26 10 00 0-3 02 0 Искусственные переменные вышли из базиса, и в дальнейшем их можно не рассматривать. п.п.БазисОценкаСв. член5 Х13 Х24 Х3-1 Х41Х4-11043112Х15111300М140-83-50 Получили оптимальное решение X1 1, X41 , Z4. Лабораторная работа 7.
Составление и решение двойственных задач. Целью проведения данной работы является приобретение студентами знаний по проведению анализа полученных оптимальных решений по отношению к коэффициентам целевой функции. В ходе выполнения данной работы студенты должны выполнить следующие задачи 1. К имеющейся задаче линейного программирования составить двойственную задачу. 2. Проверить правильность составления двойственной задачи.
3. Получить решение двойственной задачи и сравнить его с решением прямой. Каждой задаче линейного программирования соответствует двойственная задача. Для получения двойственной задачи нужно 1 Каждому ограничению прямой задачи поставить в соответствие оценку ресурса 2 Транспонировать матрицу коэффициентов ограничений 3 Расставить знаки ограничений. Для симметричных задач все ограничения которой представлены неравенствами
одного вида, знаки ограничений меняем на противоположные. Для несимметричных задач ограничения которых содержат знаки равенства вводим дополнительные искусственные переменные, все ограничения приводим к виду равенств. Знаки ограничений расставляем в соответствии с таблицей Прямая задачаДвойственная задачаЦелевая функцияЦелевая функцияЗнак ограниченияПеременныеMaxMinНе огранич.
MinMaxНе огранич. Рассмотрим на примере переход от прямой задачи к двойственной. Z -2X5XXmin 7X2X11Х 13 5X6X-3X25 3X8X2X16 Все неравенства приводим к равенствам 7X2X11ХХ13 Y 5X6X-3X25 Y 3X8X2XХ16 Y Коэффициентами новой целевой функции будут правые части ограничений, а правыми частями ограничений коэффициенты целевой функции. F13Y25Y16Ymax 7Y5X3Х-2 2Y6Y8Y5 11Y-3Y2Y1 Учитывая введнные нами искусственные переменные, вводим два дополнительных ограничения
Y0 -Y0 Учитывая, то что правые части ограничений должны быть положительны, умножаем первое ограничение на -1 F13Y25Y16Ymax -7Y-5X-3Х2 2Y6Y8Y5 11Y-3Y2Y1 Y0 -Y0 Это окончательный вид искомой двойственной задачи. Для проверки правильности составления двойственной задачи нужно проверить выполнение четвртого свойства двойственных задач. Отметим свойства двойственной задачи 1.
Теоретически в оптимальных решениях целевая функция прямой задачи равна целевой функции двойственной. 2. Если прямая задача имеет n переменных и m ограничений, то обратная задача – m переменных и n ограничений. 3. В симметричных двойственных задачах, переменные прямой и двойственной задачи положительны. В несимметричных задачах переменные могут быть отрицательными. 4. Двойственная задача к двойственной прямая. 5. Прямая и двойственная задача могут выступать в качестве
прямой. 6. Переменные двойственной задачи равны оценкам переменных прямой задачи, и наоборот. 7. Столбцы коэффициентов прямой задачи строки коэффициентов двойственной. 8. Правые части ограничений прямой задачи коэффициенты целевой функции двойственной задачи. 9. Коэффициенты целевой функции прямой задачи правые части ограничений двойственной задачи. 10. Если прямая задача не имеет решения, то и двойственная тоже не имеет решения.
Сравнив решения прямой и двойственной задачи, делаем вывод о правильности выполнения всех действий. Решение прямой задачи Z 15,4375 X0,875-1,156 X3,4371,2187 X00. В скобках указаны оценки переменных. Решение двойственной задачи F15,4375 Y -1,1560,875 Y3,4371,2187 Y00. Лабораторная работа 8. Решение транспортной задачи. Целью проведения данной работы является приобретение студентами знаний
о таком частном случае задач линейного программирования как транспортная задача. В ходе выполнения данной работы студенты должны выполнить следующие задачи 1. Решить предложенную преподавателем транспортную задачу одним из существующих методов. 2. Проверить оптимальность получившегося решения с помощью программы линейного программирования. 3. Получить представление о решении транспортных задач с дополнительными ограничениями.
Транспортная задача является частным случаем общей распределительной задачи линейного программирования. Е смысл в оптимальном распределении производимых поставщиками товаров между потребителями. Е составление невозможно без ряда допущений рассматривается перевозка однотипного груза, одинаковым транспортом одинаковой грузоподъмности. Весь груз от поставщиков должен быть доставлен потребителям. Целевая функция транспортной задачи может быть на минимум стоимости перевозок или на минимум затраченного
на перевозку времени. Особенности решения задачи происходят из того, что в ней используется двумерный массив индексов переменных. Программа ПЛП-88 имеет специальную подпрограмму для решения транспортных задач. Она находится в каталоге Tran , файл Potenc1.exe . Задача решаема только в том случае, если выполняется условие равенства суммы произведнных к перевозке товаров и суммы потребностей потребителей m n ai bj i1 j1
В этом случае задача называется закрытой. Если условие не выполняется число товаров у поставщиков меньше необходимого потребителям количества товаров или наоборот то для решения задачи необходимо ввести дополнительного поставщика или потребителя. В ручную задача может быть решена методом северо-западного верхнего угла, методом минимальной стоимости, способом двойного предпочтения, методом потенциалов. Рассмотрим на примере весь процесс решения задачи примере.
Задача. Число поставщиков равно трм, a7, a6, a8. Число потребителей равно четырм, b5, b6, b6, b5. Таблица стоимости перевозок выглядит следующим образом. 21 25 26 22 С 27 33 32 31 39 40 41 35 Проверим выполнение условие равенства количества товаров у поставщиков и объма товаров необходимого потребителям. a21, b22. Так как ai bj задача открыта. Вводим дополнительного поставщика a1.
В таблицу стоимости добавляем четвртую строку с нулевыми величинами 21 25 26 22 С 27 33 32 31 39 40 41 35 0 0 0 0 Первый способ решения методом верхнего угла. Это самый простой способ, но полученное таким способом допустимое решение далеко от оптимального. Делаем шаблон таблицы, и заполняем графы начиная с левого верхнего угла. У первого поставщика 7 единиц товаров, а первому потребителю нужно 5 единиц.
Записываем первому потребителю максимально возможное количество товара 5. Оставшиеся у первого поставщика 2 единицы товара записываем второму потребителю. Всего ему нужно 6 единиц, недостающие 4 берм у второго поставщика. Оставшиеся у второго поставщика 2 единицы товара записываем третьему потребителю, которому ещ не хватает 4 единицы. Их берм у третьего поставщика. Последние 4 единицы записываем четвртому потребителю.
У четвртого искусственного поставщика 1 единицу товара записываем четвртому потребителю. Все товары успешно распределились. b5b6b6b5a7 5 2a6 4 2a8 4 4a1 1 Подсчитаем, чему будет равна целевая функция Z521225433232441435655 Как видно, искусственно введнная одна единица товара не играет роли при подсчте целевой функции. Второй способ решения метод минимальной стоимости.
В этом методе сначала заполняются ячейки с минимальными тарифами, а затем распределяются остальные ресурсы. Заполнение возможно по строкам и по столбцам. Заполненная по строкам таблица выглядит следующим образом b5b6b6b5a7 5 2a6 1 5a8 6 2 a1 1 Рассчитываем целевую функцию в этом случае Z521226132531640241666 Таблица, заполненная по столбцам b5b6b6b5a7 5 2 a6 6 a8 3 5a1 1
Z521225632340535642 Как видно, результат в таблице, заполненной по столбцам имеет лучший результат чем результат в таблице, заполненной методом северо-западного угла. Третий способ двойного предпочтения. Максимально заполняем в первую очередь ячейки с минимальными тарифами. b5b6b6b5a7 5 2 a6 6 a8 3 5a1 1 В данном случае результат совпал с результатом заполнения таблицы методом минимальной стоимости по столбцам. Выше описанные методы позволяют получить быстрый результат, но этот
результат может быть и не лучшим. Так как транспортная задача является частным случаем задач линейного программирования, она может быть решена с применением алгоритма симплексного метода. Этот метод называется методом потенциалов. Сначала таблица решения заполняется одним из простых способов, затем рассчитывается потенциал всех клеток таблицы и по результатам этих расчтов делается вывод об оптимальности полученного решения. Потенциал всех заполненных клеток равен нулю.
Wij0 Потенциал не заполненных клеток может быть положительным или отрицательным и рассчитывается по формуле Wijсij-uivj, где ui – потенциал строки, vj- потенциал столбца, а cij – оценка перевозки. Система потенциалов может быть рассчитана только для невырожденного плана, т.е. если выполняется условие число перевозок nm-1 , где n и m ограничения по поставщикам и по потребителям. Изначально задам потенциал строки или столбца равным какому-либо числу удобно использовать 0.
Далее рассчитываем остальные потенциалы. При решении задачи на минимум оптимальное решение при отсутствии отрицательных характеристик. Рассчитаем потенциалы клеток нашей таблицы. b5b6b6b5a7 5 2 a6 6 a8 3 5a1 1 V21, V25, V32, V20 U0, U0, U15, U25. W0 , W0 , W-6, W2 W6 , W8 , W 0 , W11 W13, W0, W-6, W0 W-46,W0, W-57,W-45. Видим, что решение не является оптимальным. Необходимо дальнейшее улучшение решения.
Данная задача, решнная в программе ПЛП-88 получила такое решение Z121427625232341535641. b5b6b6b5a7 1 6 a6 4 2 a8 3 5a1 1 В транспортную задачу могут быть введены дополнительные ограничения с целью выполнения заданных условий. Например, заранее известно, что отсутствуют перевозки, между какими- либо пунктами , или эта величина известна , или она не должна превышать указанной величины.
Для выполнения поставленных условий нужно поступить следующим образом в первом случае в ячейках с отсутствующими перевозками нужно поставить очень большую оценку на два три порядка выше остальных, и в результате решения они останутся не заполненными. Во втором случае нужно вычесть известную величину и у поставщика и у потребителя и поставить большую оценку в эту клетку. В третьем случае вычитаем у поставщика и у потребителя указанную величину.