Введение, Графический метод решения задач линейного программирования - Методы оптимальных решений

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

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

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

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

Оптимизировать структуру посевных площадей. Необходимо посеять пшеницу и посадить картофель. Площадь пашни составляет 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-й симплексной таблицы

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

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

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

Переменные, которые находятся в первой строке симплексной таблицы (х1, х2, х3 и х4) называются свободными и их значения равны нулю. Переменные, которые находятся в первом столбце таблицы (y1, Y2 И y3) называются базисными и их значения находятся в столбце свободных членов: у1 = 16, у2 = 110 и у3 = 100.

Похожие статьи




Введение, Графический метод решения задач линейного программирования - Методы оптимальных решений

Предыдущая | Следующая