- •Киевский университет имени Тараса Шевченко
- •Общие рекомендации к использованию программного обеспечения
- •Элементарные преобразования матриц. Метод гаусса
- •Задача линейного программирования. Симплекс-метод Постановка задачи линейного программирования в стандартной форме (сзлп).
- •Задача линейного программирования. Модифицирован симплекс-метод.
- •Задача линейного программирования. Двойственный симплекс-метод
- •Транспортная задача. Метод потенциалов
- •Транспортная задача с ограниченными пропускными
- •Способностями. Метод потенциалов
- •Постановка транспортной задачи с ограниченными
- •Пропускными способностями (тзо).
- •Задача о кратчайшем пути на сети. Метод минти
- •Задача о максимальном потоке на сети. Метод форда-фалкерсона
- •Задача целочисленного линейного программирования. Метод гомори-1
- •Задача частично целочисленного линейного программирования. Метод гомори-2 Постановка частично целочисленной задачи линейного программирования (чцзлп).
- •Задача целочисленного линейного програмування. Метод гомори-3
- •Задача частично дискретного линейного программирования. Метод дальтона-ллевелина Постановка частично дискретной задачи линейного программирования (чдзлп).
- •Задача целочисленного линейного программирования. Метод ветвей и границ.
- •Лабораторная работа 14. Задача о назначении. Венгерский метод
- •Лабораторная работа 15. Задача о назначении. Метод мака Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4).
- •6. Если каждый столбец матрицы расходов имеет элемент с отметкой *, тогда задача об оптимальных назначениях решена. Иначе переходим к следующему пункту.
- •Матричные игры. Связь с задачей линейного программирования. Метод брауна-робiнсон
- •Лабораторная работа 17. Методы одномерной оптимiзации
- •Лабораторная работа 18. Задача выпуклого квадратичного программирования. Квадратичный симплекс-метод
- •Задача безусловной оптимизации. Метод самого быстрого спуску
- •Лiтература
Задача линейного программирования. Модифицирован симплекс-метод.
Изложение модифицированного симплекс-метода.
Модифицированный симплекс-метод (МСМ) непосредственно применяется к решению КЗЛП и осуществляет целенаправленное перебирание ДБР, к множеству которых принадлежит оптимальное решение, если он существует; или определяет, что ЗЛП не имеет оптимального решения.
В МСМ в отличие от СМ симплекс-превращение применяются только к базисной части матрицы условий А.
Признак оптимума и условия отсутствия оптимального решения ЗЛП для МСМ и СМ одинаковые.
Алгоритм модифицированного симплекс-метода.
На s-у шаге МСМ выполняются такие действия:
1. Вычисляются относительные оценки (симплекс - разницы)
j[s]= cj – (u[s], Aj)
где u[s]=cб[s]Воб[s] — вектор симплекс - множителей, Воб[s] — матрица, обратная к базисной, cб[s] — базисная часть вектора c. Если j[s]0 для всех j=1...,n, то конец: текущее базисное решение оптимальное. Если существует j такое, что j[s]<0, то перейти к пункту 2.
2. Выбирается k за формулой
k=argminj[s].
j: j[s]<0
Вычисляются векторы Ak[s]= Воб[s] Ak и A0[s]= Воб[s] A0.
Если Ak[s]0, то конец: целевая функция неограниченна снизу на допустимом множестве. Если существуют и такие, что aik[s]>0, то перейти к пункту 3.
3. Вычисляются отношения и[s]=ai0[s]/aik[s] для всех aik[s]>0 но выбирается l так, что
l=argminи[s].
и: aik[s]>0
Вектор Akпринадлежит ввести к базису, а вектор, что является базисным в lму непрямом ограничении, должен быть выведенным из базиса.
4. Матрица Воб[s+1] вычисляется за матрицей Воб[s]с помощью обычных симплекс - превращений с использованием ведущего элементаalk[s].Подобным образом может быть определен и векторA0[s+1]. Для КЗЛПВоб[0] — единичная матрица размерности mm.
Программное обеспечение.
Обучающий модуль, с помощью которого ЗЛП решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.
Задание.
Решить модифицированным симплекс-методом задачи линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи.
Во всех задачах, которые предлагаются ниже, все переменные неотъемлемые.
1) |
x1 – x2 + 3x4 + x5 min |
2) |
3 x1 + x2 + x4 + x5 min |
|
x1 + 2x2 + 3x3 + 3x4 + x5 = 15 |
|
2 x1 – x2 + x4 – x5 = 9 |
|
2 x1 – x2 – 3x3 + x4 – x5 = 4 |
|
4 x1 – x2 – x3 – x5 = 4 |
|
2 x1 – 2x2 – x3 + 2x5 = 8; |
|
x1 – x2 – x3 – x5 = 6; |
3) |
x1 – 2x2 + 2x3 + x4 + 2x5 max |
4) |
x1 + 2x2 + x3 – x4 min |
|
–x1 + x2 – 2x3 + 3x4 + x5 = 2 |
|
–x1 + 5x2 + x3 + x4 + x5 = 10 |
|
–x1 + 2x2 – x3 + 2x4 = 3 |
|
2x1 – x2 + x3 – 3x4 = 6 |
|
2x1 + 3x2 + x4 – x5 = 6; |
|
10x2 + x3 + 2x4 + 3x5 = 25; |
5) |
x1 – x2 + x3 + x4 – x5 min |
6)) |
x1 – x2 + x3 + 2x4 max |
|
x1 + x4 + 6 x5 = 9 |
|
x1 + x2 + x3 + 2x4 + 3x5 = 7 |
|
3 x1 + x2 – 4 x3 + 2 x5 = 2 |
|
x1 + 2x2 + 2x3 + 3x4 + 2x5 = 12 |
|
x1 + 2 x2 + 2 x5 = 6; |
|
2x1 + 3x2 + 4x3 + 4x4 – x5 = 22; |
7) |
x1 + 2 x2 – x3 – x4 min |
8) |
x1 – x2 + x3 + x4 + x5 – x6 min |
|
x1 + x2 + 2 x3 – x4 = 2 |
|
4x1 + x2 – 4x3 + x4 + 8x6 = 15 |
|
x1 + 2 x2 – 3 x3 + x4 = 6 |
|
4x1 + x2 – 2x3 + x5 + 4x6 = 8 |
|
x1 + x2 + x3 + x4 = 7; |
|
5x1 + x2 – 2x3 + x4 + x5 + 10x6 = 21; |
9) |
x1 + 2x2 + 3x3 + x4 + x5 max |
10)) |
x1 – x2 + x3 – 3x4 + 2x5 min |
|
x1 + x2 + 4x3 – x4 + x5 = 1 |
|
x1 +2x2 – x3 + 2x4 + x5 8 |
|
x1 + x2 – 2x3 + x4 + x5 = 1 |
|
–x1 – x2 + x3 – 3x4 – 2x5 = 10 |
|
–x1 + x2 – 6x3 + x4 + x5 = 1; |
|
2x1 – x2 + 3x3 – x4 + 2x5 4. |
Ответы:
1) x* = (5.11; 3.67; 0; 0; 2.56), L(x*)= 4.
2) Решения нет ( D = ).
3) Решения нет (целевая функция неограниченна сверху на допустимом множестве).
4) x* = (1; 0; 4; 0; 7), L(x*)= 5.
5) x* = (0; 1.5; 0.63; 0; 1.5), L(x*)= 2.38.
6) x* = (1; 0; 4; 1; 0), L(x*)= 7.
7) x* = (4.13; 0; 1.25; 2.62), L(x*)= 1.25.
8) x* = (0; 1; 0.83; 0; 0; 2.17), L(x*)= 2.33.
9) x* = (0; 1; 0; 0; 0), L(x*)= 2.
10) Решения нет ( D = ).
Лабораторная работа 4.