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