Методы оптимальных решений в линейном программировании

ОБЩАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Общая задача математического программирования: найти экстремум целевой

Если целевая функция (1.1) и система ограничений (1.2) линейны, то задача

F(X) = с1 х1 + с2 х2 + ... + сп

В задаче на нахождение минимального значения целевой функции математическая модель её

РАССМОТРИМ ВАРИАНТЫ СОСТАВЛЕНИЯ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ДЛЯ СЛЕДУЮЩИХ ЗАДАЧ

Задача 1. (Планирование производства.)
Некоторое

Необходимо так организовывать производство, чтобы получить наибольшую прибыль при реализации продукции

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ

Обозначим через хi j — время, затраченное на изготовление

При этом продукции 1-го вида будет выпущено 20х11+ 30х21 , 2-го

ОКОНЧАТЕЛЬНО ПОЛУЧАЕМ МАТЕМАТИЧЕСКУЮ МОДЕЛЬ ЗАДАЧИ

F=5(20х11+ 30х21)+3(25х12+20х22)+6(30х13+ 15х23) → max,

ЗАДАЧА 2. (ЗАДАЧА О СМЕСИ.)

Известно, что при правильном питании человек

Математическая модель задачи
Пусть хi — количество продукта Пi, потребляемого в день

F=25х1 +30x2 +20х3 → min,

ЗАДАЧА 3. (О РАСКРОЕ МАТЕРИАЛА.)

Для изготовления некоторого изделия требуется 2

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ РАССМОТРИМ ВОЗМОЖНЫЕ ВАРИАНТЫ РАСПИЛИВАНИЯ ДОСОК.

Обозначим через хi— количество досок, распиленных i-м способом, тогда заготовок по

х 3 + x5 + 2x6=к. Исключим к.
2(3x1+ 2х2

Окончательно получим математическую модель к=х 3 + x5 + 2x6→ max,

все

ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задача с двумя переменными
Пусть требуется найти

Алгоритм решения ЗЛП с двумя переменными графическим методом:
Строится область допустимых решений.
Строится

Пример 1. Решить задачу линейного программирования графическим методом: F(X)=2x1+4x2→ max,

Решение. Изобразим на плоскости систему координат Ох1х2 и построим граничные прямые

Перпендикулярно вектору построим одну из линий уровня (на рис. она проходит

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

Пример 2. Найти минимум функции F(X)=2x1+x2→ min при ограничениях

А (6/7; 25/7) и Fmin = 37/7.

ДВОЙСТВЕННАЯ ЗАДАЧА

В теории двойственности используются четыре пары двойственных задач (приведем их

Исходная задача Двойственная задача
Симметричные пары
1. F(X)=CX→max, Z(Y)=YA0→min
AX≤ A0 , YA≥

Несимметричные пары
1. F(X)=CX→max, Z(Y)=YA0→min
AX= A0 , YA≥ C.
X≥θ;
2.

Здесь С=(с1, с2,…, сn), Y= (у1, у2,… …,ут),

Пример 1. Составить задачу, двойственную к данной

F(X) = х1 + 4х2

Решение. Умножим первое ограничение-неравенство на -1. Задача примет вид исходной задачи

Окончательно двойственная задача имеет вид
Z(Y) = -10у1 + 6у2 + 12у3→

Первая теорема двойственности
Теорема. Если одна из пары двойственных задач имеет оптимальное

Вторая теорема двойственности
Пусть имеется симметричная пара двойственных задач

Теорема. Для того чтобы допустимые решения Х= (х1, х2, ..., хп),

Пример 1. Для данной задачи составить двойственную, решить ее графическим методом

Решение. Составим двойственную задачу: Z(Y) = 2у1 + 3у2→ max,

Решим эту задачу графическим методом. На рис. изображены область допустимых решений

2у1=6

у1*=3, у2*=4.

Y *=(3,4).
Z(Y *)=2·3+3·4=18.

Подставим оптимальное решение Y *= (3, 4) в систему ограничений. Получим,

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

Отсюда находим х3*= 1, х4* = 2. Окончательно записываем X*=(0,0,1,2,0).
Ответ: min

ТРАНСПОРТНАЯ ЗАДАЧА

Формулировка транспортной задачи
Однородный груз сосредоточен у т поставщиков в объемах

Исходные данные задачи могут быть представлены также в виде вектора запасов

ОПОРНОЕ РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

Свойство системы ограничений транспортной задачи:
ранг системы векторов ― условий транспортной

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

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

Существует ряд методов построения начального

Во избежание ошибок после построения начального опорного решения необходимо проверить, что

ПЕРЕХОД ОТ ОДНОГО ОПОРНОГО РЕШЕНИЯ К ДРУГОМУ

В транспортной задаче переход от

Теорема (о существовании и единственности цикла).
Если таблица транспортной задачи содержит

Сдвигом по циклу на величину θ называется увеличение объемов перевозок во

МЕТОД ПОТЕНЦИАЛОВ

Числа Δij называются оценками свободных клеток таблицы или векторов ― условий

ОСОБЕННОСТИ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ С НЕПРАВИЛЬНЫМ БАЛАНСОМ

Следовательно, чтобы задача в рассматриваемом случае имела решение, необходимо ввести фиктивного

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

Алгоритм решения транспортной задачи методом потенциалов
Проверяют выполнение необходимого и достаточного условия

3.Строят систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений

при

если известен потенциал

.

4. Проверяют, выполняется ли условие оптимальности для свободных клеток таблицы. Для

5. Переходят к новому опорному решению, на котором значение целевой функции

Строят цикл, включающий в свой состав данную клетку и часть клеток,

Если минимум достигается в нескольких клетках, то одна из них остается

ПРИМЕР. РЕШИТЬ ТРАНСПОРТНУЮ ЗАДАЧУ, ДАННЫЕ ПРИВЕДЕНЫ В ТАБЛИЦЕ

Решение. 1. Проверяем выполнение необходимого и достаточного условия разрешимости задачи. Находим

2. Составляем начальное опорное решение методом минимальной стоимости. Записываем матрицу стоимостей

Полученное решение Х1 имеет т + п — 1=4 + 4

3. Для проверки оптимальности опорного решения необходимо найти потенциалы. По признаку

Система состоит из семи уравнений и имеет восемь переменных. Система неопределенная.

4. Проверяем опорное решение Х1 на оптимальность. С этой целью вычисляем

5. Переходим к новому опорному решению. Находим клетку таблицы, которой соответствует

Х1

bj

v1=2 v2=3 v3=4 v4=9

Положительные оценки записываем в левые нижние углы соответствующих клеток таблицы, вместо

В данном случае минимум перевозок в клетках, отмеченных знаком «-», достигался

6. Проверяем второе опорное решение Х2 на оптимальность. Находим, потенциалы и

v1=1 v2=0 v3=3 v4=1

Х3

Вычисляем значение целевой функции на третьем опорном решении:
F(X3)= 0·1 + 100·1

v1=1 v2=0 v3=3 v4=1

Х4

Вычисляем значение целевой функции на четвертом опорном решении: F(Х4) = 0·l

Х5

v1=3 v2=4 v3=7 v4=3