Тема: Решение симплекс-методом задачи линейного программирования.

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«БЕЛГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ НАЦИОНАЛЬНЫЙ

ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ»

( Н И У « Б е л Г У » )

ИНСТИТУТ ИНЖЕНЕРНЫХ И ЦИФРОВЫХ ТЕХНОЛОГИЙ

КАФЕДРА ПРИКЛАДНОЙ ИНФОРМАТИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Исследование операций и методы оптимизации

Лабораторная работа №4
Тема: Решение симплекс-методом задачи линейного программирования.

студентки очного отделения

4 курса, 12001504 группы,

Марко С. Тангуила

Проверил:

Старший преподаватель

Болгова Евгения Витальевна

Белгород, 2018 год

Цель работы

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

Результат выполнения работы

1. Матрица A коэффициентов системы имеет вид:

   7	5	1	0	0
   -5	4	0	1	0
   3	-2	0	0	1

2. Первая часть системы ограничений уравнений имеет вид:

   35

   20

   2

3. Составление симплексной таблицы. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последняя строка – это целевая функция. Последние три векторы-столбцы образуют базис в трехмерном пространстве. Следовательно, базисные переменные x_B=[x₃,x₄,x₅]^T, а свободные переменные x_F=[x₁,x₂]^T:

Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.

1. Выбор разрешающего столбца. Минимальный элемент p_jj*=2.

2. Выбор разрешающей строки. Разрешающий столбец содержит положительные элементы a₃₂=5 и a₄₂=4. Найдем min(35:5, 20:4)=5 (минимум равен b₄/a₄₂). Следовательно, номер разрешающей строки i*=4. Разрешающий элемент a₄₂=4, он выделен серым цветом.

3. Замена базиса:

1. в левом столбце новой таблицы на место 4 ставится 2. Остальные индексы остаются на своих местах.

2. на место элемента a₄₂=4 в новой таблице пишем элемент a₂₄=1:а₄₂=1:4=1/4.Затем, вычисляются новые элементы вместо элементов разрешающего столбца и строки.

1. пересчитываются остальные элементы симплекс-таблицы по следующим формулам:

,,,

Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.

1. В качестве разрешающего выберем столбец j*=1, так как это наибольший коэффициент. Разрешающий столбец содержит положительные элементы a₃₁=53/4 и a₅₁=1/2. Найдем min(10:53/4, 12:1/2)=40/53 (минимум равен b₃/a₃₁). Следовательно, номер разрешающей строки i*=3. Разрешающий элемент a₃₁=53/4, он выделен серым цветом.

2. Пересчет симплекс-таблицы:

Среди коэффициентов целевой функции нет положительных. Поэтому эта таблица определяет оптимальный план задачи. Оптимальный план можно записать так:

x₁=40/53, x₂=315/53, x₃=0, x₄=0, x₅=616/53

F(X)=-1*40/53-2*315/53-4=-882/53≈16,6415

Код решения с помощью Matlab:

function lab4(x)

f=[-1 -2 0 0 0];

Aeq=[7 5 1 0 0; -5 4 0 1 0; 3 -2 0 0 1];

beq=[35 20 2];

lb=zeros(5,1);

[x,fval]=linprog(f,[],[],Aeq,beq,lb);

x

fval-4

Результат выполнения: