Файл: zlp-mp.doc

21

Министерство общего и профессионального

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

__________________________________

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

КОЛОМЕНСКИЙ ИНСТИТУТ

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

или

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

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

---

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

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

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

max z = -x₁ + 2x₂ + x₃

2x₁ + 3x₂ - 5x₃  3

-x₁ + 9x₂ - x₃  5

4x₁ + 6x₂ + 3x₃  15

x_i  0

Для приведения задачи к стандартной форме вводим дополнительные переменные:

max z = -x₁ + 2x₂ + x₃

2x₁ + 3x₂ - 5x₃ - x₄ = 3

-x₁ + 9x₂ - x₃ - x₅ = 5

4x₁ + 6x₂ + 3x₃ + x₆ = 15

x_i  0

Матрица системы ограничений не содержит выделенной единичной матрицы:

.

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

.

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

---

.

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

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

max z = -x₁ + 2x₂ + x₃ - Mx₆ - Mx₇

2x₁ + 3x₂ - 5x₃ - x₄ + x₆ = 3

-x₁ + 9x₂ - x₃ - x₅ + x₇ = 5

4x₁ + 6x₂ + 3x₃ + x₈ = 15

x_i  0

Модель содержит 8 переменных, из них x₁, х₂, х₃ - исходные, х₄, х₅, х₈ - дополнительные, х₆ и х₇ - искусственные. Искусственные переменные вводятся в целевую функцию со штрафом М (в задаче максимизации искусственные переменные входят в целевую функцию со штрафом -М).

Исходные данные модели имеют вид:

= (-1; 2; 1; 0; 0; -М; -М; 0) - вектор коэффициентов целевой функции;

- матрица коэффициентов системы ограничений;

- вектор правых частей системы ограничений.

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

,

где содержит коэффициенты при исходных переменных, а - при искусственных. Для рассматриваемой модели: = (-1; 2; 1; 0; 0; 0 ; 0; 0), = (0; 0; 0; 0; 0; -1; -1; 0).

---