Условно-стандартная задача линейного программирования - Программирование, компьютеры и кибернетика задача

Главная

Программирование, компьютеры и кибернетика
Условно-стандартная задача линейного программирования

Оптимальный план прямой задачи графическим, симплекс-методом. План двойственной задачи по первой теореме двойственности. Определение целочисленного решения графическим, методом Гомори. Сравнение значений функций целочисленного и нецелочисленного решений.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

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


Условно- стандартная задача линейного программиров а ния
двойственный линейный программирование гомори
Необходимо выполнить в указанном порядке следующие задания.
1. Найти оптимальный план прямой задачи:
б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).
3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
4. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».
5. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, который был получен графическим методом (см. п. 1а).
6. Найти оптимальное целочисленное решение:
Сравнить значения функций целочисленного и нецелочисленного решений.
1. а) Найдем оптимальный план прямой задачи графическим методом
Решение: Изобразим на плоскости систему координат Ох 1 х 2 и построим граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе):
Область допустимых решений определяется множеством АВС D Е .
Для линий уровня 2 х 1 + 3 х 2 = h ( h - const) строим нормальный вектор . Перпендикулярно нормальному вектору построим одну из линий уровня (на рисунке она проходит через начало координат) Так как задача на максимум, то перемещаем линию уровня в направлении вектора до опорной прямой. В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L 6 и L 4 , т.е. через точку . Для определения координат точки А решаем систему уравнений:
Это и будет оптимальным решением данной задачи, которому соответствует максимальное значение целевой функции Z max :
1. б) Найдем оптимальный план прямой задачи симплекс-методом.
Приводим задачу к каноническому виду. Умножим первое ограничение на -1:
Для этого в левую часть ограничений-неравенств типа «» вводим по дополнительной переменной с коэффициентом (+1). В целевую функцию эти переменные входят с коэффициентом (0). Получаем
В 3-м ограничении отсутствует базисная переменная. Формулируем задачу искусственного базиса.
Полученную задачу будем решать модифицированным симплексным методом [1].
Сформулируем вспомогательную задачу, которая позволит исключить искусственные переменные из базиса и построить начальное опорное решение исходной канонической задачи.
Находим начальное опорное решение. Для этого свободные переменные приравниваем к нулю х 1 = х 2 = 0. Получаем опорное решение Х 1 = (0,0,19,28,0,47,19) с единичным базисом
Вычисляем оценки разложений векторов условий по базису опорного решения,
Оценки векторов, входящих в базис, всегда равны нулю. Опорное решение, коэффициенты разложений и оценки разложений векторов условий по базису опорного решения записываем в симплексную таблицу
Начальное опорное решение не является оптимальным, так как оценки 1 = 4, 2 = 1 для векторов А 1 и А 2 противоречат признаку оптимальности. Для оптимальности опорного решения в задаче на максимум требуется неотрицательность оценок для всех векторов условий.
Определим, введение, какого из двух векторов приведёт к большему приращению целевой функции. Приращения целевой функции найдём по формуле . Вычислим значения параметра 01 для первого и третьего столбцов по правилу Креко, получим 01 = 1 при l = 2 и 0 2 =4 при l =2. Находим приращение целевой функции при введении в базис первого вектора и второго вектора . Следовательно, для наиболее быстрого нахождении оптимального решения необходимо ввести в базис опорного решения вектор А 2 вместо вектора базиса А 7 .
Далее выполним преобразование Жордана-Гаусса с элементом х 2 2 = 1, получим второе опорное решение Х 2 :
Так как оценки неотрицательны, построенный план оптимален.
Искусственные переменные выведены из базиса.
Оптимальное решение вспомогательной задачи - это х7=х8=0, max G=0.
Попутно построен опорный план исходной канонической задачи:
Вернемся к ней. Используем последнюю симплекс-таблицу, из которой исключим переменную х7 и изменим цены базисных переменных, взяв их из заданной целевой функции. Получим
План необходимо улучшить. Вводим в базис х5, выводим х6
Проверим план на оптимальность. Оценки неотрицательны, план оптимален.
Ответ: max Z ( X ) = 20 1/7 при Х *= (0; 6 5/7; 45 6/7; 61 4/7; 2 5/7; 0).
2. Построим двойственную задачу к исходной. Так как исходная задача на максимизацию, то приведём все неравенства системы ограничений к виду «», для чего обе части 1-го и 3-го неравенств умножим на (1). Получим
Составим расширенную матрицу системы
Найдём матрицу , транспонированную к А
3. Найдем оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
Чтобы допустимые решения х, у пары двойственных задач были оптимальны, необходимо и достаточно, чтобы выполнялись соотношения, т.е. условия дополняющей нежесткости:
Так как прямая задача разрешима, то двойственная тоже имеет решение, и, в силу первой теоремы двойственности, . Найдем значения переменных.
Подставим найденное оптимальное решение Х *= (0; 6 5/7) в систему ограничений исходной задачи:
В силу условия 1 дополняющей нежесткости получаем: .
Получаем систему уравнений для нахождения оставшихся неизвестных:
Ответ: оптимальное решение двойственной задачи
4. Найдем оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи. Решению двойственной задачи соответствуют оценки переменных х 3 - х 6 ..
Проверим утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают», то есть то есть равенство выполняется.
5. Двойственную задачу решим симплекс-методом.
Запишем задачу в каноническом виде.
Перейдем к канонической задаче. Из левой части второго неравенства вычтем дополнительную переменную, к левой части первого неравенства прибавим, перейдем к задаче на максимум. Получим
Сформулируем задачу искусственного базиса
Сформулируем вспомогательную задачу искусственного базиса. Ее решение даст нам опорный план исходной канонической задачи (см. [1])
Решаем вспомогательную задачу симплекс-методом:
Оценки неотрицательны, следовательно, решение задачи искусственного базиса, т.е. , max (-G(y))=0. Параллельно построен начальный опорный план исходной канонической задачи: .
Исключим из рассмотрения искусственные переменные, перепишем последнюю таблицу, заменив в ней нулевые цены на цены переменных из исходной задачи.
Так как оценки неотрицательны, построенный план не требует дальнейшего улучшения.
Используя окончательную симплекс-таблицу двойственной задачи, найдем оптимальный план прямой задачи по первой теореме двойственности.
Решение исходной задачи (т.е. двойственной к двойственной) будет равно оценкам дополнительных переменных и , а максимум функции исходной задачи будет равен минимуму функции двойственной задачи:
Сравним результат с результатом, который был получен графическим методом (см. п. 1а).
Очевидно, что результаты совпадают.
6. а) Найдем оптимальное целочисленное решение графическим методом.
Для этого используем рисунок п. 1. а), дополнив его построением прямых линий х=с и у=с. Проведем линии уровня (пунктир) через точки пересечения этих прямых линий, расположенные в области допустимых решений и отстоящие как можно дальше в направлении градиента целевой функции.
Точка максимума с целочисленными координатами - это, очевидно, F (2; 5). Максимальное значение функции в этом случае равно Z=2*2+3*5= 19.
6. б) Найдем оптимальное целочисленное решение методом Гомори.
Для этого используем последнюю таблицу п. 1 б)
Построим отсечение дробной части решения. Для этого построим дополнительное ограничение и запишем его коэффициенты в последнюю (перед k ) строку.
Построим отсечение дробной части по переменной х 4 .
В новую строку запишем дробную часть соответствующего элемента строки х 4 , взятую с противоположным знаком.
Оценки переменных остались неизменными. Но в столбце свободных членов появился отрицательный элемент. Следовательно, выводим из базиса х 7 . Наименьшее отношение дает 4/5, поэтому вводим в базис х 6 .
Получено оптимальное, но нецелочисленное решение. Выполним отсечение дробной части по переменной х 2 . Дробные части чисел строки х 2 запишем в строку х 8 с отрицательными знаками. Введем в базис х 1 , выведем х 8 . Получим следующую таблицу:
Так как оценки k неотрицательны, а числа в столбце «b» целые, получено оптимальное целочисленное решение задачи: х 1 =2, х 2 =5, max Z= 19.
Сравним значения функций целочисленного и нецелочисленного решений: значение функции, полученное без условия целочисленности, больше: 20 1/7 > 19.
Реализация алгоритма Гомори на языке программирования Object Pascal при использовании среды разработки Borland Delphi 7. Рассмотрение основных способов компьютерного осуществления решения задач целочисленного программирования симплексным методом. курсовая работа [1,8 M], добавлен 28.03.2013
Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания. контрольная работа [2,0 M], добавлен 02.05.2012
Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность. курсовая работа [100,0 K], добавлен 31.10.2014
Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции. курсовая работа [1,1 M], добавлен 21.03.2012
Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели. курсовая работа [581,5 K], добавлен 13.10.2008
Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения. контрольная работа [118,5 K], добавлен 11.04.2012
Практические навыки моделирования задач линейного программирования и их решения графическим и симплекс-методом с использованием прикладной программы SIMC. Моделирование транспортных задач и их решение методом потенциалов с помощью программы TRAN2. контрольная работа [199,8 K], добавлен 15.06.2009
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Условно-стандартная задача линейного программирования задача. Программирование, компьютеры и кибернетика.
Реферат: Виды индукторов и создаваемых ими полей
Реферат: Доходы и расходы местных бюджетов
Курсовая работа по теме Проблемы и перспективы налогообложения субъектов малого бизнеса
Желчнокаменная Болезнь Курсовая Работа Заключение
Пример Дневника По Производственной Практике Юриста
Агрессивные Дети Курсовая
Контрольная Работа На Тему Введение Химия
Написать Реферат Про Бетховена
Доклад: Меланотении
Дипломная Работа На Тему Применение Условно-Досрочного Освобождения
Реферат: Внедрение систем экологического менеджмента, как средство повышения эффективности управления охраной окружающей среды на промышленном предприятии
Курсовая работа по теме Синтез суммирующего асинхронного счетчика
Носов Сочинение Егэ
Почему Для Философии Актуальны Проблемы Творчества Эссе
Білім Алу Эссе
Лекция: Поздние осложнения аденомэктомии. Скачать бесплатно и без регистрации
Контрольная работа по теме Розвиток програм підготовки соціальних працівників у США
Курсовая работа по теме Аудит амортизационных отчислений основных средств и нематериальных активов
Учебное пособие: Методические указания по выполнению дипломной работы для студентов всех форм обучения специальности 080102. 65 (060600)
Реферат На Тему Современный Писатель
Стволовые клетки - Медицина реферат
Основы физиологии крови (функции крови, состав крови, плазма крови, форменные элементы крови) - Медицина презентация
Правовые последствия гражданской войны севера и юга США - Государство и право реферат