Принципы решения некоторых задач математического программирования

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

Рубрика Математика
Вид контрольная работа
Язык русский
Дата добавления 27.11.2011
Размер файла 333,3 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Задача 1

;

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

1. Решить задачу графическим методом.

2. Решить задачу симплексным методом.

3. Построить для задачи двойственную.

4. Решить двойственную задачу с помощью первой основной теоремы теории двойственности.

5. Решить двойственную задачу с помощью второй основной теоремы теории двойственности.

Задача 2

j / i

1

2

3

4

1

1

2

2

1

50

2

2

2

1

2

70

3

1

2

1

3

30

40

25

60

25

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

2. Найти опорный план перевозок транспортной задачи методом северо-западного угла.

3. Найти опорный план перевозок транспортной задачи методом минимального элемента.

4. Решить методом потенциалов транспортную задачу дважды, используя найденные в пунктах 2 и 3 опорные планы перевозок.

Решение:

Задача №1:

1. Графический метод

Преобразуем задачу на минимум к задаче на максимум:

=

Основные ограничения задачи содержат 3 уравнения с 5-ю неотрицательными переменными. Так как число переменных n = 5 и число ограничений т = 3 отличаются на 2, то можно предположить, что эту задачу можно решить графическим методом. Соотношение n-m = 2 сохранится, если основные ограничения задачи линейно независимые.

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

Все вычисление проведём в таблице, используя метод полного исключения (Метод Жардана - Гаусса). ? - контрольная сумма.

X1

X2

X3

X4

X5

B

1

4

1

0

1

15

4

-3

-1

1

1

6

2

-4

-1

1

0

-3

-1

1

-1

-2

1

0

1

4

1

0

1

15

0

-19

-5

1

-3

-54

0

-12

-3

1

-2

-33

0

5

0

-2

2

15

1

4

1

0

1

15

0

-19

-5

1

-3

-54

0

7

2

0

1

21

0

-33

-10

0

-4

-93

1

-3

-1

0

0

-6

0

2

1

1

0

9

0

7

2

0

1

21

0

-5

-2

0

0

-9

-1/3

1

1/3

0

0

2

2/3

0

1/3

1

0

5

7/3

0

-1/3

0

1

7

-5/3

0

-1/3

0

0

1

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

Разрешив эту систему относительно базисных переменных , , и учитывая, что мы получим следующую задачу:

Эта задача содержит 2 переменных и её можно решить графическим методом. Запишем уравнения границ области, точки для их построения и укажем полуплоскости, определяемые неравенствами основных ограничений задачи

(1) (0; 6) (-6; 0)

(2) (0; 15) (7,5; 0)

(3) (0; - 21) (3; 0)

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

Область D - это точки 1-ой четверти. Вектор L в данном случае имеет вид L = (1,6; 0,3).

Строим прямую Z перпендикулярно вектору L. Таким образом, получаем пересечение перпендикуляра с прямыми 2) и 3), в результате чего получаем точку А. В соответствии в этим составляем систему уравнений. Решая систему уравнении: находим координаты этой точки.

А = (4; 7), подставим в целевую функцию получим следующие значения:

, , получим: .

2. Симплекс метод

Разделим переменные на базисные и свободные методом полного исключения (см. Графический метод), получим:

Составим таблицу итераций:

БАЗИС

С

A0

ВЕКТОРЫ

A1

A2

A3

A4

A5

A2

0

2

-1/3

1

1/3

0

0

A4

0

-5

2/3

0

1/3

1

0

A5

0

7

7/3

0

-1/3

0

1

?

1

-5/3

0

-1/3

0

1

2-я итерация

А2

0

3

0

1

1/21

0

1/7

А4

0

3

0

0

3/7

1

-2/7

А1

5/3

3

1

0

-1/7

0

5/7

?

6

0

0

-12/21

0

5/7

3-я итерация

А2

0

8/3

0

1

0

-1/9

11/63

А3

1/3

7

0

0

1

7/3

-2/3

А4

5/3

4

1

0

0

1/3

1/3

?

10

0

0

0

4/3

1/3

На первой итерации видим, что среди ? есть отрицательные - это значит что решение не оптимально. Вектор А1 выводим в базис, так как . Для того чтобы выбрать какой элемент мы будем выводить из базиса делаем следующее: элемент столбца делим на элемент столбца по принципу первый на первый, второй на второй. Из полученных результатов деления выбираем наименьшее положительное.

Из этого следует что выводим элемент . Далее пересчитываем таблицу по методу Жардано-Гаусса и получаем таблицу второй итерации.

Видим, что среди ? есть отрицательные - это значит что решение не оптимально. Вектор выводим в базис потому, что . По вышеизложенному принципу выбираем элемент для вывода из базиса. Выводим из базиса . Далее пересчитываем таблицу по методу Жардана-Гаусса и получаем таблицу третей итерации.

Видим, что среди ? нет отрицательных - это значит что решение оптимально.

3. Двойственная задачи

Любая задача математического программирования имеет обратную ей задачу, так называемую двойственную ей задачу, причем соблюдается условие: и на оборот.

Строим двойственную задачу по такому принципу: A [] - матрица задачи, тогда матрица обратной задачи будет, причем.

Разделим переменные на базисные и свободные методом полного исключения (см. Графический метод), получим:

Тогда двойственная этой задачи будет иметь вид:

4. Решение двойственной задачи с помощью первой основной теоремы теории двойственности

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

Теорема: Если одна из двойственных задач имеет оптимальное решение, то и двойственная ей задача имеет оптимальное решение, причем - эти задачи совпадают.

Из доказательства теоремы следует, что . Матрица решений получается перемножением матриц (вектор-строка коэффициентов в целевой функции при базисных переменных); (матрица обратная матрицы , составленная из векторов оптимального базиса, тоесть матрица на исходных векторах, но взятых из последней симплекс таблицы).

Решаем двойственную задачу с помощью симплексных таблиц (см. Симплекс метод).

БАЗИС

С

A0

ВЕКТОРЫ

A1

A2

A3

A4

A5

A2

0

2

-1/3

1

1/3

0

0

A4

0

-5

2/3

0

1/3

1

0

A5

0

7

7/3

0

-1/3

0

1

?

1

-5/3

0

-1/3

0

1

2-я итерация

А2

0

3

0

1

1/21

0

1/7

А4

0

3

0

0

3/7

1

-2/7

А1

5/3

3

1

0

-1/7

0

5/7

?

6

0

0

-12/21

0

5/7

3-я итерация

А2

0

8/3

0

1

0

-1/9

11/63

А3

1/3

7

0

0

1

7/3

-2/3

А4

5/3

4

1

0

0

1/3

1/3

?

10

0

0

0

4/3

1/3

Отсюда следует, что:

5. Решение двойственной задачи с помощью второй основной теоремы теории двойственности

Вторая теорема двойственности также позволяет решить двойственную задачу, используя решение первой задачи и используя ограничения.

Разделим переменные на базисные и свободные методом полного исключения (см. Графический метод) и возьмем точку А (см. Графический метод) получим:

А=(4; 7)

Отсюда следует, что необходимо искать и .

Решив, систему уравнений получим: .

Отсюда

Ответ: Максимальная прибыль будет равна 10.

Задача №2

1. Построение математической модели транспортной задачи

Транспортные задачи - это задачи в которых нужно решить проблему: доставку продукции от множества поставщиков к множеству потребителей с минимальными затратами на транспортировку.

Для решения этих задач нужно знать матрицу поставщиков , матрицу потребителей и матрицу перевозок . Матрица перевозок показывает стоимость перевозки от i поставщика к j потребителю.

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

Решение задачи будет определение количество товара, которое необходимо поставить от каждого поставщика к каждому потребителю.

Исходя из условий задачи получаем:

Матрица поставщиков имеет вид:

Матрица потребителей имеет вид:

Матрица перевозок имеет вид:

Система ограничений по поставки имеет вид:

Система ограничений по потреблению имеет вид:

Функция цели имеет вид:

2. Поиск опорного плана транспортной задачи методом северо-западного угла

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

i / j

40

25

60

25

50

1

40

2

10

2

1

70

2

2

15

1

55

2

30

1

2

1

5

3

25

Стоимость перевозок: L=40+20+30+55+5+75=225

3. Поиск опорного плана транспортной задачи методом минимального элемента

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

i / j

40

25

60

25

50

1

40

2

2

1

10

70

2

2

1

60

2

10

30

1

2

25

1

3

5

Стоимость перевозок: L=40+50+60+10+20+15=195

4. Решение транспортной задачи методом потенциалов

Введем для обозначения потенциалов буквы: для обозначения потенциала строки букву «U», обозначения потенциалов столбца букву «V». Возьмем опорный план, найденный в третьем пункте задачи, и заполним таблицу с учетом потенциалов. Причем для потенциалов будет выполняться условие: .

i / j

40

25

60

25

U

50

1

40

2

2

1

10

U1

70

2

2

1

60

2

10

U2

30

1

2

25

1

3

5

U3

V

V1

V2

V3

V4

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

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

Составляем косвенные стоимости () для пустых клеток по найденным потенциалам.

Определяем оценки (г) для пустых клеток по формуле: прямая минус косвенная стоимость.

Поскольку отрицательных оценок есть, то данный план не оптимален. Составляем новый план с другим позиционированием коэффициентов.

i / j

40

25

60

25

U

50

1

25

2

2

1

25

U1

70

2

2

10

1

60

2

U2

30

1

15

2

15

1

3

U3

V

V1

V2

V3

V4

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

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

Составляем косвенные стоимости () для пустых клеток по найденным потенциалам.

Определяем оценки (г) для пустых клеток по формуле: прямая минус косвенная стоимость.

Так как отрицательных оценок нет, то план перевозок оптимален. L=175

Ответ: Себестоимость перевозок равна L=175.

Размещено на Allbest.ru


Подобные документы

  • Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.

    задача [58,6 K], добавлен 16.02.2016

  • Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству.

    контрольная работа [23,5 K], добавлен 12.06.2011

  • Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.

    курсовая работа [219,4 K], добавлен 17.04.2013

  • Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.

    курсовая работа [118,7 K], добавлен 30.04.2011

  • Численные методы поиска безусловного экстремума. Задачи безусловной минимизации. Расчет минимума функции методом покоординатного спуска. Решение задач линейного программирования графическим и симплексным методом. Работа с программой MathCAD.

    курсовая работа [517,9 K], добавлен 30.04.2011

  • Двойственные задачи в линейном программировании. Симметричные и несимметричные двойственные задачи. Связь исходной и двойственной задач. Анализ моделируемой ситуации (моделируемого объекта). Реализация двойственности на Visual Basic for Application.

    курсовая работа [703,5 K], добавлен 14.10.2011

  • Формирование нижних и верхних оценок целевой функции. Алгоритм метода ветвей и границ, решение задач с его помощью. Решение задачи коммивояжера методом ветвей и границ. Математическая модель исследуемой задачи, принципы ее формирования и порядок решения.

    курсовая работа [153,2 K], добавлен 25.11.2011

  • Применение математических и вычислительных методов в планировании перевозок. Понятие и виды транспортных задач, способы их решения. Особенности постановки задачи по критерию времени. Решение транспортной задачи в Excel, настройка параметров решателя.

    курсовая работа [1,0 M], добавлен 12.01.2011

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

    контрольная работа [551,9 K], добавлен 27.08.2009

  • Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.

    курсовая работа [65,3 K], добавлен 30.11.2010

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