Оптимальное решение модели. - Методика решения задачи целочисленного программирования
Рис. 1
Шаг 1. Исходную задачу 1 заносим в дерево задач.
В качестве исходного допустимого решения берем: x1=x2=x3=0. Соответствующее значение целевой функции берем в качестве нижней границы оптимального значения целевой функции:
Итерация 1.
Шаг 2. Выбираем единственную висячую вершину дерева задач - задачу 1.
Шаг 3. Решаем задачу линейного программирования, соответствующую задаче 1. Полученное решение имеет вид:
Шаг 4. Полученное оптимальное решение задачи линейного программирования не является целочисленным, поэтому переход на шаг 5.
Шаг 5. Выбираем переменную x3. Запишем в дерево задач две новые задачи - 2 и 3. Первая из них отличается от задачи 1 тем, что в ней добавляется новое ограничение x31, а вторая: x32 . Принимаем.
Итерация 2.
Шаг 2. Выбираем задачу 2.
Шаг 3. Находим оптимальное решение задачи линейного программирования, соответствующей задаче 2:
Шаг 4. Решение не является целочисленным, поэтому переходим на шаг 5.
Шаг 5. Выбираем переменную x2. Вносим в дерево задач задачу 4 с добавочным ограничением x10 и задачу 5 с ограничением x11. Принимаем Переходим на шаг 2.
Итерация 3
Шаг 2. Выбираем задачу 3.
Шаг 3. Система ограничений не совместна и задача линейного программирования, соответствующая задаче 3, не имеет допустимого решения. Принимаем. Переходим на шаг 2.
Итерация 4
Шаг 2. Выбираем задачу 4.
Шаг 3. Оптимальное решение задачи линейного программирования:
Шаг 4. Решение не является целочисленным, поэтому переходим на шаг 5.
Шаг 5. Выбираем переменную x2. Вносим в дерево задач задачу 6 с добавочным ограничением x20, задачу 7 с ограничением x21.
Итерация 5
Шаг 2. Выбираем задачу 6.
Шаг 3. Оптимальное решение задачи линейного программирования:
Шаг 4. Так как решение задачи линейного программирования целочисленно, то принимаем
Итерация 6
Шаг 2. Выбираем задачу 7.
Шаг 3. Задача линейного программирования не имеет допустимого решения. Принимаем
Итерация 7
Шаг 2. Выбираем задачу 5.
Шаг 3. Оптимальное решение задачи линейного программирования:
Шаг 4. Решение не является целочисленным, поэтому переходим на шаг 5.
Шаг 5. Выбираем переменную x3. Вносим в дерево задач задачу 8 с добавочным ограничением x30, задачу 9 с ограничением x31.
Итерация 8.
Шаг 2. Выбираем задачу 8.
Шаг 3. Оптимальное решение задачи линейного программирования:
Шаг 4. Решение не является целочисленным, поэтому переходим на шаг 5.
Шаг 5. Выбираем переменную x1. Вносим в дерево задач задачу 10 с добавочным ограничением x11, задачу 11 с ограничением x12.
Итерация 9.
Шаг 2. Выбираем задачу 9.
Шаг 3. Система ограничений не совместна и задача линейного программирования, соответствующая задаче 9, не имеет допустимого решения. Принимаем. Переходим на шаг 2.
Итерация 10.
Шаг 2. Выбираем задачу 10.
Шаг 3. Оптимальное решение задачи линейного программирования:
Шаг 4. Решение не является целочисленным, поэтому переходим на шаг 5.
Шаг 5. Выбираем переменную x2. Вносим в дерево задач задачу 12 с добавочным ограничением x20, задачу 13 с ограничением x21.
Итерация 11.
Шаг 2. Выбираем задачу 11.
Шаг 3. Система ограничений не совместна и задача линейного программирования, соответствующая задаче 11, не имеет допустимого решения. Принимаем. Переходим на шаг 2.
Итерация 12.
Шаг 2. Выбираем задачу 12.
Шаг 3. Оптимальное решение задачи линейного программирования:
Шаг 4. Так как решение задачи линейного программирования целочисленно, то принимаем
Итерация 13.
Шаг 2. Так как нерассмотренных ранее висячих вершин дерева задач больше нет, то выполнение алгоритма закончено: , так как. Оптимальное решение:
На основании полученного решения делаем вывод, что нефтеперерабатывающему заводу наиболее выгодно производить дизельное топливо. математический линейный целочисленность
Похожие статьи
-
Известно оптимальное решение X*=(0;0;1;1) задачи линейного программирования: Составьте двойственную задачу и найдите ее оптимальное решение по теореме...
-
Так как целевая функция не является линейной, то эта задача является задачей нелинейного программирования. Найдем ее решение, используя геометрическую...
-
Необходимость введения нового ограничения может возникнуть, например, когда первоначально для сокращения затрат машинного времени некоторые интуитивно...
-
Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...
-
Математическая модель задачи нелинейного программирования (ЗНП) (*) Для ЗНП в отличие от Задачи Линейного Программирования (ЗЛП) нет единого метода...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Основные понятия линейного программирования - Оптимальное программирование
Математические исследования отдельных экономических проблем, математическая формализация числового материала проводилась еще в XIX веке. При...
-
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой...
-
Изучение теоретических вопросов анализа чувствительности оптимального решения ЗЛП к вариациям некоторых параметров задачи и введению нового ограничения....
-
Пример транспортной задачи линейного программирования - Оптимальное программирование
Транспортная задача -- математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из...
-
Как известно решение задач симплексным методом применяется очень часто. Это связано с тем, что симплексный метод подходит для решения широкого круга...
-
Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....
-
Необходимо найти минимальное значение целевой функции F = 4x1+18x2 > min, при системе ограничений: X1+4x2?14(1) X1+6x2?15(2) X1+x2?5(3)...
-
Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...
-
Ограничение чувствительность задача программирование Вариации правых частей ограничений приводят к изменению области допустимых решений ЗЛП, в действии...
-
Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...
-
ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЗЛП) - Линейное программирование в экономике
Линейное программирование - направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между...
-
Введение - Оптимальное программирование
Линейный программирование транспортный задача Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при...
-
Линейное программирование, Общая задача линейного программирования - Экономико-математические методы
Термин "линейное программирование" впервые появился в 1951 г. в работах американских ученых (Дж. Данциг, Т. Купманс), а первые исследования по линейному...
-
Задачей линейного программирования (ЛП) называется задача минимизации или максимизации линейного функционала при линейных ограничениях. В литературе...
-
Введение - Решение оптимизационных экономических задач методами линейного программирования
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных...
-
Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....
-
Приведем систему ограничений к каноническому виду, для этого необходимо неравенства преобразовать в равенства, с добавлением дополнительных переменных....
-
Постановка задачи - Методика решения задачи целочисленного программирования
Сформулировать по заданному 24-хзначному числу модель целочисленного программирования вида: Где все параметры модели должны быть определены из следующих...
-
Теория оптимального программирования - Оптимальное программирование
Оптимальное программирование [optimal programming] -- применение в экономике методов математического программирования. Часто эти термины определяют как...
-
Области применения линейного программирования - Оптимальное программирование
Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий,...
-
Модели линейного программирования. Основные определения Еще одним классом задач экономико-математического моделирования являются задачи линейного...
-
Решение симплекс-методом с помощью симплекс-таблиц - Математические методы и модели в экономике
Определим оптимальный план выпуска продукции, решив задачу линейного программирования (ЗЛП). Для этого сначала приведем модель к каноническому виду...
-
Пусть имеется оптимизационная задача вида: (1) (2) (3) - задан(4) Здесь предполагается, что FJ(xJ,yJ)>0 для всех допустимых значений xJ,yJ. В этом случае...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
Несмотря на требование линейности функций критериев и ограничений, в рамки линейного программирования попадают многочисленные задачи распределения...
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
С целью формализации задачи введем необходимые обозначения: I - код изделия (i = 1,...,n); ХI - искомый объем выпуска годовой программы по i-му изделию;...
-
Большое число экономических и планово-производственных задач связано с распределением каких-либо, как правило, ограниченных ресурсов (сырья, рабочей...
-
Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции P1 P2 P3 P4 S1 4 1 1 1 3 S2 18 2 4 6 1 Прибыль от единицы...
-
Экономические задачи, сводящиеся к транспортной модели Транспортная модель используется для составления наиболее экономичного плана перевозок одного вида...
-
Экономико-математические методы и моделирование в землеустройстве позволяют решать большой круг задач, связанных с оптимизацией территориальной...
-
Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач
Постановка задачи. Пусть имеются N видов грузов с номерами. Единица груза j-го вида имеет все aJ. Если груз j-го вида берется в количестве xJ, то его...
-
Исследуем на экстремум функцию: 1. С помощью необходимого существования экстремума, т. е. из системы Найдем координаты стационарных (критических) точек:...
-
Вводим дополнительные ограничения в модель: А) продукция типа 1 выпускается только в том случае, если разрешен выпуск хотя бы одного типа продукции: 2 и...
Оптимальное решение модели. - Методика решения задачи целочисленного программирования