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

Рассмотрим применение симплекс-метода на примере задачи, решенной графическим способом.

Формируем исходную систему уравнений:

1x₀-3x₁-5x₂=0 (0)

2x₁+4x₂+1x₃=16 (1)

3x₁+x₂+1x₄=9 (2)

Здесь в уравнении (0) функция F заменена на x₀, а в левые части уравнений (1) и (2) добавлены фиктивные переменные x₃ и x₄ (x₃³0, x₄³0) для превращения неравенств в уравнения. Выбираем базис для начального решения. Количество переменных в базисе должно совпадать с числом уравнений, базисные переменные в системе должны присутствовать только по одному разу и коэффициенты при них равны единице. Соответственно этим условиям базисом является x₀=0, x₃=16 и x₄=9. Тогда при этом x₁=x₂=0. Базисное решение совпадает с началом координат.

Первая итерация.

Выбираем переменную, которую будем вводить в базис.
В данном случае это x₂, так как с₂>с₁.

Для определения значения x₂ составим таблицу.

Вводим x₂=4 в уравнение (1), а x₃ выведем из базиса. Пересчитываем систему уравнений. Уравнение (1) делим на 4 (коэффициент при x₂). Получаем уравнение (1’):

0.5x₁+1x₂+0.25x₃=4. (1’).

Выражаем отсюда x₂=4-0.5x₁-0.25x₃ и подставляем его в уравнения (0) и (2):

1x₀-3x₁-5(4-0.5x₁-0.25x₃)=0,

1x₀-0.5x₁+1.25x₃=20, (0’)

3x₁+4-0.5x₁-0.25x₃+1x₄=9,

2.5x₁-0.25x₃+1x₄=5. (2’)

Новая система уравнений имеет вид

1x₀-0.5x₁+1.25x₃=20 (0’)

0.5x₁+1x₂+0.25x₃=4 (1’)

2.5x₁-0.25x₃+1x₄=5 (2’)

Новый базис составляют переменные x₀=20, x₂=4, x₄=5. При этом x₁=x₃=0. Это решение совпадает с (.) А. Необходима еще одна итерация, так как в уравнении (0’) коэффициент при x₁ отрицателен.

Пересчитываем систему уравнений, вводя x1=2 в уравнение (2’), для чего его делим на 2.5.

Получим уравнение (2”)

1x₁-0.1x₃+0.4x₄=2. (2”)

Выражаем отсюда x₁=2+0.1x₃-0.4x₄ и подставляем его в другие уравнения:

1x₀-0.5(2+0.1x₃-0.4x₄)+1.25x₃=20,

1x₀+1.2x₃+0.2x₄=21, (0”)

0.5x₀(2+0.1x₃-0.4x₄)+1x₂+0.25x₃=4,

1x₂+0.3x₃-0.2x₄=3, (1”)

Новая система уравнений имеет вид

1x₀+1.2x₃+0.2x₄=21, (0”)

1x₂+0.3x₃-0.2x₄=3, (1”)

1x₁-0.1x₃+0.4x₄=2. (2”)

Новый базис составляют переменные x₀=21, x₂=3, x₁=2, среди которых нет фиктивных. При этом x₃=x₄=0. Это решение совпадает с точкой B (x₁=2, x₂=3, F=21) и является наилучшим, так как в уравнении (0”) нет отрицательных коэффициентов при переменных x₁ и x₂.

Задача 17

Транспортная задача.

В двух пунктах отправления A1 и А2 находится соответственно 20 и 30 т горючего. В пункты В1, В2, В3 требуется доставить соответственно 15, 15 и 20 т горючего. Стоимости перевозки тонны горючего из пункта A1 в пункты В1, В2, В3 составляют соответственно 5, 4 и 1 денежных единиц, а из пункта А2 4, 3, 2 соответственно. Составить оптимальный план перевозок горючего так, чтобы общая сумма транспортных расходов была наименьшей.

Решение.

Построим таблицу исходных данных:

Заполнение начнем с клетки (1,1): x₁₁=min(20,15)=15, первый столбец закрыт. Переходим к клетке (1,2): x₁₂=min(20-15,15)=5, первая строка закрыта; далее переходим к клетке (2,2): x₂₂=min(15-5,30)=10. Так как во второй строке оказался остаток равный 20, то переходим к заполнению клетки (2,3), куда заносим x₂₃=20. Поскольку остатки по строке и столбцу равны нулю, опорное исходное решение построено. Этому плану соответствуют затраты в количестве F= 15×5+5×4+10×3+20×2=165 денежных единиц. Такой способ построения опорного плана называется методом Северо-Западного угла.

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

Припишем каждому пункту Ai некоторое число, условно равное стоимости ед. груза в этом пункте поставки u_i. Соответственно каждому пункту потребления Bj припишем также некоторое число v_j. Они называются потенциалами и связаны соотношением v_j=u_i+c_ij. Теперь можно приступить к попытке улучшения опорного решения.

Первый этап.

Если предположить, что потенциал u₁=0, то можно вычислить по формуле v_j=u_i+c_ij числовые значения всех остальных. Далее следует расставить все потенциалы по соответствующим ячейкам.

Второй этап.

Проверяем возможности улучшения плана. Для этого анализируем незанятые клетки и по условию v_j-u_i£c_ij определяем возможности дальнейшей оптимизации опорного решения.

Если v_j-u_i-c_ij£0, то резервов оптимизации решения нет, если же

v_j-u_i-c_ij>0, то план не оптимален, есть резервы и, следовательно, можно переходить к алгоритму получения нового плана.

Рассмотрим пример применения метода потенциалов для оптимизации опорного решения.

Пусть опорное решение имеет следующий вид:

Оценим этот план по стоимости: F=15×5+5×4+10×3+20×2=165.

Рассчитаем потенциалы и внесем их в таблицу. Положим, что u1=0, тогда

v1=u1+c11=0+5=5,

v2=u1+c12=0+4=4,

u2=v2-c22=4-3=1,

v3=u2+c23=1+2=3

и таблица примет вид

Выполним проверку для незанятых ячеек условия v_j-u_i-c_ij£0. Для ячейки А1В3 получаем v3-u1-cij£0 или 3-0-1£0, т.е. условие не выполняется и, следовательно, есть резервы для улучшения плана. Для ячейки А1В3 v1-u2-c21 или 5-1-4=0 – условие выполняется, т.е. резервов для улучшения плана нет.

Переместив 5 единиц продукции по циклу А1В2®А1В3®А2В3®А2В2, получим новый план:

Оценим план: F=15×5+5×1+15×3+15×2=155.

Теперь выполним проверку условия v_j-u_i-c_ij£0 для ячеек А1В2 и А2В1. Для ячейки А2В1 получаем 5+1-3£0, т.е. условие не выполняется и, следовательно, есть резервы для улучшения плана. Для ячейки А1В2 или 2-4+0£0 – условие выполняется, т.е. резервов для улучшения плана нет.

Перемещая 15 единиц по контуру А1В1®А1В3®А2В3®А2В1, получим новый план:

Оцениваем план: F=20×1+15×4+15×3=125.

Дальнейшая проверка показывает, что условие v_j-u_i-c_ij£0 для А1В2 и А2В3 выполняется, следовательно, резервов для улучшения плана нет.

Задача 18 (динамическое программирование).

Производственное объединение, имеющее четыре филиала в разных городах, желает распределить ресурсы в 10 млн руб. так, чтобы получить наибольшую прибыль. Специалисты объединения изучили состояние рынка в каждой зоне и определили кривые математического ожидания прибыли как функции полных капитальных вложений:

Решение.

Задача сводится к перебору всех разбиений 10 на четыре группы из целых чисел: (10,0,0,0); (9,1,0,0); (9,0,1,0); (9,0,0,1); … (8,1,1,0); (8,1,0,1); (8,0,1,1); (8,2,0,0); … и т.д. Всего 286 комбинаций. Можно вычислить доходы, соответствующие каждой комбинации, и выбрать наибольший. Таким образом, имеем комбинаторную задачу. Применим для ее решения метод динамического программирования. Обозначим функции дохода для зон 1, 2, 3 и 4 соответственно f₁(x), f₂(x), f₃(x) и f₄(x). Примем F_1,2(A)– оптимальное распределение, когда А вкладывается в зоны 1 и 2 вместе; F_1,2,3(A) – 1, 2 и 3 вместе; F_1,2,3,4(A) – оптимальное распределение, когда А вкладывается во все четыре зоны вместе.

Таким образом, чтобы определить F_1,2(2), надо вычислить

f₁(0)+ f₂(2) = 0.00+0.41=0.41;

f₁(1)+ f₂(1)= 0.28+0.25=0.53;

f₁(2)+ f₂(0)= 0.45+0.00=0.45,

так что F_1,2(A)=0.53.

Вычисляем таким образом значения F_1,2(0); F_1,2(1); F_1,2(2); F_1,2(3); …; F_1,2(20), что дает таблицу

Таблица позволяет определить политики, соответствующие оптимальному доходу при данных капитальных вложениях. Например, если в зоны 1 и 2 вложить 4 млн руб., то в зону 1 следует вложить 3 млн руб., а в зону 2 – 1 млн руб.

Продолжим исследование поиском F_1,2,3(A) , т.е. поиском оптимальной комбинации, когда капитальные вложения вкладываются в зоны 1, 2 и 3, причем

Продолжим вычисления, определяя

Можно убедиться, что те же результаты имеют место при любом ином порядке вычислений: F_3,1(A), F_3,1,2(A), F_3,1,2,4(A) и т.п., результаты расчетов оформим в виде таблицы:

Таким образом, оптимальное распределение 10 млн руб.
в четыре зоны следующее: (4,3,1,2). При этом гарантируется максимальная прибыль 1.81.

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

Варианты заданий к контрольным работам

Контрольная работа №1

Задача 1. Описать свойства функций, построить графики

№ вар.	Функции
	а	б	в

Задача 2. Найти экстремумы функций одной переменной. Построить графики функций и . В качестве исследуемых функций выбрать функции а и взадачи 1.

Задача 3. Найти экстремумы функции двух переменных.

№ вар.	Функция

Задача 4.Найти первообразные функций

№ вар.	Функции
	а	б

Задача 5. Вычислить интеграл.

№ вар.	Интеграл

Задача 6. Аналитическая геометрия на плоскости

А) Линии первого порядка

1. Построить треугольник с вершинами A(-2;4); B(2;1) и C(5;5) и определить его периметр и углы.

2. Определить середины сторон треугольника с вершинами А(-1;2), B(5;6) и С(3;0).

3. Отрезок прямой с концами в точках А(4;2) и В(13; 8), разделен на три равные части. Определить координаты точек деления.

4. Даны вершины треугольника: А(6;4), B(3;0), С(2;5). Определить длины медиан и вычислить координаты точки их пересечения.

5. Даны вершины треугольника: А(3;3), B(6;-1), С(-5;-3). Найти точку пересечения биссектрисы угла А со стороной ВС и её длину AD.

6. Дан треугольник с вершинами А(-5;0), В(2; 1), С(-2;3). Написать уравнения сторон треугольника.

7. В треугольнике с вершинами A(2;0), В(-2;6) и С(-4;2) проведены высота BD и медиана BE. Найти уравнения AC, BE и BD.

8. Найти углы и уравнения сторон треугольника с вершинами A(4;6), B(-3;0) и С(2;-3).

9. Найти точку пересечения медиан и точку пересечения высот треугольника, вершины которого A(-4;3), В(2;-4) и С(5;1).

10.Найти длину высоты AD в треугольнике с вершинами А(3;3), В(-4; 1), С(1;-2).

Задача 7.Теория последовательностей и функций одной переменной.

Найти пределы:

1. ,

2. ,

3. ,

4. ,

5. ,

6. ,

7. ,

8. ,

9. ,

10. .

Задача 8. Дифференциальное исчисление функции одной переменной

Найти производные от функций:

1.	2.
3.	4.
5.	6.
7.	8.
9.	10.

Контрольная работа №2

Задача 1.

Для матриц А и В определить

Номер варианта	А	В
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

Задача 2.

Используя матрицы А и В, вычислить методом алгебраических дополнений

Номер варианта	А	В
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

Задача 3.

Решить систему уравнений методом Жордана-Гаусса. Если система является неопределенной, то в ответ записать одно базисное решение и одно частное, не являющееся базисным.

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

Задача 4. Решить задачу линейного программирования симплекс-методом, привести графическое решение задачи, обеспечивающее Fmax. Математическая постановка задачи в общем виде:

Конкретное задание, например, для варианта №3 имеет следующий вид:

Задача 5. Решить транспортную задачу методом потенциалов, опорный план построить методом Северо-Западного угла.

Задача 6. Динамическое программирование

Распределить 8 млн. руб. между четырьмя предприятиями так, чтобы получить максимальную прибыль. Статистические исследования математического ожидания прибыли по зонам даны в следующих 10 таблицах, соответствующих разным вариантам.

Вариант 1.

Вариант 2.

Вариант 3.

Вариант 4.

Вариант 5.

Вариант 6.

Вариант 7.

Вариант 8.

Вариант 9.

Не нашли, что искали? Воспользуйтесь поиском по сайту: