Методичка для выполнения лабораторных работ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

НОВГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ ЯРОСЛАВА МУДРОГО

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

ДЛЯ ВЫПОЛНЕНИЯ ЛАБОРАТОРНЫХ РАБОТ ПО КУРСУ:

«ЭКОНОМИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ»

ДЛЯ СТУДЕНТОВ СПЕЦИАЛЬНОСТИ 311000

«ЗЕМЕЛЬНЫЙ КАДАСТР»

ВЕЛИКИЙ НОВГОРОД

2001

©Варенцов

Ведение.

Целью проведения лабораторных работ по курсу «Экономико-математические модели и методы» является закрепление теоретических знаний, полученных студентами при изучении теоретической части курса, и приложение этих знаний для решения конкретных задач.

При выполнении работ студенты должны научиться работать с двумя программными пакетами – «ПЛП-88» и «Microsoft Excel®» , а при выполнении итоговой расчетно-графической работы ёщё и справочной литературой.

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

Лабораторная работа № 1

«Изучение пакета ПЛП-88».

Целью проведения данной работы является знакомство с пакетом линейного программирования «ПЛП-88».

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

1. Прочитать файл «plp88.txt» .

2. Ознакомиться с функциональными меню и функциональными клавишами каждого меню программы.

3. Научиться запускать программу, вводить задачу в программу, сохранять её на диске, вызывать сохранённую задачу .

1.Общие сведения о программе «ПЛП-88».

ПЛП-88 - это программа, работающая на IВМ-совместимых персональных компьютерах ("Искра-1030", EC-1841, IBM/PC (XT/AT)) под управлением операционной системы MS DOS.

ПЛП-88 позволяет решать задачи линейного программирования (ЛП), содержащие до 510 ограничений и 2510 переменных. В этом пакете программ применен модифицированный симплекс-алгоритм.

Программа ПЛП 88 позволяет хранить в памяти задачу, управлять ходом вычислений и получать распечатанные выходные данные или направлять их в файл для последующего использования. Возможен интерактивный и пакетный режим работы. В интерактивном режиме управление процессом выполнения программы осуществляется при помощи клавиш F1,F2,...,F10. В пакетном режиме роль клавиш

выполняют простые команды.

Набор числовой экономико-математической модели осуществляется при помощи экранного редактора, встроенного в ПЛП-88, с визуальным контролем на мониторе (дисплее).

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

Размерность задачи (M*N) можно увеличить или уменьшить во время

их ввода или редактирования (набора). Матрицу задачи ЛП можно хранить на дискетах или жестком диске ("винчестере"), а также распечатать.

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

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 (DISPLAY EDITOR) для вывода экранного редактора. В 23-й строке экрана (внизу) будет запрос имени строки и столбца. Нажмите клавишу Ehter два раза, если Вас устроит имя строки Y.iи имя столбца X.i. Обозначаются 15 строк и 10 столбцов, но это не значит, что Вы не сможете ввести большее количество строк и столбцов. Используйте клавиши Ins и Del для увеличения числа столбцов, а клавиши PgUp и PgDn для увеличения числа строк.

Далее работа заключается в простом заполнении пустых клеток на пересечении столбцов Х и строк Y цифровыми значениями коэффициентов матрицы задачи ЛП. Незаполненные клетки считаются нулевыми. Знаки > или < устанавливаются перед символами, =, которые отображаются на экране. Курсор перемещается по экрану

с помощью клавиш, отмеченных стрелками (вправо, вверх, влево, вниз).

4. Запись сформированной задачи в память.

Убедитесь еще раз, что система находится под управлением SETUP MENU. Затем нажмите клавишу F4 (SAVE PROBLEM – записать задачу). ПЛП88 запрашивает имя файла для запоминания задачи.

Придумав и набрав имя задачи латинскими буквами, подтвердите набор нажатием клавиши Enter.

Вам дается шанс изменить имя задачи в вопросе:

Имя для запоминания задачи? PRIMER.

PRIMER запоминается как PRIMER (Y/N)?

Ответив 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 попросит Вас подтвердить конец сеанса.

Желаете закончить сеанс ( Y/N ) ? Y . По Y управление переходит к MS DOS.

Лабораторная работа № 2

«Решение задач линейного программирования в программе ПЛП-88».

Целью проведения данной работы является закрепление студентами знаний о программе «ПЛП-88».

Основной задачей данной работы является получение студентами навыков решения задач линейного программирования с помощью программы «ПЛП-88».

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

Задача. Найти минимальное значение целевой функции Z=3X?+3Х? при ограничениях: Х?-0,5Х??0; Х?-5Х??-5; 2Х? +3Х??7 .

Порядок решения задачи следующий:

1. Запускаем файл plp88.exe;

2. На запрос программы вводим имя файла под которым будет сохранена данная задача (например “zadacha”);

3. На следующие запросы просто нажимаем клавишу «Enter» , и все параметры установятся по как по умолчанию;

4. Нажимаем функциональную клавишу F1 и попадаем в MASTER MENU;

5. Для ввода новой задачи нажимаем функциональную клавишу F2 (SETUP MENU), в форме диалога отвечаем на поставленные программой вопросы о решаемой задаче.

В данном примере:

Имя новой задачи? zadacha

Целевая функция (min\max) min

Количество ограничений 3

Количество переменных 2

1. Закончив ввод данных о задаче ,переходим к вводу непосредственно самой задачи. Нажимаем функциональную клавишу F3 ( переходим в EXECUTION MENU ) . Здесь решаемая задача представлена в виде матрицы в ячейки которой необходимо ввести коэффициенты при соответствующих переменных, знаки неравенства и правые части ограничений .

2. Закончив ввод, возвращаемся в MASTER MENU (F9) .

3. Нажимаем функциональную клавишу F2 – даём команду решить задачу;

4. На появившийся вопрос просто нажимаем Enter 2 раза.

5. Появляется окно решения:

Это краткое отображение решения задачи ЛП. Параллельно оно посылается на принтер или в файл,если это было предусмотрено при первоначальной установке.

Итак, здесь X1=1,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 может быть использована для решения задач линейного программирования благодаря имеющейся в ней надстройки «Поиск решения» в меню «Сервис». Количество вводимых переменных и ограничений здесь ограничивается лишь размерами самой таблицы.

Рассмотрим процесс решения задач на примере, который мы использовали в прошлый раз:

Задача. Найти минимальное значение целевой функции Z=3X?+3Х? при ограничениях: Х?-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 .

Задача. Найти минимальное значение целевой функции Z=3X?+3Х? при ограничениях: Х?-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 , Х?=7/3

Х?=1 , Х?=2 Х?=0 , Х?=-5 Х?=0 , Х?= 7

3 Х?

Z

7/3 A X? B

C

2 -5 0 X? 7/2 Х?

1

22222

Как видно из графика, решение образуется пересечением 2-го и 3-го ограничения.

Таким образом, 2-ое и 3-е ограничения – дефицитные, т.е. их изменение влияет на положение точки решения. Координаты точки решения А можно найти решив систему из двух уравнений:

Х?-5Х?=-5

2Х? +3Х?=7

Х?=20/13=1,5384

Х?=17/13=1,3077

Z=8,5385

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

Из графика видно, что перемещение вправо точки решения ничем не ограничивается, поэтому возможно бесконечное увеличение правой части 3-го ограничения. Нижний предел дадут координаты точки В (решаем систему уравнений 1-го и 2-го ограничений). Второе ограничение, перемещаясь вверх, перестаёт быть дефицитным после точки пересечения 1-го и 3-го ограничений. Подставив координаты этой точки в формулу второго ограничения, получим верхний предел изменения этого ограничения. (Решаем систему уравнений 1-го и 3-го ограничений). Нижний предел ограничения дадут координаты точки (7/2;0) , дальнейшее уменьшение приведёт к тому, что точка решения будет перемещаться вправо по оси Х1.

Итак, для второго ограничения:

-7.875?B?3.5

Для третьего ограничения:

4.444 ?B??

Подтверждение нашего решения можно получить в программах линейного программирования «ПЛП-88» и «Microsoft Excel®». Во второй из указанных программ отчёт по устойчивости можно получить в результате решения задачи в одного из итоговых отчётов.

Microsoft Excel 8.0 Отчет по устойчивости
Рабочий лист: [ЭММ.xls]Лист1
Отчет создан: 15.11.01 23:22:38
Изменяемые ячейки
			Результ.	Нормир.	Целевой	Допустимое	Допустимое
	Ячейка	Имя	значение	стоимость	Коэффициент	Увеличение	Уменьшение
	$A$3	X1	1,538461538	0	3	1E+30	1
	$B$3	X2	1,307692308	0	3	1,5	18
Ограничения
			Результ.	Теневая	Ограничение	Допустимое	Допустимое
	Ячейка	Имя	значение	Цена	Правая часть	Увеличение	Уменьшение
	$G$5	Огранич.1	0,884615385	0	0	0,884615385	1E+30
	$G$6	Огранич.2	-5	0,230769231	-5	8,5	2,875
	$G$7	Огранич.3	7	1,384615385	7	1E+30	2,555555556

Последней нашей задачей в этой лабораторной работе является нахождение двойственных оценок – отношения приращения целевой функции к приращению дефицитных ресурсов.

Двойственная оценка находится по формуле:

Z - Zmax

Y=

B??-B?

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

В нашем случае, для второго ограничения Х?-5Х?=-5 , при B??=0 B?=3,5 и соответствеено Z= 9,6923 и Zmax=10,5 , Y?=0.2307;

Для третьего ограничения 2Х? +3Х?=7 , при B??=5 B?=7 и соответствеено Z=5,7692 и Zmax=8,5385 , Y?=1,3846.

В отчёте по устойчивости значения двойственных оценок можно найти в графе «Теневая цена».

Лабораторная работа № 5.

«Анализ оптимальных решений по отношению к коэффициентам целевой функции».

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

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

1. Найти оптимальное решение для имеющейся задачи.

2. Определить дефицитные ресурсы.

3. Найти допустимые пределы изменения коэффициентов целевой функции.

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

графиком любого дефицитного ресурса.

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

Задача. Найти минимальное значение целевой функции Z= 6X? +5X ?, при ограничениях: 4Х?+3Х??60; 2Х?+X??24; X?+2X??20; X??18; X??25.

Решение выполним графически.

1) 4Х?+3Х?=60 2) 2Х?+X?=24 3) X?+2X?=20 Z= 6X? +5X?

Х?=0 X?=20 Х? =0 X?=24 Х?=0 X?=10 X?=0 X?=0

X?=0 Х?=15 X?=0 Х?=12 X?=0 Х?=20 X?=6 Х?=-5

На схематическом графике видно, что точкой решения задачи будет точка А. Её координаты найдём из решения системы уравнений 2-го и 3-го ограничений:

2Х?+X?=24

X?+2X?=20

Х? 4 5

3

1

18

B

Z 2 12

Х? C

A

0 X? 12 15 20 Х?

Х? = 28/3

X?=16/3

Z= 248/3

Теперь нам необходимо узнать какие значения могут принимать коэффициенты целевой функции. Для этого нужно решить две системы уравнений, первое – состоящее из целевой функции и 2-го ограничения, второе – из целевой функции и3-го ограничения.

Причём коэффициенты целевой функции мы поочерёдно заменяем переменными С? и С?. Второй неизвестной будет выступать величина Z.

С?X? +5X?=Z

2Х?+X?=24

Разделим первое уравнение на 5, получим:

С?/5X? +X?=Z/5

2Х?+X?=24

Следовательно : С?/5=2 , С?=10 и Z/5=24 , Z=120.

6X? + С?X?=Z

2Х?+X?=24

Умножим второе уравнение на 3, получим:

6X? + С?X?=Z

6Х?+3X?=72

С?=3 , Z=72 .

С?X? +5X?=Z

X?+2X?=20

Первое уравнение умножим на 2 , а второе на 5:

2С?X? +10X?=2Z

5X?+10X?=100

2С?=5 , С?=5/2 ; 2Z=100 , Z=50.

6X? + С?X?=Z

Х?+2X?=20

Второе уравнение умножим на 6:

6X? + С?X?=Z

6Х?+12X?=120

С?=12 , Z=120.

В итоге имеем:

- для С? 2,5?С??10 , 50?Z?120.

- для С? 3?С??12 , 72?Z?120.

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

Лабораторная работа № 6.

«Симплексный метод решения задач линейного программирования».

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

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

1. Определить каким способом решается предложенная преподавателем задача.

2. Выполнить решение задачи в виде таблиц.

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

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

Первый - симплексный метод с естественным базисом, второй – с искусственным.

Первым методом решаются задачи с ограничениями вида ?. Следует отметить также, что ограничения типа ? могут быть приведены к типу ? умножением на (–1) всего уравнения, но также важно знать, что правые части ограничений всегда должны быть неотрицательны.

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

Рассмотрим два примера – отдельно для каждого случая.

Задача 1.

Найти максимальное значение целевой функции Z= -X?+X?+3Х?, при ограничениях:

2X?-X?+X??1; 4X?-2X?+X? ?-2; 3X?+X ??5.

Умножив на (-1) целевую функцию и 2-ое ограничение, мы сведём решение задачи к решению на минимум, и правая часть второго ограничения станет положительной. Получаем:

F= X?-X?-3Х?? min

2X?-X?+X??1

-4X?+2X?-X??2

3X?+X ??5.

Для того чтобы перейти от неравенств к равенствам необходимо ввести дополнительные переменные – базисные. В ограничениях вида ? они будут естественными, в других случаях они будут искусственными.

2X?-X?+X?+X?=1

-4X?+2X?-X?+X?=2

3X?+X ?+X?=5

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

F= X?-X?-3Х?+0 X?+0 X?+0 X?? min

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

X?=X?=X?=0 ,

X?=1 , X?=2 , X?=5.

№ п./п.	Базис	оценка	Св. член	1 X1	-1 X2	-3 X3	0 X4	0 X5	0 X6
1	X4	0	1	2	-1	1	1	0	0
2	X5	0	2	-4	2	-1	0	1	0
3	X6	0	5	3	0	1	0	0	1
M+1			0	-1	1	3	0	0	0

По индексной строке мы судим об оптимальности получившегося решения. Для задач на минимум показатель оптимального решения – отсутствие положительных значений. Как правило, первое решение далеко не оптимальное, что мы и имеем в данном случае. Для дальнейшего решения задачи необходимо найти разрешающий элемент. Чтобы его найти в индексной строке выбираем максимальное положительное число – в данном случае 3. Мы нашли разрешающий столбец. Теперь в этом столбце находим разрешающий элемент, как минимальное отношение величины из графы «свободный член», к величине из данного столбца, исключая отрицательные значения: Bi/xi?min, xi>0. Разрешающим элементом будет число 1. Ту переменную, которая находится в базисе напротив разрешающего элемента мы выводим из базиса, на её место вводится переменная из разрешающего столбца. Х4 меняем на Х3. Оценка новой базисной переменной находится в этом же разрешающем столбце.

Следующую симплексную таблицу составляем по следующим правилам:

1. Вместо разрешающего элемента пишем число 1.

2. Все значения разрешающего столбца равны 0.

3. Все элементы разрешающей строки делим на разрешающий элемент.

4. Все остальные значения рассчитываем следующим образом. Ячейка разрешающего элемента и ячейка искомого значения образуют собой сторону или диагональ прямоугольника. Находим произведение разрешающего элемента и диагонального ему элемента – по главной диагонали, и произведение двух других элементов – по побочной диагонали. Теперь находим разность между получившимися значениями и делим её на разрешающий элемент.

№ п./п.	Базис	оценка	Св. член	1 X1	-1 X2	-3 X3	0 X4	0 X5	0 X6
1	X3	-3	1	2	-1	1	1	0	0
2	X5	0	3	-2	1	0	1	1	0
3	X6	0	4	1	-1	0	-1	0	1
M+1			-3	-7	4	0	-3	0	0

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

№ п./п.	Базис	оценка	Св. член	1 X1	-1 X2	-3 X3	0 X4	0 X5	0 X6
1	X3	-3	-4	0	0	1	2	1	0
2	X2	-1	3	-2	1	0	1	1	0
3	X6	0	1	3	0	0	-2	-1	1
M+1			-15	1	0	0	-7	-4	-1/3

В индексной строке имеется одно положительное значение, продолжаем наше решение:

№ п./п.	Базис	оценка	Св. член	1 X1	-1 X2	-3 X3	0 X4	0 X5	0 X6
1	X3	-3	-4	0	0	1	2	1	0
2	X2	-1	3 2/3	0	1	0	2 1/3	1 2/3	2/3
3	X1	1	1/3	3	0	0	-2/3	-1/3	1/3
M+1			-15 1/3	0	-1/3	0	-6 2/3	-3 2/3	-1/3

Наконец мы получаем конечное решение – в индексной строке нет положительных оценок. Переменные, которые находятся в базисе получили значения X1=1/3 , Х2=3 2/3 , Х3=-3 , F=-15 1/3 , все остальные переменные равны нулю.

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

Задача 2 .

Найти максимальное значение целевой функции Z=-5X?-3X?-4X?+X? , при ограничениях Х?+3Х?+2Х?+2Х?=3 , 2Х?+2Х?+Х?+?=3 .

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

Х?+3Х?+2Х?+2Х?+X?=3

2Х?+2Х?+Х?+Х?+X?=3 .

Z= -5X?-3X?-4Х?+X?+0 X?+0 X?? max

Умножив на (-1) целевую функцию сводим решение задачи к решению на минимум. Нулевые коэффициенты при искусственных переменных изменятся на некоторые большие числа М.

Z= 5X?+3X?+4Х?-X?+М X?+М X?? min

Получаем первое возможное решение:

X?=X?=Х?=X?=0,

X?=3, X?=3.

Составляем симплексную таблицу:

№ п./п.	Базис	Оценка	Св. член	5 Х1	3 Х2	4 Х3	-1 Х4	М Х5	М Х6
1	Х5	М	3	1	3	2	2	1	0
2	Х6	М	3	2	2	1	1	0	1
М+1 М+2			0 6	-5 3	-3 5	-4 3	1 3	0 0	0 0

В методе решения с искусственным базисом в таблице заполняется две индексные строки. Они заполняются по следующей формуле:

n,m

Zj – Cj = ? Ai,j Cij– Ci

i,j=1

Проще говоря находим сумму произведений столбца переменной и столбца оценки, коэффициент при М записываем в строку М+2 , а свободный член в М+1 строку. В строке М+2 находим максимальное положительное число и в этом столбце – разрешающий элемент. Дальнейший ход решения аналогичен методу с естественным базисом. Когда все оценки в строке М+2 перестанут быть положительными, в следующей таблице начинаем работать со строкой М+1, так же добиваемся отсутствия положительных оценок.

№ п./п.	Базис	Оценка	Св. член	5 Х1	3 Х2	4 Х3	-1 Х4	М Х5	М Х6
1	Х2	3	1	1/3	1	2/3	2/3	1/3	0
2	Х6	М	1	4/3	0	-1/3	-1/3	-2/3	1
М+1 М+2			3 1	-4 4/3	0 0	-2 -1/3	3 -1/3	1 -5/3	0 0

№ п./п.	Базис	Оценка	Св. член	5 Х1	3 Х2	4 Х3	-1 Х4
1	Х2	3	3/4	0	1	3/4	3/4
2	Х1	5	3/4	1	0	-1/4	-1/4
М+1 М+2			6 1	0 0	0 0	-3 0	2 0

Искусственные переменные вышли из базиса, и в дальнейшем их можно не рассматривать.

№ п./п.	Базис	Оценка	Св. член	5 Х1	3 Х2	4 Х3	-1 Х4
1	Х4	-1	1	0	4/3	1	1
2	Х1	5	1	1	1/3	0	0
М+1			4	0	-8/3	-5	0

Получили оптимальное решение:

X1= 1, X4=1 , Z=4.

Лабораторная работа № 7.

«Составление и решение двойственных задач».

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

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

1. К имеющейся задаче линейного программирования составить двойственную задачу.

2. Проверить правильность составления двойственной задачи.

3. Получить решение двойственной задачи и сравнить его с решением прямой.

Каждой задаче линейного программирования соответствует двойственная задача. Для получения двойственной задачи нужно: 1) Каждому ограничению прямой задачи поставить в соответствие оценку ресурса; 2) Транспонировать матрицу коэффициентов ограничений; 3) Расставить знаки ограничений. Для симметричных задач (все ограничения которой представлены неравенствами одного вида), знаки ограничений меняем на противоположные. Для несимметричных задач (ограничения которых содержат знаки равенства) вводим дополнительные искусственные переменные, все ограничения приводим к виду равенств. Знаки ограничений расставляем в соответствии с таблицей:

Прямая задача	Двойственная задача
Целевая функция	Целевая функция	Знак ограничения	Переменные
Max	Min	?	Не огранич.
Min	Max	?	Не огранич.

Рассмотрим на примере переход от прямой задачи к двойственной.

Z= -2X?+5X?+X??min

7X?+2X?+11Х? ?13

5X?+6X?-3X?=25

3X?+8X?+2X??16

Все неравенства приводим к равенствам:

7X?+2X?+11Х?+Х?=13 Y?

5X?+6X?-3X?=25 Y?

3X?+8X?+2X?+Х?=16 Y?

Коэффициентами новой целевой функции будут правые части ограничений, а правыми частями ограничений – коэффициенты целевой функции.

F=13Y?+25Y?+16Y??max

7Y+5X?+3Х??-2

2Y?+6Y?+8Y??5

11Y?-3Y?+2Y??1

Учитывая введённые нами искусственные переменные, вводим два дополнительных ограничения:

Y??0

-Y??0

Учитывая, то что правые части ограничений должны быть положительны, умножаем первое ограничение на (-1):

F=13Y?+25Y?+16Y??max

-7Y-5X?-3Х??2

2Y?+6Y?+8Y??5

11Y?-3Y?+2Y??1

Y??0

-Y??0

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

Отметим свойства двойственной задачи:

1. Теоретически в оптимальных решениях целевая функция прямой задачи равна целевой функции двойственной.

2. Если прямая задача имеет n переменных и m ограничений, то обратная задача - m переменных и n ограничений.

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

4. Двойственная задача к двойственной – прямая.

5. Прямая и двойственная задача могут выступать в качестве прямой.

6. Переменные двойственной задачи равны оценкам переменных прямой задачи, и наоборот.

7. Столбцы коэффициентов прямой задачи – строки коэффициентов двойственной.

8. Правые части ограничений прямой задачи – коэффициенты целевой функции двойственной задачи.

9. Коэффициенты целевой функции прямой задачи – правые части ограничений двойственной задачи.

10. Если прямая задача не имеет решения, то и двойственная тоже не имеет решения.

Сравнив решения прямой и двойственной задачи, делаем вывод о правильности выполнения всех действий.

Решение прямой задачи:

Z= 15,4375; X?=0,875(-1,156); X?=3,437(1,2187) X?=0(0).

В скобках указаны оценки переменных.

Решение двойственной задачи:

F=15,4375; Y?= -1,156(0,875); Y?=3,437(1,2187); Y?=0(0).

Лабораторная работа № 8.

«Решение транспортной задачи».

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

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

1. Решить предложенную преподавателем транспортную задачу одним из существующих методов.

2. Проверить оптимальность получившегося решения с помощью программы линейного программирования.

3. Получить представление о решении транспортных задач с дополнительными ограничениями.

Транспортная задача является частным случаем общей распределительной задачи линейного программирования. Её смысл в оптимальном распределении производимых поставщиками товаров между потребителями. Её составление невозможно без ряда допущений: рассматривается перевозка однотипного груза, одинаковым транспортом одинаковой грузоподъёмности. Весь груз от поставщиков должен быть доставлен потребителям. Целевая функция транспортной задачи может быть на минимум стоимости перевозок или на минимум затраченного на перевозку времени.

Особенности решения задачи происходят из того, что в ней используется двумерный массив индексов переменных. Программа «ПЛП-88» имеет специальную подпрограмму для решения транспортных задач. Она находится в каталоге “Tran” , файл – Potenc1.exe .

Задача решаема только в том случае, если выполняется условие равенства суммы произведённых к перевозке товаров и суммы потребностей потребителей:

m n

? ai = ? bj

i=1 j=1

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

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

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

Задача.

Число поставщиков равно трём, a?=7, a?=6, a?=8. Число потребителей равно четырём, b?=5, b?=6, b?=6, b?=5. Таблица стоимости перевозок выглядит следующим образом.

21 25 26 22

С= 27 33 32 31

39 40 41 35

Проверим выполнение условие равенства количества товаров у поставщиков и объёма товаров необходимого потребителям. ? a=21, ? b=22. Так как ? ai ? ? bj задача открыта. Вводим дополнительного поставщика a?=1. В таблицу стоимости добавляем четвёртую строку с нулевыми величинами:

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 единицу товара записываем четвёртому потребителю. Все товары успешно распределились.

21 25 26 22	b?=5	b?=6	b?=6	b?=5
a?=7 31 27 33 32	5	2
a?=6 3 4 4 39 0 1 5		4	2
a?=8 0 0 0 0			4	4
a?=1				1

Подсчитаем, чему будет равна целевая функция:

Z=5*21+2*25+4*33+2*32+4*41+4*35=655

Как видно, искусственно введённая одна единица товара не играет роли при подсчёте целевой функции.

Второй способ решения – метод минимальной стоимости.

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

21 25 26 22	b?=5	b?=6	b?=6	b?=5
a?=7 31 27 33 32	5		2
a?=6 3 4 4 39 0 1 5			1	5
a?=8 0 0 0 0		6	2
a?=1			1

Рассчитываем целевую функцию в этом случае:

Z=5*21+2*26+1*32+5*31+6*40+2*41=666

Таблица, заполненная по столбцам:

21 25 26 22	b?=5	b?=6	b?=6	b?=5
a?=7 33 32 31 27	5	2
a?=6 3 4 4 39 0 1 5			6
a?=8 0 0 0 0		3		5
a?=1		1

Z=5*21+2*25+6*32+3*40+5*35=642

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

Третий способ – двойного предпочтения.

Максимально заполняем в первую очередь ячейки с минимальными тарифами.

21 25 26 22	b?=5	b?=6	b?=6	b?=5
a?=7 33 32 31 27	5	2
a?=6 3 4 4 39 0 1 5			6
a?=8 0 0 0 0		3		5
a?=1		1

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

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

Потенциал всех заполненных клеток равен нулю. Wij=0 Потенциал не заполненных клеток может быть положительным или отрицательным и рассчитывается по формуле: Wij=сij-(ui+vj), где ui - потенциал строки, vj- потенциал столбца, а cij - оценка перевозки. Система потенциалов может быть рассчитана только для невырожденного плана, т.е. если выполняется условие: число перевозок < n+m-1 , где n и m – ограничения по поставщикам и по потребителям.

Изначально задаём потенциал строки или столбца равным какому-либо числу  (удобно использовать 0). Далее рассчитываем остальные потенциалы. При решении задачи на минимум – оптимальное решение при отсутствии отрицательных характеристик.

Рассчитаем потенциалы клеток нашей таблицы.

21 25 26 22	b?=5	b?=6	b?=6	b?=5
a?=7 27 33 32 31	5	2
a?=6 3 4 4 39 0 1 5			6
a?=8 0 0 0 0		3		5
a?=1		1

V?=21, V?=25, V?=32, V?=20; U?=0, U?=0, U?=15, U?=25.

W??=0 , W??=0 , W??=-6, W??=2;

W??=6 , W??=8 , W??= 0 , W??=11;

W??=13, W??=0, W??=-6, W??=0;

W??=-46,W??=0, W??=-57,W??=-45.

Видим, что решение не является оптимальным. Необходимо дальнейшее улучшение решения.

Данная задача, решённая в программе «ПЛП-88» получила такое решение:

Z=1*21+4*27+6*25+2*32+3*41+5*35=641.

21 25 26 22	b?=5	b?=6	b?=6	b?=5
a?=7 27 33 32 31	1	6
a?=6 3 4 4 39 0 1 5	4		2
a?=8 0 0 0 0			3	5
a?=1			1

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