Решение задач симплекс-методом
Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 05.04.2016 |
| Размер файла | 191,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
ЗАДАНИЕ 1
Для приведенной ниже задачи составить математическую модель, подставив данные своего варианта из таблицы 1. Решить задачу симплекс методом и графически, показать соответствие опорных решений и вершин допустимой области, проверить полученные значения на компьютере.
Сельскохозяйственное предприятие снабжает своей продукцией перерабатывающие предприятия региона. Для производства двух видов сельскохозяйственной продукции с пастбищ и сенокосов (П1, П2 ), требуется три вида ресурсов Р1 , Р2 , Р3 , где Р1 - трудовые ресурсы, Р2 - минеральные удобрения, Р3 - оросительная вода. При получении 1т продукции с пастбищ первый ресурс используется tп1 чел- час, второй ресурс - tп2 кг, третий ресурс -tп3 м 3 . При получении 1 т продукции с сенокосов первый ресурс используется tс1 чел- час, второй ресурс - tс2 кг, третий ресурс - tс3 м3 . Запасы ресурсов ограничены и не может превышать для первого вида продукции T1 чел-час, для второго - T2 кг, для третьего - T3 м3 . При реализации 1 т продукции с пастбищ предприятие получает прибыль С1 рублей, а при реализации 1 т продукции с сенокосов - С2 рублей. Найти оптимальный план выпуска продукции каждого вида, дающий максимальную прибыль от реализации всей продукции.
|
№ |
tп1 |
tп2 |
tп3 |
tс1 |
tс2 |
tс3 |
T1 |
T2 |
T3 |
С1 |
С2 |
|
|
3 |
5 |
3 |
1 |
3 |
2 |
0 |
259 |
162 |
39 |
18 |
11 |
Решение:
Обозначим за X1 - объем в тоннах продукции с пастбищ, за X2 - объем в тоннах продукции с сенокосов
Составим математическую модель
Ограничение на трудовые ресурсы:
5x1+3x2?259
Ограничение на минеральные удобрения
3x1+2x2?162
Ограничения на оросительную воду:
x1?39
При этом заметим, что объем продукции не должен быть отрицательным
x1, x2?0
Целевая функция будет иметь вид:
F = 18x1+11x2 > max
Решим задачу графически:
Построим уравнение 5x1+3x2 = 259 по двум точкам.
x1 = 0 =>x2 = 86.33.
x2 = 0 => x1 = 51.8.
Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 5 * 0 + 3 * 0 - 259 ? 0, т.е. 5x1+3x2 - 259? 0 в полуплоскости ниже прямой.
Построим уравнение 3x1+2x2 = 162 по двум точкам.
x1 = 0 => x2 = 81.
x2 = 0 => x1 = 54.
Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 3 * 0 + 2 * 0 - 162 ? 0, т.е. 3x1+2x2 - 162? 0 в полуплоскости ниже прямой.
Построим уравнение x1 = 39.
Эта прямая проходит через точку x1 = 39 параллельно оси OX2. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 * 0 - 39 ? 0, т.е. x1 - 39? 0 в полуплоскости левее прямой.
Построим прямую, отвечающую значению функции F = 0: F = 18x1+11x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора - точка (0; 0), конец - точка (18; 11).
Прямая F(x) = const пересекает область в точке C, полученная в результате пересечения прямых:
5x1+3x2=259
3x1+2x2=162
Решив систему уравнений, получим: x1 = 32, x2 = 33
Откуда найдем максимальное значение целевой функции:
F(X) = 18*32 + 11*33 = 939
Решим задачу симплекс методом
переход к канонической форме
В 1-м неравенстве смысла (?) вводим базисную переменную x3. В 2-м неравенстве смысла (?) вводим базисную переменную x4. В 3-м неравенстве смысла (?) вводим базисную переменную x5.
5x1 + 3x2 + 1x3 + 0x4 + 0x5 = 259
3x1 + 2x2 + 0x3 + 1x4 + 0x5 = 162
1x1 + 0x2 + 0x3 + 0x4 + 1x5 = 39
|
Б |
1 |
x1 |
x2 |
Q |
|
|
x3 |
259 |
5 |
3 |
514/5 |
|
|
x4 |
162 |
3 |
2 |
54 |
|
|
x5 |
39 |
1 |
0 |
39 |
|
|
F |
0 |
-18 |
-11 |
0 |
Данное решение X=(0;0) соответствует точке A на графике
|
Б |
1 |
x2 |
x5 |
Q |
|
|
x3 |
64 |
3 |
-5 |
211/3 |
|
|
x4 |
45 |
2 |
-3 |
221/2 |
|
|
x1 |
39 |
0 |
1 |
- |
|
|
F |
702 |
-11 |
18 |
0 |
Данное решение X=(39;0) соответствует точке D на графике
|
Б |
1 |
x3 |
x5 |
Q |
|
|
x2 |
211/3 |
1/3 |
-12/3 |
- |
|
|
x4 |
21/3 |
-2/3 |
1/3 |
7 |
|
|
x1 |
39 |
0 |
1 |
39 |
|
|
F |
9362/3 |
32/3 |
-1/3 |
0 |
Данное решение X=(39; 211/3) соответствует точке E на графике
|
Б |
1 |
x3 |
x4 |
Q |
|
|
x2 |
33 |
-3 |
5 |
||
|
x5 |
7 |
-2 |
3 |
||
|
x1 |
32 |
2 |
-3 |
||
|
F |
939 |
3 |
1 |
Данное решение X=(32; 33) соответствует точке C на графике
При решении задачи на компьютере получаем следующую модель:
Формулы имеют следующий вид:
Математическая модель
В результате получаем
ЗАДАНИЕ 2
Решить симплексным методом с искусственным базисом каноническую задачу линейного программирования:
Z = c1x1 + c2x2 + c3x3 + c4x4 + c5x5 > max
При условиях:
Выполнить проверку оптимальности найденного решения, используя теорию двойственности. Найти оптимальное решение двойственной задачи.
Решение
F(X) = 2x1 - 2x2 - 3x3 - 2x4 - 2x5 ->max
3x1 + 3x2 - x3 - x5?13
x1 + 3x2 - x4 - 3x5?1
- 2x1 + x2 + x3 - 3x4 + x5?8
переход к канонической форме
В 1-м неравенстве смысла (?) вводим базисную переменную x6. В 2-м неравенстве смысла (?) вводим базисную переменную x7. В 3-м неравенстве смысла (?) вводим базисную переменную x8.
3x1 + 3x2-1x3 + 0x4-1x5 + 1x6 + 0x7 + 0x8 = 13
1x1 + 3x2 + 0x3-1x4-3x5 + 0x6 + 1x7 + 0x8 = 1
-2x1 + 1x2 + 1x3-3x4 + 1x5 + 0x6 + 0x7 + 1x8 = 8
решение задача математический симплексный
|
Б |
1 |
x1 |
x2 |
x3 |
x4 |
x5 |
Q |
|
|
x6 |
13 |
3 |
3 |
-1 |
0 |
-1 |
41/3 |
|
|
x7 |
1 |
1 |
3 |
0 |
-1 |
-3 |
1 |
|
|
x8 |
8 |
-2 |
1 |
1 |
-3 |
1 |
- |
|
|
F |
0 |
-2 |
2 |
3 |
2 |
2 |
0 |
|
Б |
1 |
x2 |
x3 |
x4 |
x5 |
x7 |
Q |
|
|
x6 |
10 |
-6 |
-1 |
3 |
8 |
-3 |
11/4 |
|
|
x1 |
1 |
3 |
0 |
-1 |
-3 |
1 |
- |
|
|
x8 |
10 |
7 |
1 |
-5 |
-5 |
2 |
- |
|
|
F |
2 |
8 |
3 |
0 |
-4 |
2 |
0 |
|
Б |
1 |
x2 |
x3 |
x4 |
x6 |
x7 |
Q |
|
|
x5 |
5/4 |
-3/4 |
-1/8 |
3/8 |
1/8 |
-3/8 |
||
|
x1 |
19/4 |
3/4 |
-3/8 |
1/8 |
3/8 |
-1/8 |
||
|
x8 |
65/4 |
13/4 |
3/8 |
-25/8 |
5/8 |
1/8 |
||
|
F |
7 |
5 |
5/2 |
3/2 |
1/2 |
1/2 |
Оптимальный план можно записать так:
X =( 43/4;0;0;0; 11/4)
F(X) = -2*11/4 + 2*43/4 = 7
Составим двойственную задачу:
|
Исходная задача I |
Двойственная задача II |
||
|
2x1 - 2x2 - 3x3 - 2x4 - 2x5 > max |
- |
13y1 + y2 + 8y3 > min |
|
|
3x1 + 3x2 - x3 - x5?13 |
- |
y1 ? 0 |
|
|
x1 + 3x2 - x4 - 3x5?1 |
- |
y2 ? 0 |
|
|
- 2x1 + x2 + x3 - 3x4 + x5?8 |
- |
y3 ? 0 |
|
|
x1 ? 0 |
- |
3y1 + y2 - 2y3?2 |
|
|
x2 ? 0 |
- |
3y1 + 3y2 + y3?-2 |
|
|
x3 ? 0 |
- |
- y1 + y3?-3 |
|
|
x4 ? 0 |
- |
- y2 - 3y3?-2 |
|
|
x5 ? 0 |
- |
- y1 - 3y2 + y3?-2 |
Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
3*43/4 + 3*0 + (-1)*0 + 0*0 + (-1)*11/4 = 13 = 13 => y1 ? 0
1*43/4 + 3*0 + 0*0 + (-1)*0 + (-3)*11/4 = 1 = 1 => y2 ? 0
-2*43/4 + 1*0 + 1*0 + (-3)*0 + 1*11/4 = -81/4 < 8 => y3 = 0
x1 ? 0=>3y1 + y2 - 2y3=2
x5 ? 0=>- y1 - 3y2 + y3=-2
Получаем систему из двух уравнений:
Получаем, что
y1 = 1/2
y2 = 1/2
y3 = 0
Z(Y) = 13*1/2+1*1/2+8*0 = 7
Так как Z(Y)=F(X), значит полученный план является оптимальным
ЗАДАНИЕ 3
|
ai/bj |
200 |
400 |
100 |
200 |
100 |
|
|
200 |
1 |
7 |
12 |
2 |
5 |
|
|
100 |
2 |
3 |
8 |
4 |
7 |
|
|
200 |
3 |
5 |
4 |
6 |
9 |
|
|
200 |
4 |
4 |
3 |
8 |
2 |
|
|
300 |
5 |
3 |
7 |
10 |
1 |
Решение:
Проверим необходимое и достаточное условие разрешимости задачи.
?a = 200 + 100 + 200 + 200 + 300 = 1000
?b = 200 + 400 + 100 + 200 + 100 = 1000
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
x21 = min(100,200) = 100.
x11 = min(200,100) = 100.
x55 = min(300,100) = 100.
x14 = min(100,200) = 100.
x43 = min(200,100) = 100.
x52 = min(200,400) = 200.
x42 = min(100,200) = 100.
x32 = min(200,100) = 100.
x34 = min(100,100) = 100.
|
v1=1 |
v2=1 |
v3=0 |
v4=2 |
v5=-1 |
|||
|
u1=0 |
1 100 [-] |
7 |
12 |
2 100 [+] |
5 |
200 |
|
|
u2=1 |
2 100 |
3 |
8 |
4 |
7 |
100 |
|
|
u3=4 |
3 [+] |
5 100 |
4 |
6 100 [-] |
9 |
200 |
|
|
u4=3 |
4 |
4 100 |
3 100 |
8 |
2 |
200 |
|
|
u5=2 |
5 |
3 200 |
7 |
10 |
1 100 |
300 |
|
|
200 |
400 |
100 |
200 |
100 |
m + n - 1 = 9.
Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 1*100 + 2*100 + 2*100 + 5*100 + 6*100 + 4*100 + 3*100 + 3*200 + 1*100 = 3000
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 1; 0 + v1 = 1; v1 = 1
u2 + v1 = 2; 1 + u2 = 2; u2 = 1
u1 + v4 = 2; 0 + v4 = 2; v4 = 2
u3 + v4 = 6; 2 + u3 = 6; u3 = 4
u3 + v2 = 5; 4 + v2 = 5; v2 = 1
u4 + v2 = 4; 1 + u4 = 4; u4 = 3
u4 + v3 = 3; 3 + v3 = 3; v3 = 0
u5 + v2 = 3; 1 + u5 = 3; u5 = 2
u5 + v5 = 1; 2 + v5 = 1; v5 = -1
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(3;1): 4 + 1 > 3; ?31 = 4 + 1 - 3 = 2
Выбираем максимальную оценку свободной клетки (3;1): 3
Цикл приведен в таблице (3,1 > 3,4 > 1,4 > 1,1).
|
v1=-1 |
v2=1 |
v3=0 |
v4=2 |
v5=-1 |
|||
|
u1=0 |
1 |
7 |
12 |
2 200 |
5 |
200 |
|
|
u2=3 |
2 100 [-] |
3 [+] |
8 |
4 |
7 |
100 |
|
|
u3=4 |
3 100 [+] |
5 100 [-] |
4 |
6 0 |
9 |
200 |
|
|
u4=3 |
4 |
4 100 |
3 100 |
8 |
2 |
200 |
|
|
u5=2 |
5 |
3 200 |
7 |
10 |
1 100 |
300 |
|
|
200 |
400 |
100 |
200 |
100 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v4 = 2; 0 + v4 = 2; v4 = 2
u3 + v4 = 6; 2 + u3 = 6; u3 = 4
u3 + v1 = 3; 4 + v1 = 3; v1 = -1
u2 + v1 = 2; -1 + u2 = 2; u2 = 3
u3 + v2 = 5; 4 + v2 = 5; v2 = 1
u4 + v2 = 4; 1 + u4 = 4; u4 = 3
u4 + v3 = 3; 3 + v3 = 3; v3 = 0
u5 + v2 = 3; 1 + u5 = 3; u5 = 2
u5 + v5 = 1; 2 + v5 = 1; v5 = -1
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;2): 3 + 1 > 3; ?22 = 3 + 1 - 3 = 1
(2;4): 3 + 2 > 4; ?24 = 3 + 2 - 4 = 1
max(1,1) = 1
Выбираем максимальную оценку свободной клетки (2;2): 3
Цикл приведен в таблице (2,2 > 2,1 > 3,1 > 3,2).
|
v1=-1 |
v2=1 |
v3=0 |
v4=2 |
v5=-1 |
|||
|
u1=0 |
1 |
7 |
12 |
2 200 |
5 |
200 |
|
|
u2=2 |
2 |
3 100 |
8 |
4 |
7 |
100 |
|
|
u3=4 |
3 200 |
5 0 |
4 |
6 0 |
9 |
200 |
|
|
u4=3 |
4 |
4 100 |
3 100 |
8 |
2 |
200 |
|
|
u5=2 |
5 |
3 200 |
7 |
10 |
1 100 |
300 |
|
|
200 |
400 |
100 |
200 |
100 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v4 = 2; 0 + v4 = 2; v4 = 2
u3 + v4 = 6; 2 + u3 = 6; u3 = 4
u3 + v1 = 3; 4 + v1 = 3; v1 = -1
u3 + v2 = 5; 4 + v2 = 5; v2 = 1
u2 + v2 = 3; 1 + u2 = 3; u2 = 2
u4 + v2 = 4; 1 + u4 = 4; u4 = 3
u4 + v3 = 3; 3 + v3 = 3; v3 = 0
u5 + v2 = 3; 1 + u5 = 3; u5 = 2
u5 + v5 = 1; 2 + v5 = 1; v5 = -1
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ? cij.
Минимальные затраты составят: F(x) = 2*200 + 3*100 + 3*200 + 4*100 + 3*100 + 3*200 + 1*100 = 2700
Размещено на Allbest.ru
Подобные документы
Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.
курсовая работа [100,0 K], добавлен 31.10.2014Нахождение минимума целевой функции для системы ограничений, заданной многоугольником. Графическое решение задачи линейного программирования. Решение задачи линейного программирования с использованием таблицы и методом отыскания допустимого решения.
курсовая работа [511,9 K], добавлен 20.07.2012Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Практические навыки моделирования задач линейного программирования и их решения графическим и симплекс-методом с использованием прикладной программы SIMC. Моделирование транспортных задач и их решение методом потенциалов с помощью программы TRAN2.
контрольная работа [199,8 K], добавлен 15.06.2009Обзор алгоритмов методов решения задач линейного программирования. Разработка алгоритма табличного симплекс-метода. Составление плана производства, при котором будет достигнута максимальная прибыль при продажах. Построение математической модели задачи.
курсовая работа [266,4 K], добавлен 21.11.2013Решение общей задачи линейного программирования симплексным методом, графическое построение целевой функции. Его проверка с помощью встроенной функции "Поиск решения" MS Excel. Определение плана перевозок при наименьших суммарных транспортных затрат.
контрольная работа [362,3 K], добавлен 03.11.2011Широкое применение вычислительной техники как в общей математике, так и в одном из её разделов – математических методах. Ознакомление с решением задач линейного программирования симплекс-методом и графически. Составлена программа на языке Delphi.
курсовая работа [57,1 K], добавлен 04.05.2010Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.
контрольная работа [2,0 M], добавлен 02.05.2012