- •Министерство общего и профессионального
- •1. Введение
- •2. Соотношения двойственности
- •3. Решение детерминированной задачи.
- •4. Решение злп с помощью соотношений двойственности
- •5. Задание для лабораторной работы
- •Литература
- •Типовой отчет по лабораторной работе "Решение задач линейного программирования"
- •Исходные данные
Министерство общего и профессионального
ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
__________________________________
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ
КОЛОМЕНСКИЙ ИНСТИТУТ
|
"УТВЕРЖДЕНО" Учебно-методическим Советом КИ МГОУ Председатель Совета _____________________ А.М. Липатов "___"__________1999 г. |
Трушков А.С.
ИНСТРУКЦИЯ
для выполнения лабораторной работы
по математическому программированию
РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ
г. Коломна
1999 г.
Содержание
1. |
Введение ......................... ................................................................................. |
2 |
2. |
Соотношения двойственности ………………………………………………... |
2 |
3. |
Решение детерминированной задачи ........…………………………………… |
4 |
4. |
Решение ЗЛП с помощью соотношений двойственности ............................. |
7 |
5. |
Задание для лабораторной работы .................................................................. |
13 |
6. |
Литература ........................................................................................................ |
14 |
|
Приложение ……………………………………………………………………. |
15 |
1. Введение
Лабораторная работа выполняется с помощью программы ²Решение и моделирование задач линейного программирования² /1/. Программа написана на алгоритмическом языке Visual Basic for Application (VBA) и оформлена в виде модуля табличного процессора Excel 97. Программа позволяет решать задачи линейного программирования (ЗЛП) для детерминированных исходных данных, а также проводить имитационное моделирование для линейных моделей при стохастических исходных данных для оценивания параметров распределения вероятностей переменных оптимального плана и значения целевой функции.
Целью лабораторной работы в курсе “Математического программирования” является освоение программы, а также реализация вычислительных процедур симплекс-метода с помощью встроенных функций табличного процессора Excel.
2. Соотношения двойственности
Задача линейного программирования в стандартной форме записывается в следующем виде /2/:
Здесь последние m переменных являются переменными начального базиса. Введем обозначения:
единичная
матрица
размера
m
Столбцы коэффициентов при переменных равны:
Тогда (А,I) - блочная матрица коэффициентов ограничений. ЗЛП в стандартной форме в векторно-матричной форме можно записать в следующем виде:
или
Двойственная задача в этих обозначениях формулируется следующим образом:
где - вектор-строка двойственных переменных.
На любой итерации любой элемент симплекс-таблицы можно определить, если известна обратная матрица базиса , с помощью следующих двух соотношений двойственности:
1) столбец левой части или правой части вычисляются как произведения матрицы на вектор-столбец или исходной таблицы:
Если обозначить - матрицу правой части симплекс-таблицы на текущей итерации, то:
;
2) элемент строки целевой функции (оценок плана) определяется как разность левой и правой части соответствующего ограничения двойственной задачи:
Вектор двойственных переменных на любой итерации определяется как произведение вектор-строки исходных коэффициентов целевой функции при базисных переменных прямой задачи на рассматриваемой итерации на матрицу : . Порядок элементов вектора соответствует порядку базисных элементов в столбце “БП”.
Введем вектор оценок плана (коэффициентов z-стороки симплекс-таблицы): . На основе вышесказанного имеет место следующее соотношение:
или
Значение целевой функции определяется по формуле:
Решение двойственной задачи можно найти, зная решение прямой задачи: .