Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






ЛИНЕЙНОЕ И НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.

ЛИНЕЙНОЕ И НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.

ЭЛЕМЕНТЫ ТЕОРИИ ИГР.

СЕТЕВОЕ ПЛАНИРОВАНИЕ

 

 

Лабораторный практикум

 

Самара

Самарский государственный технический университет

Печатается по решению редакционно-издательского совета СамГТУ

 

УДК 51

 

 

Линейное и нелинейное программирование. Динамическое программирование. Элементы теории игр. Сетевое планирование: лабораторный практикум / Сост. М.А. Евдокимов, Л.Н. Смирнова, Т.А. Бенгина, Т.Н. Кочетова, О.В. Филиппенко. – Самара: Самар. гос. техн. ун-т, 2014. – 99 с.: ил.

 

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

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

Работа предназначена для студентов и преподавателей университета.

 

Р е ц е н з е н т

 

Ó М.А. Евдокимов, Л.Н. Смирнова,

Т.А. Бенгина, Т.Н. Кочетова,

О.В. Филиппенко, 2014

Ó Самарский государственный

технический университет, 2014


 

ВВЕДЕНИЕ

 

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

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

Сейчас существует множество прикладных программ используемых для решения математических задач (MathCAD, Matlab, Mathematica, Maple и др.), однако при выборе программного обеспечения используемого на лабораторных занятиях мы решили остановиться на табличных процессорах Microsoft Excel и OpenOffice.org Calc. Основными предпосылками для этого послужили: доступность данного программного продукта (почти на любом ПК сегодня установлена операционная система Windows c её приложениями) и знакомый для студента интерфейс (что облегчает работу, т.к. не приходится затрачивать время на изучение основ работы с самим программным продуктом).

Каждая лабораторная работа содержит краткие теоретические сведения по определенной теме дисциплины «Исследование операций», пояснения по использованию программного обеспечения (табличного редактора Microsoft Excel и OpenOffice.org Calc) для решения задач данной темы, задания для самостоятельного выполнения и контрольные вопросы.

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

 

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

Постановка задачи линейного программирования (ЗЛП) и алгоритм ее решения графическим методом. Решение задач ЛП в редакторе Microsoft Excel и OpenOffice.org Calc с помощью

Встроенной функции Поиск решения

Цель лабораторного занятия:

Приобретение навыков решения задач линейного программирования (ЗЛП) графическим методом, а также в табличных редакторах Microsoft Excel и OpenOffice.org Calc с помощью встроенной функции Поиск решения.

Задачи лабораторного занятия:

1. Построение математической модели задачи.

2. Построение области допустимых решений (ОДР), градиента целевой функции, линий уровня для целевой функции.

3. Нахождение максимума (минимума) целевой функции графическим методом.

4. Ввод данных на листе Excel.

5. Знакомство с командой Поиск решения.

6. Нахождение максимума (минимума) целевой функции с помощью команды Поиск решения.

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

8. Оформление отчета.

Содержание

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

2. Решение ЗЛП графическим методом в Microsoft Excel и OpenOffice.org Calc.

3. Решение ЗЛП в Microsoft Excel и OpenOffice.org Calc с помощью встроенной функции Поиск решения.

4. Задание.

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

Краткие теоретические сведения

Графический метод решения задач линейного программирования применяется для задач с двумя переменными. Задача линейного программирования с двумя переменными в стандартной форме имеет вид:

(1)

(2)

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

Перпендикулярно вектору проводится линия уровня функции . Линия уровня перемещается по направлению вектора для задачи максимизации и в направлении противоположном для задачи минимизации.

Перемещение линии уровня производится до тех пор, пока у нее окажется только одна общая точка с ОДР. Эта точка определяет единственное решение ЗЛП.

Если окажется, что линия уровня совпадает с одной из сторон ОДР, то ЗЛП будет иметь бесконечное множество решений.

Если ОДР представляет неограниченную область, то целевая функция может быть неограниченна.

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

Для составления математической модели ЗЛП необходимо выполнить следующие этапы:

1. Обозначить переменные.

2. Составить целевую функцию в соответствии с целью задачи.

3. Записать систему ограничений с учетом имеющихся в условии задачи показателей.

Алгоритм решения ЗЛП графическим методом:

1. Построить ОДР.

2. Построить вектор .

3. Провести линию уровня функции .

4. Перемещать линию уровня до пересечения с точкой оптимума, если таковая имеется в данной задачи.

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

 

Задание

1. Решить задачи 2 и 3 графическим методом.

2. Решить задачи 2 и 3 в редакторе Microsoft Excel или OpenOffice.org Calc используя встроенную функцию Поиск решения.

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

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

5. Оформить отчет.

Задача 2.[1] Фармацевтическая фирма Ozark ежедневно производит не менее 800 фунтов некой пищевой добавки – смеси кукурузной и соевой муки, состав которой представлен в таблице 2.

Таблица 2

Мука Белок (в фунтах на фунт муки) Клетчатка (в фунтах на фунт муки) Стоимость (в долл. за фунт)
Кукурузная 0,09 0,02 0,3
Соевая 0,60 0,06 0,9

 

Диетологи требуют, чтобы в пищевой добавке было не менее 30% белка и не более 5% клетчатки. Фирма Ozark хочет определить рецептуру смеси минимальной стоимости с учетом требований диетологов.

 

Задача 3. Предприятие, специализирующееся на производстве трикотажного полотна двух видов, использует для своего производства четыре вида сырья (шерстяную, хлопковую, вискозную, и акриловую нити), запасы которого на планируемый период составляют соответственно 80, 80, 260 и 410 бобин. В приведенной ниже таблице даны технологические коэффициенты, т.е. расход каждого вида сырья на производство одного метра каждого вида трикотажа.

Таблица 3

Виды сырья Технологические коэффициенты Запасы сырья
I вид трикотажного полотна. II вид трикотажного полотна
Шерсть 80 б.
Хлопок 80 б
Вискоза 260 б.
Акрил 410 б.

 

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

 

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

1. Что означает составить математическую модель ЗЛП?

2. Из каких этапов состоит графический метод решения ЗЛП?

3. Какова геометрическая интерпретация решения системы линейных неравенств с двумя переменными?

4. Как определяется направление наискорейшего возрастания целевой функции?

5. Какое решение называется оптимальным решением ЗЛП?

6. В каком случае ЗЛП имеет множество решений?

7. При каких условиях ЗЛП может быть неразрешима?

8. Как установить модуль Поиск решения?

9. Для чего предназначена кнопка Предположить в окне Поиск решения?

10. Какие типы отчетов можно получить при решении ЗЛП с помощью встроенной функции Поиск решения?

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

Симплексный метод. Задача определения оптимального плана выпуска продукции. Использование встроенных функций редакторов Microsoft Excel и OpenOffice.org Calc для построения математической модели и решения ЗЛП.

Цель лабораторного занятия:

Приобретение навыков решения ЗЛП симплекс-методом. Освоение приемов записи математической модели ЗЛП с большим количеством неизвестных в табличных редакторах Microsoft Excel и OpenOffice.org Calc с помощью встроенной функций СУММПРОИЗВ. Приобретение навыков решения ЗЛП с большим количеством неизвестных с помощью функции Поиск решения.

Задачи лабораторного занятия:

1. Освоение симплекс-метода решения ЗЛП.

2. Построение математической модели задачи в табличных редакторах Microsoft Excel и OpenOffice.org Calc с помощью встроенной функций СУММПРОИЗВ.

3. Нахождение максимума (минимума) целевой функции с помощью команды Поиск решения.

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

5. Оформление отчета.

Содержание

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

2. Решение ЗЛП симплекс методом без использования табличных редакторов.

3. Решение ЗЛП на определение оптимального плана выпуска продукции в Microsoft Excel и OpenOffice.org Calc с помощью встроенной функции Поиск решения.

4. Задание.

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

Краткие теоретические сведения

В основу симплекс-метода (симплексного метода) легла идея последовательного улучшения решения.

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

Реализация симплекс-метода предусматривает содержание трех основных элементов:

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

2. Правила перехода к лучшему (точнее, не худшему) решению;

3. Критерий проверки оптимальности найденного решения.

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

Практические расчеты при решении прикладных задач симплексным методом выполняются в настоящее время с помощью компьютерных программ, таких как табличный процессор Microsoft Excel, пакеты прикладных программ MathCAD, Math Lab и др. Однако, если расчеты осуществляются вручную, удобно использовать так называемые симплексные таблицы.

I шаг.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

В качестве разрешающего выберем столбец, соответствующий переменной , т.к. ей соответствует наибольший по модулю отрицательный коэффициент (-3).

3. Определение новой свободной переменной.

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

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

4. Пересчет симплекс-таблицы.

В столбце базисных переменных (БП) записываем новый базис: вместо базисной переменной - переменную .

Каждый элемент разрешающей строки (которая в новой симплекс таблице будет уже соответствовать переменной ) делим на разрешающий элемент ( ).

На месте разрешающего элемента получаем 1. В столбцах, соответствующих базисным переменным ( , , , ,) проставляем нули и единицы: 1 – против «своей» базисной переменной; 0 – против «чужой» базисной переменной; 0 – в последней индексной строке для всех базисных переменных.

Все остальные элементы новой симплекс-таблицы (включая элементы индексной строки) находим по правилу «прямоугольника» (см. п. 5.4.4. алгоритма).

После преобразований получаем новую таблицу (таблица 6).

Таблица 6

БП СЧ Оценочное отношение
 
-3
-3 42,5
-2  

Базисное решение: .

II шаг.

1. Проверка критерия оптимальности.

Полученное на II шаге базисное решение (опорный план) не является оптимальным, т.к. в индексной строке есть отрицательный коэффициент (-2).

2. Определение новой базисной переменной.

В качестве разрешающего выберем столбец, соответствующий переменной , т.к. ей соответствует отрицательный коэффициент (-2).

3. Определение новой свободной переменной.

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

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

4. Пересчет симплекс-таблицы.

В столбце базисных переменных (БП) записываем новый базис: вместо базисной переменной - переменную .

Каждый элемент разрешающей строки (которая в новой симплекс таблице будет уже соответствовать переменной ) делим на разрешающий элемент ( ).

На месте разрешающего элемента получаем 1. В столбцах, соответствующих базисным переменным ( , , , ,) проставляем нули и единицы: 1 – против «своей» базисной переменной; 0 – против «чужой» базисной переменной; 0 – в последней индексной строке для всех базисных переменных.

Все остальные элементы новой симплекс-таблицы (включая элементы индексной строки) находим по правилу «прямоугольника» (см. п. 5.4.4. алгоритма).

После преобразований получаем новую таблицу (таблица 7).

 

Таблица 7

БП СЧ Оценочное отношение
-1
-3  
-4
-3  

 

Базисное решение: .

III шаг.

1. Проверка критерия оптимальности.

Полученное на III шаге базисное решение (опорный план) не является оптимальным, т.к. в индексной строке есть отрицательный коэффициент (-3).

2. Определение новой базисной переменной.

В качестве разрешающего выберем столбец, соответствующий переменной , т.к. ей соответствует отрицательный коэффициент (-3).

3. Определение новой свободной переменной.

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

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

4. Пересчет симплекс-таблицы.

В столбце базисных переменных (БП) записываем новый базис: вместо базисной переменной - переменную .

Каждый элемент разрешающей строки (которая в новой симплекс таблице будет уже соответствовать переменной ) делим на разрешающий элемент ( ).

На месте разрешающего элемента получаем 1. В столбцах, соответствующих базисным переменным ( , , , ,) проставляем нули и единицы: 1 – против «своей» базисной переменной; 0 – против «чужой» базисной переменной; 0 – в последней индексной строке для всех базисных переменных.

Все остальные элементы новой симплекс-таблицы (включая элементы индексной строки) находим по правилу «прямоугольника» (см. п. 5.4.4. алгоритма).

После преобразований получаем новую таблицу (таблица 8).

Таблица 8

БП СЧ Оценочное отношение
4/9 -1/9  
1/3 -1/3  
-1/3 1/3  
-4/9 1/9  
2/3 1/3  

Базисное решение: .

IV шаг.

1. Проверка критерия оптимальности.

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

Таким образом оптимальным будет решение: при котором Т.е. для получения максимальной прибыли от реализации трикотажного полотна в размере 310 у.е. предприятие должно выпустить за планируемый период соответственно 50 и 70 метров трикотажного полотна первого и второго вида.

 

Поиск решения

Задачи с небольшим числом неизвестных и ограничений могут быть решены симплексным методом вручную, задачи, содержащие большое количество неизвестных легко решаются в Microsoft Excel и OpenOffice.org Calc с помощью встроенной функции Поиск решения. При установке параметра Линейная модель решение здесь ищется так же с помощью симплекс-метода.

Замечание. Если флажок Линейная модель выключен, решение задач ведется методом Ньютона или градиентным методом.

Задача 4.Коммерческая организация имеет 9 видов ресурсов, запасы которых на планируемый период составляют соответственно: 1451,56; 1234,78; 1345,98; 1456,76; 1890,41; 1234,56; 1567,23; 1456,48 условных единиц. Имеющиеся ресурсы могут быть использованы для выпуска 4 видов продукции. В приведенной ниже таблице 9 даны технологические коэффициенты, т.е. расход каждого вида ресурса на производство единицы каждого вида продукции и прибыль от реализации единицы продукции каждого вида

Таблица 9

Ресурсы Технологические коэффициенты Запасы ресурса
1вид продукции 2вид продукции 3вид продукции 4вид продукции
5,23 6,09 6,56 4,51 1451,56
9,12 7,02 8,95 5,93 1234,78
8,14 7,49 6,51 7,12 1345,98
9,81 9,60 9,14 4,91 1456,76
2,43 4,28 8,25 8,15 1890,41
7,42 5,93 4,52 2,03 1234,56
7,23 9,13 8,62 5,82 1567,23
6,78 7,12 5,19 7,23 1456,48
6,35 5,14 7,24 4,45 1890,45
Прибыль от реализации 9,85 12,31 11,99 9,61  

 

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

Составим математическую модель задачи на листе Excel (рис. 12). Обозначим через x1, x2, x3, x4 количество единиц соответствующей продукции; с1, с2, с3, с4 - прибыль от реализации единицы соответствующего вида продукции. Целевая функция задается с помощью встроенной функции СУММПРОИЗВ(В4:Е4;В6:Е6). В OpenOffice.org Calc используется функция SUMPRODUCT(В4:Е4;В6:Е6). Ограничения также зададим с помощью функции СУММПРОИЗВ в столбце F, для этого в ячейке F10 записываем формулу СУММПРОИЗВ ($В4$:$Е4$;В10:Е10) (SUMPRODUCT($В4$:$Е4$;В10:Е10)) при этом используем абсолютную адресацию для массива В4:Е4, чтобы можно было распространить формулы на все ячейки столбца «Расход ресурса».

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

 

 

Р и с. 12.

 

Задание

1. Решить задачи 1 и 2 из Л.Р.№1 с помощью симплекс-таблиц.

2. Найти оптимальное решение задачи 4 с помощью встроенной функции Поиск решения в редакторе Microsoft Excel.

Индивидуальное задание

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

2. Составить математическую модель данной задачи, дав экономическую интерпретацию переменным, функции цели и системе ограничений.

3. Записать модель в стандартной и канонической формах.

4. Решить задачу симплекс-методом с помощью симплекс-таблиц.

5. Решить задачу с использованием встроенной функции Поиск решения в Microsoft Excel или OpenOffice.org Calc.Проанализировать полученный результат.

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

1. В чем заключается идея симплекс-метода?

2. В каком виде должна быть записана модель ЗЛП для решения симплекс-методом?

3. Как определить первоначальное допустимое базисное решение?

4. Из каких этапов состоит переход от одного базисного решения к другому?

5. Как определить разрешающий столбец в симплекс-преобразованиях?

6. Как определить разрешающую строку в симплекс-преобразованиях?

7. Что является критерием оптимальности решения ЗЛП в симплекс-методе?

8. Как определяется текущее значение целевой функции из таблицы?

9. По какому правилу вычисляются значения элементов новой симплекс-таблицы?

10. Какие параметры необходимо установить при решении задачи линейного программирования в Microsoft Excel, чтобы она была решена симплекс-методом?

11. Какая встроенная функция Microsoft Excel и OpenOffice.org Calc используется для записи математической модели ЗЛП с большим количеством неизвестных?

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

Содержание

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

2. Алгоритм составления двойственной задачи.

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

4. Задание.

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

Краткие теоретические сведения

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

Т.е. ЗЛП на максимум можно поставить в соответствие ЗЛП на минимум. Эти задачи называются симметричными или взаимно-двойственными.

Рассмотрим понятие двойственных задач на примере задачи 3 об использовании ресурсов (сырья) из Л.Р. №1:

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

Экономико-математическая модель задачи следующая: найти максимум целевой функции (функции прибыли):

при выполнении системы ограничений:

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

Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы (целевая функция Z) в количествах 80, 80, 260 и 410 у.е. по ценам были минимальны, т.е.

.

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

На изготовление 1м трикотажного полотна I вида расходуется 0 у.е. первого ресурса (шерсти), 1 у.е. второго ресурса (хлопка), 1 у.е. третьего ресурса (вискозы) и 4 у.е. четветого ресурса (акрила). Поэтому для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении 1м трикотажного полотна I вида по ценам , должны быть не менее цены 1м трикотажного полотна I вида 2 у.е., т.е.

Аналогично составим ограничение в виде неравенства по второму виду продукции (трикотажному полотну II вида):

.

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

Таблица 10

Исходная задача Двойственная задача
  при ограничениях:   при ограничениях:
Матрица коэффициентов при переменных в системе ограничений Матрица коэффициентов при переменных в системе ограничений  

 

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

Цены ресурсов так же называются «внутренними» (или оценками ресурсов), т.к. они задаются не извне, а определяются непосредственно в результате решения задачи.

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

Взаимно двойственные задачи обладают следующими свойствами:

1. В одной задаче определяется максимум целевой функции, в другой – минимум.

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

3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида , а в задаче минимизации – все неравенства вида .

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

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

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

Задание

1. Для задачи 5 найти решение прямой и двойственной задачи с помощью функции Поиск решения в Microsoft Excel или OpenOffice.org Calc.

2. Составить математическую модель двойственной ЗЛП для задач 1 и 2. Из решения прямой задачи 1 и 2 (Л.Р. №2) получить решение двойственной. Расчеты выполнить на листе Microsoft Excel или OpenOffice.org Calc используя функции МОБР() (MINVERSE()), МУМНОЖ() (MMULT()).

3. Составить двойственную задачу к следующей ЗЛП:

при ограничениях:

, , .

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

 

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

1. Перечислить свойства взаимно двойственных задач.

2. Сформулировать алгоритм составления математической модели двойственной задачи.

3. Как найти решение двойственной задачи, если исходная (прямая задача) уже решена симплекс-методом?

4. В каком виде должна быть записана модель ЗЛП для решения симплекс-методом?

5. С помощью каких функций двойственная задача может быть решена в табличных редакторах Microsoft Excel или OpenOffice.org Calc?

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

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

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

Цель лабораторного занятия:

Освоение приемов записи математической модели закрытой транс

Последнее изменение этой страницы: 2016-07-23

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...