Линейное программирование

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

РОССИЙСКОЙ ФЕДЕРАЦИИ

РЯЗАНСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

КАФЕДРА АСУ

КОНТРОЛЬНАЯ РАБОТА

ПО МАТЕМАТИЧЕСКИМ ОСНОВАМ ПРИНЯТИЯ РЕШЕНИЙ

ТЕМА: «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ»

Руководитель:

преподаватель кафедры АСУ

Дондик Е.М.

Студент гр. 8030

Веденяпин И.А.

Рязань, 2011 г.

Содержание

1. Постановка задачи

2. Математическая модель

2.1 Управляемые параметры

2.2 Система ограничений

2.3 Постановка задачи

3. Графическое решение

3.1 Исследование чувствительности решения к изменению правых частей ограничений.

3.2 Исследование чувствительности решения к изменению коэффициентов матрицы

3.3 Исследование чувствительности решения к изменению коэффициентов целевой функции

3.4 Исследование возможности увеличения оптимального значения целевой функции

4. Решение задачи ЛП симплексным методом

5. Двойственность задач линейного программирования

1. Постановка задачи

В кафе подаются два вида салата

2. Математическая модель

2.1 Управляемые параметры

Х1 - количество порций за один день;

Х2 - количество порций за один день;

Х(Х1, Х2) - решение.

2.2 Система ограничений

1) -5x1+4x2<=20;

2) 2x1+3x2<=24;

3) 1x1-3x2<=3;

4) 1x1+0x2<=8;

5) 0x1+1x2<=6.

2.3 Постановка задачи

Найти Х, при котором достигается максимум целевой функции: Fmax=3X1+2X2.

3. Графическое решение

Оптимальное решение находится путем параллельного переноса целевой функции на графике.

симплексный линейный программирование

Функция максимальна в точке (8.0,2.7). Fmax(8.0,2.7)=29.33.

Нахождение оптимального решения лишь начальный этап решения задачи линейного программирования. Большой интерес представляет исследование возможности отклонения заданных параметров без изменения найденного оптимального решения. Среди анализируемых параметров можно выделить следующие:

1. Значения коэффициентов правых частей системы ограничений Bi;

2. Значения коэффициентов целевой функции Cj;

3. Значения коэффициентов матрицы системы Aij.

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

Основная цель анализа чувствительности в данном случае состоит в том, что для каждого коэффициента Bi (i=1,m) необходимо определить интервал (Bmin, Bmax), для всех значений которого система ограничений была бы совместна и её решение не изменялось.

Для исследования чувствительности решения задачи ЛП к изменению коэффициентов правых частей ограничений анализируется ОДР на возможность параллельного переноса прямой, соответствующей i-ому ограничению и не примыкающей к оптимальной вершине.

Точка D соответствует оптимальному решению. Границы ОДР, примыкающие к вершине D, то есть CD и DE, не могут быть перенесены без изменения координат D, а значит, и оптимального решения. Границу AB можно переместить параллельно самой себе в сторону начала координат или наоборот. Параллельный перенос AB означает изменение коэффициента bi уравнения этой прямой. Перемещать можно до тех пор, пока точки максимально не приблизятся друг к другу. В этом предельном случае прямая AB, соответствующая i-му ограничению, фактически «выйдет» за пределы ОДР, образованной оставшимися (m -1) ограничениями.

B1 = 20.00, B1max = 23.50, B1min = 9.75.

Аналогично находятся пределы изменения коэффициентов bi уравнения, определяющих прямые BC и EF.

B5нач = 6.00; B5max = 6.75; B5min = 5.25.

B3нач = 3.00; B3max = 7.75; B3min = 0.50.

Исследование чувствительности решения к изменению коэффициентов матрицы.

Анализ чувствительности решения к изменениям коэффициентов матрицы системы сводится к отыскиванию допустимых пределов изменения коэффициентов Aij (i = ; j = ) при сохранении оптимального найденного решения, то есть найти пределы поворота границ ОДР, не примыкающих к вершине D. Поворот прямой нужно выполнять относительно точек её пересечения с осями координат.

Относительно точки B (AB):

A11min = -462.48; A12max = 65.00; A11max = -0.006; A12min = 3.34.

Относительно точки А (AB):

A12 = 4.00; A11min = -229.16; A11max = -1.46.

Относительно точки B (BC):

A51min = -1.42, A52max = 1.19; A51max = 0.42, A52min = 0.94;

Относительно точки C (BC):

A51max = 0.49; A52min = 0.75; A51min = -0.36; A52max = 1.18;

Относительно точки E (EF):

A31min = 0.38; A32max = -0.01; A31max = 18.87; A32min = -88.79;

Относительно точки F (EF):

A31 = 1.00; A32max = -1.96; A32min = -57.29;

Исследование чувствительности решения к изменению коэффициентов целевой функции.

Анализ чувствительности полученного решения к изменению коэффициентов функционала предусматривает нахождение пределов изменений коэффициентов Cj при постоянстве оптимального решения. При графическом представлении решения задачи ЛП изменение коэффициентов в выражении целевой функции соответствует изменению ее наклона. Возможные пределы поворота целевой функции определяются наклоном границ ОДР, примыкающих к оптимальной вершине.

Исследование возможности увеличения оптимального значения целевой функции.

4. Решение задачи лп симплексным методом

Симплексный метод основан на идее перехода от одного базисного решения в вершине многоугольника допустимых решений к другому базисному решению, более близкому к оптимальному.

Выразим базисные переменные через свободные:

y1 = 20 +5x1 - 4x2;

y2 = 24 -2x1 - 3x2;

y3 = 3 - 1x1 + 3x2;

y4 = 8 - 1x1 - 0x2;

y5 = 6 - 0x1 - 1x2;

Каждая строка симплекс-таблицы соответствует базисной переменной, а каждому столбцу соответствует свободная переменная xj и выделен столбец свободных членов (правых частей ограничений) bi . Внизу помещена строка целевой функции F.

Решение задачи симплексным методом

Разрешающий элемент - А(3;1);

Разрешающий элемент - А(4;2);

Разрешающий элемент - А(2;1);

5. Двойственность задач линейного программирования

Если существует исходная задача нахождения максимума целевой функции F, то существует и двойственная к ней задача нахождения минимума функционала Ф

Существует правило перехода к двойственной задаче, заключающееся в следующем:

j-й столбец, составленный из коэффициентов ограничения исходной задачи, совпадает с j-й строкой, составленной из коэффициентов ограничений двойственной задачи.

Строка, составленная из коэффициентов целевой функции, совпадает со столбцом, составленным из констант правых частей ограничений двойственной модели.

Столбец, составленный из констант правых частей ограничений исходной модели, совпадает со строкой, составленной из коэффициентов целевой функции двойственной задачи.

Направление знаков неравенства в исходной модели противоположно направлению знаков неравенства в двойственной задаче.

Требование максимизации (или минимизации) в исходной задаче заменено требованием минимизации (или максимизации) в двойственной задаче.

Исходная система ограничений:

1) -5x1+4x2<=20;

2) 2x1+3x2<=24;

3) 1x1-3x2<=3;

4) 1x1+0x2<=8;

5) 0x1+1x2<=6.

Целевая функция: Fmax=3X1+2X2.

Двойственная задача запишется следующим образом:

Ф=20y1+24y2+3y3+8y4+6y5

Система ограничений:

1) -5y1+2y2+1y3+1y4+0y5>=3;

2) 4y1+3y2-3y3+0y4+1y5>=2;

Конечную симплекс-таблицу двойственной задачи, исходя из конечной симплекс-таблицы прямой задачи, можно записать в виде:

Размещено на Allbest.ru