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

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

Министерство сельского хозяйства Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Государственный аграрный университет Северного Зауралья»

Университет дистанционного образования

Кафедра: Экономика математических методов и вычислительной техники

КОНТРОЛЬНАЯ РАБОТА

По дисциплине: Математическое моделирование

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

Студента 3 курса

ЭЗБ-31 группы

Кандыба Н.Н.

Преподаватель:

Селюкова Г.П.

Тюмень 2015

Содержание

Введение

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

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

Список литературы

Введение

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

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

экономический линейный симплексный переменная

Постановка задачи

Оптимизировать структуру посевных площадей. Необходимо посеять пшеницу и посадить картофель. Площадь пашни составляет 1000 га, трудовые ресурсы - 2000 чел. - дн., планируется произвести не менее 800 т. пшеницы. Урожайность пшеницы 2 т/га, затраты труда на 1 га составляют: для пшеницы 1 чел. - дн, для картофеля - 5 чел. - дн. Прибыль от продажи пшеницы - 100 руб/га, картофеля - 250 руб/га.

Критерий оптимальности - максимум прибыли от продажи пшеницы и картофеля.

Развернутая экономика - математическая модель

Система переменных:

х1 - площадь пшеницы, га

х2 - площадь картофеля, га

Система ограничений:

1. По площади пашни, га: х1+ х2 ? 1000

2. По плану производства пшеницы, т: 2х1 ? 800

3. По трудовым ресурсам, чел. - дн.: х1 + 5х2 ? 2000

Целевая функции - максимум прибыли, руб.:

F = 100х1 + 250х2 > max

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

Точка А: х1 = 400 х2 = 0 F = 40000

Точка D: х1 = 1000 х2 = 0 F = 100000

Точка B: х1 = 4000 х2 = 350 F = 115000

Точка C: х1 = 750 х2 = 250 F = 137500

Оптимальное решение будет находится в точки С, то есть под пшеницу необходимо отвести 750 га. пашни, под картофель 250 га.

Рис. 1. Графический метод решения задачи линейного программирования

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

Алгоритм симплексного метода

1. На основе числовой модели строится первая симплексная таблица.

2. Решение проверяется на допустимость и оптимальность, если оно:

· допустимо и оптимально - решение найдено;

· не допустимо - решения нет;

· допустимо, но не оптимально - переход к п.3.

3. Переход к следующей симплексной таблице.

4. Переход к пункту 2.

Построение 1-й симплексной таблицы

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

Полученная система уравнений записывается по-новому, а именно решается относительно дополнительных переменных:

Новая запись легко оформляется в виде таблицы (табл.2), получившая название первой симплексной таблицы.

Переменные, которые находятся в первой строке симплексной таблицы (х₁, х₂, х₃ и х₄) называются свободными и их значения равны нулю. Переменные, которые находятся в первом столбце таблицы (y_1, y₂ и y₃) называются базисными и их значения находятся в столбце свободных членов: у₁ = 16, у₂ = 110 и у₃ = 100.

2.Первая симплексная таблица

Проверка на допустимость и оптимальность

Математиками доказано, что по правилу 1 можно определить допустимость решения, а по правилу 2 - его оптимальность.

Правило 1: Если все элементы столбца свободных членов (без учета значения целевой функции) положительны, то решение допустимо.

В рассматриваемой задаче все элементы (16, 110 и 100) положительны, следовательно, решение допустимо.

Правило 2: Если все элементы строки целевой функции (без учета значения целевой функции) имеют одинаковый знак, то решение оптимально: а) если знак «-», то оптимально по минимуму; б) если знак «+», то решение оптимально по максимуму.

В рассматриваемой задаче все элементы имеют знак «-», следовательно решение оптимально по минимуму, но задача должна быть решена на максимум. Вывод: решение допустимо, но не оптимально.

Алгоритм перехода к следующей симплексной таблице

1. Определяется разрешающий столбец - по максимальному значению (по абсолютной величине) элемента строки ЦФ (без учета ЦФ): Столбец Х₄ будет разрешающим, так как ¦- 130¦максимальная величина

2. Рассчитывается дополнительный столбец по формуле: элемент столбца свободных членов разделить на соответствующий элемент разрешающего столбца :

16/1=16, 110/3=37, 100/13=8

3. Определяется разрешающая строка по минимальной положительной величине дополнительного столбца:

Строка у₃ будет разрешающей, так как 8 - минимальная величина.

4. На пересечении разрешающих столбца и строки находится разрешающий элемент - цифра 13.

5. Копируется структура первой симплексной таблицы, в которой переменные разрешающих столбца и строки меняются местами (табл.3):

3.Вторая симплексная таблица

Экономический смысл такого обмена заключается в том, что предлагается производить 4-ю продукцию (как самую прибыльную), при этом полностью использовать финансы, так как Х₄ будет базисной, то есть отличной от нуля, а У₃ - свободной, то есть равной нулю.

6. Во второй симплексной таблице рассчитываются все элементы строки, соответствующей разрешающей (строка Х₄), по формуле: элемент разделить на разрешающий элемент:

100/13=8, 4/13=0,3, 6/13=0,5, 10/13=0,8, 13/13=1

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

0-(-130)*100/13=1000, 16-1*100/13=8, 110-3*100/13=87 и так далее.

Заполняется вторая симплексная таблица (табл.4):

4.Вторая симплексная таблица

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

5.Третья симплексная таблица

Решение допустимо, но не оптимально, требуется переход к следующей симплексной таблице (табл.6):

6.Четвертая симплексная таблица

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

Литература

1. Селюкова Г.П. Математическое моделирование производственно-экономических процессов и систем, Тюмень, ТГСХА, 2010. - 124 с.

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