Метод ветвей и границ для задачи целочисленного программирования.

Рассмотрим частично целочисленную задачу ЛП:

минимизировать

(10.23)

при условиях

; (10.24)

; (10.25)

- целые числа. (10.26)

Процесс поиска оптимального решения начинают с решения непрерывной задачи ЛП. Если полученный при этом оптимальный план не удовлетворяет условию (10.26), то значение целевой функции дает нижнюю оценку для искомого решения, т.е. .

27.Опишите процесс решения задач линейного программирования с использованием программного обеспечения MATLAB

В состав MATLAB входит Optimization Toolbox, предназначенный для решения линейных и нелинейных оптимизационных задач.

Задача линейного программирования состоит в нахождении вектора x, который минимизирует целевую линейную функцию

f^Tx при условии AX≤B ; X≥0,

где с=(с₁, c₂,…,c_n) представляет собой n-мерный вектор, соствленный из коэффициентов целевой функции, причем c^T – транспонированная вектор- строка; x=(x₁ . x_n) – n –мерный вектор переменных решений,

B=[b₁

b₂ m-мерный вектор свободных членов

b_m]

B_eq=[b_eq1

_…

b_eqr] ограничения в виде равенств;

двусторонние покомпонентные ограничения в векторной форме

lb≤x≤ub

A=

Пример: задача состваления рациона питания

Имеются 3 продукта П₁, П₂ и П₃ разной цены, каждый из которых содержит определенное количество питательных ингридиентов И₁, И₂, И₃, И_4.

Известно, что в день требуется : И₁не менее 250, И₂ не менее 60, И₃ не менее 100 и И₄ не менее 220. Требуется минимизировать затраты на приобретение продуктов. Очевидно, что количество приобретаемых процессов не может быть отрицательным..

Записываем целевую функцию, матрицу A, векторы b и lb в соответствии с требованиями Toolbox, обозначив искомые количества продуктов через x_1, x₂ и x₃ соответственно. Поскольку линейные ограничения содержат «меньшк или равно», а количество ингредиентов в рационе не может быть менее заданных величин, то следует изменить знаки обеих частей системы.При вызове программы linprog вместо неиспользуемых ограничение (нет ограничений в виде равенств) задайте пустые массивы, обозначаемые в MATLAB пустыми скобками.

Программа ration

% задание матрицы и вектора правой части системы неравенств

A=[4 6 15

2 2 0

5 3 4

7 3 12]

A=-A; b=[250 60 100 220]; b=-b;

% Определение коэффициентов целеой функции f=[44; 35; 100];

% Задание ограничений снизу на переменные lb=[0; 0; 0];

% решение и вывод результата в командное окно x=linprog(f,A,b,[],[],lb)

31.Опишите алгоритм решения задач дискретного программирования методом ветвей и границ