Введение, Графический метод решения задач линейного программирования - Методы оптимальных решений
Задача линейного программирования может быть решена графическим методом, достоинство которого в его простоте и наглядности, но существенным недостатком является то, что решаемая модель может содержать не более двух переменных. Этот метод имеет теоретическое значение, а на практике применяются аналитические методы, которых множество, но существует универсальный метод решения задач линейного программирования, который называется симплексным методом. Достоинство этого метода заключается в том, что можно решить задачу с любым количеством переменных, но потребуется большое количество вычислений.
Графический метод решения задач линейного программирования
Экономический линейный симплексный переменная
Постановка задачи
Оптимизировать структуру посевных площадей. Необходимо посеять пшеницу и посадить картофель. Площадь пашни составляет 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.
Построение 1-й симплексной таблицы
Числовая модель приводится каноническому виду, то есть к системе уравнений, с помощью дополнительных переменных - yI, которые обозначают недоиспользованные ресурсы.
Полученная система уравнений записывается по-новому, а именно решается относительно дополнительных переменных:
Новая запись легко оформляется в виде таблицы (табл.2), получившая название первой симплексной таблицы.
Переменные, которые находятся в первой строке симплексной таблицы (х1, х2, х3 и х4) называются свободными и их значения равны нулю. Переменные, которые находятся в первом столбце таблицы (y1, Y2 И y3) называются базисными и их значения находятся в столбце свободных членов: у1 = 16, у2 = 110 и у3 = 100.
Похожие статьи
-
При решении некоторых задач линейного программирования бывает необходимо получить целочисленное решение, которое находится методами целочисленного...
-
Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...
-
Нелинейное программирование - Методики решения задач линейного и нелинейного программирования
Задача математического программирования называется нелинейной, если нелинейны ограничения или целевая функция. Задачи нелинейного программирования бывают...
-
Основная задача линейного программирования: Найти неотрицательное решение системы ограничений обеспечивающее максимум (минимум) целевой функции. Чтобы...
-
Линейное программирование, Общая задача линейного программирования - Экономико-математические методы
Термин "линейное программирование" впервые появился в 1951 г. в работах американских ученых (Дж. Данциг, Т. Купманс), а первые исследования по линейному...
-
Оптимальное решение модели. - Методика решения задачи целочисленного программирования
Рис. 1 Шаг 1. Исходную задачу 1 заносим в дерево задач. В качестве исходного допустимого решения берем: x1=x2=x3=0. Соответствующее значение целевой...
-
Основные понятия линейного программирования - Оптимальное программирование
Математические исследования отдельных экономических проблем, математическая формализация числового материала проводилась еще в XIX веке. При...
-
Как известно решение задач симплексным методом применяется очень часто. Это связано с тем, что симплексный метод подходит для решения широкого круга...
-
Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Так как целевая функция не является линейной, то эта задача является задачей нелинейного программирования. Найдем ее решение, используя геометрическую...
-
Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....
-
Введение - Решение оптимизационных экономических задач методами линейного программирования
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных...
-
ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЗЛП) - Линейное программирование в экономике
Линейное программирование - направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между...
-
Области применения линейного программирования - Оптимальное программирование
Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий,...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
Необходимость введения нового ограничения может возникнуть, например, когда первоначально для сокращения затрат машинного времени некоторые интуитивно...
-
Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции P1 P2 P3 P4 S1 4 1 1 1 3 S2 18 2 4 6 1 Прибыль от единицы...
-
Математическая модель задачи нелинейного программирования (ЗНП) (*) Для ЗНП в отличие от Задачи Линейного Программирования (ЗЛП) нет единого метода...
-
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой...
-
Известно оптимальное решение X*=(0;0;1;1) задачи линейного программирования: Составьте двойственную задачу и найдите ее оптимальное решение по теореме...
-
Необходимо найти минимальное значение целевой функции F = 4x1+18x2 > min, при системе ограничений: X1+4x2?14(1) X1+6x2?15(2) X1+x2?5(3)...
-
Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач
Постановка задачи. Пусть имеются N видов грузов с номерами. Единица груза j-го вида имеет все aJ. Если груз j-го вида берется в количестве xJ, то его...
-
Введение - Оптимальное программирование
Линейный программирование транспортный задача Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
-
Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...
-
Изучение теоретических вопросов анализа чувствительности оптимального решения ЗЛП к вариациям некоторых параметров задачи и введению нового ограничения....
-
Экономико-математические методы и моделирование в землеустройстве позволяют решать большой круг задач, связанных с оптимизацией территориальной...
-
Приведем систему ограничений к каноническому виду, для этого необходимо неравенства преобразовать в равенства, с добавлением дополнительных переменных....
-
Решение задачи графическим методом - Математическое моделирование в менеджменте и маркетинге
Необходимо найти максимальное значение целевой функции L(x)= 2x1+2x2 > max, при системе ограничений: 6x1+8x2?48, (1) 8x1+11x2?88, (2)...
-
Большое число экономических и планово-производственных задач связано с распределением каких-либо, как правило, ограниченных ресурсов (сырья, рабочей...
-
Пример транспортной задачи линейного программирования - Оптимальное программирование
Транспортная задача -- математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из...
-
Динамическое программирование (ДП) - Методики решения задач линейного и нелинейного программирования
Динамическими называются задачи экономики, организации и управления, в которых необходимо распределять ресурсы на каждом этапе какого - либо промежутка...
-
Метод кусочно-линейной аппроксимации. В нашей задаче есть такая величина, как коэффициент увеличения затрат при нагрузке, который не использовался нами...
-
Теория оптимального программирования - Оптимальное программирование
Оптимальное программирование [optimal programming] -- применение в экономике методов математического программирования. Часто эти термины определяют как...
-
Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы
Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой...
-
Пусть имеется оптимизационная задача вида: (1) (2) (3) - задан(4) Здесь предполагается, что FJ(xJ,yJ)>0 для всех допустимых значений xJ,yJ. В этом случае...
-
Решение: Строим на плоскости х1Ох2 многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки...
-
Геометрическая интерпретация и графическое решение ЗЛП - Экономико-математические методы
Геометрическая интерпретация экономических задач дает возможность наглядно представить их структуру, выявить особенности и открывает пути исследования...
Введение, Графический метод решения задач линейного программирования - Методы оптимальных решений