Решение задач симплекс-методом

Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 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

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.