Министерство общего и профессионального
ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
__________________________________
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ
КОЛОМЕНСКИЙ ИНСТИТУТ
|
|
"УТВЕРЖДЕНО" Учебно-методическим Советом КИ МГОУ Председатель Совета _____________________ А.М. Липатов "___"__________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-стороки симплекс-таблицы): 
.
На основе вышесказанного имеет место
следующее соотношение:
или
Значение целевой функции определяется по формуле:
Решение
двойственной задачи можно найти, зная
решение прямой задачи: 
.