рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

П.2.2. Решение задач линейного программирования

П.2.2. Решение задач линейного программирования - Лекция, раздел Программирование, Задачи линейного программирования Порядок Решения Зада Лп С Помощью Qsb Рассмотрим На Примере П.2.1. Подготовьт...

Порядок решения зада ЛП с помощью QSB рассмотрим на примере П.2.1. Подготовьте ЭММ задачи для решения на ЭВМ:

В нашей задаче: ЦФ на максимум, 4 переменных и 7 ограничений. Условия неотрицательности переменных (т.е., х2 ³ 0) заданы по умолчанию.

Выберите опцию Линейное программирование в главном меню системы. На экране появится функциональное меню:

Добро пожаловать в линейное программирование! Варианты работы с LP: Если вы работаете с системой впервые, то выберите опцию 1.
Опция Функция Помощь по LP Ввод новой задачи Чтение задачи с диска Просмотр/Печать исходных данных Решение задачи Запись задачи на диск Изменение задачи Просмотр/Печать итогового решения Возврат в главное меню Выход из QSB

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

Введите название задачи (до 6 символов)? prim1

Наберите имя задачи, длиной не более 6 символов, например, prim1 ,и нажмите Enter . При нажатии Enter автоматически происходит возврат в функциональное меню.

Вверху экрана появятся требования, которые необходимо соблюдать при вводе исходных данных (способы представления чисел, знаки отношения в неравенствах, клавиши перемещения курсора и др.); а внизу – вопросы о задаче:

Критерий на максимум (1) или минимум (2)? (Введите 1 или 2) <1> Сколько переменных в вашей задаче? (введите число <=40) <4> Сколько ограничений в вашей задаче? (введите число <=40) <7> Хотите использовать заданные имена переменных (Х1, Х2,...,Хn) (Y/N)? <y>

Ответьте на вопросы. Варианты ответов показаны выше (ЦФ на максимум, 4 переменных и 7 ограничений, будем использовать заданные имена переменных – Х1, Х2,...,Хn). Переход от предыдущей строки к последующей осуществляется нажатием Enter , обратный переход – клавишей Backspace .

Если при вводе не было ошибок, то по окончании нажмите клавишу

Spacebar для корректировки введённой информации – любую другую клавишу.

На экране появится шаблон ЭММ (ЦФ и ограничения) со свободными позициями для ввода коэффициентов. Заполните шаблон, при необходимости поменяйте знаки (<=, >=, =):

 

Max 60______ X1 70______X2 120_______X3 130______X4 Ограничен. 1) 1_____Х1 2_____Х2 3_____Х3 4_____Х4 £ 40_____ 2) 6_____Х1 5_____Х2 4_____Х3 3_____Х4 £ 110____ 3) 4_____Х1 6_____Х2 8_____Х3 12____Х4 £ 100____ 4) 1_____Х1 ______Х2 ______Х3 ______Х4 >=1_____ 5) 1_____Х1 ______Х2 ______Х3 ______Х4 £ 12_____ 6) ______Х1 ______Х2 1_____Х3 ______Х4 >=2_____ 7) ______Х1 ______Х2 ______Х3 1_____Х4 = 3______

После нажатия клавиши Spacebar на экране появится функциональное меню. В функциональном меню выберите опцию 6 – Запись задачи на диск. В верхней части экрана появится запрос об имени файла, в котором будут храниться исходные данные задачи.

Наберите имя файла (например, такое же как и имя задачи, т.е. prim1 ) и нажмите Enter . Для просмотра существующих файлов введите имя диска и нажмите Enter . При нажатии Enter без ввода имени файла осуществляется автоматический возврат в функциональное меню.

Если файла нет на диске, то выводится сообщение «Задача записана. Для продолжения любая клавиша.». Если файл с таким именем существует, то требуется подтверждение о замене его содержимого (Y) или отмене записи задачи (N): «Этот файл уже существует. Заменить его (Y/N)?» Введите Y или N и нажмите Enter . На экране появится функциональное меню.

В функциональном меню выберите опцию 3 – Чтение задачи с диска. В верхней части экрана появится запрос об имени файла, в котором хранятся исходные данные задачи.

Выберите имя файла prim1 и нажмите Enter . Для просмотра существующих файлов введите имя диска и нажмите Enter . При нажатии Enter без ввода имени файла осуществляется автоматический возврат в функциональное меню.

Если файла нет на диске, то выводится сообщение: «Нет такого файла. Повторите ввод». Если файл с таким именем существует, но в нём хранятся данные не задачи ЛП, то выводится сообщение «В этом файле нет задачи линейного программирования». И в том, и в другом случае необходимо повторить ввод имени файла. Если задача прочитана успешно, то выводится сообщение «Задача прочитана. Для продолжения любая клавиша». После нажатия любой клавиши на экране появится функциональное меню.

В функциональном меню выберите опцию 4 – Просмотр/Печать исходных данных. Если задача не была ведена или прочитана с диска, то будет выдано сообщение: «Задача не введена. Для продолжения любая клавиша», и после нажатия любой клавиши на экране появится функциональное меню; в противном случае – в верхней строке экрана появится запрос о необходимости вывода данных на принтер.

Убедитесь, что принтер готов к работе, введите символ Y (если распечатка не требуется, то – символ n ) и нажмите Enter . На экран (и принтер, если задано) будет выведено описание исходных данных задачи.

В задаче большой размерности исходные данные могут занимать несколько экранных страниц. Перемещение к следующей странице осуществляется нажатием клавиши / , к предыдущей странице – Esc . Для выхода в функциональное меню нажмите клавишу Spacebar после окончания просмотра.

В функциональном меню выберите опцию 5 – Решение задачи. На экране появится меню опции <Решение>:

Меню опции <Решение>
пункт 1---- Решение и просмотр начальной таблицы 2---- Решение и просмотр итоговой таблицы 3---- Решение и просмотр начальной и итоговой таблиц 4---- Решение и просмотр всех таблиц 5---- Решение без просмотра таблиц 6---- Возврат в функциональное меню

Выбор опции 6 обеспечивает возврат в функциональное меню без решения задачи. При выборе остальных опций задача будет решена. При этом для задач небольшой размерности доступны все режимы, а для больших задач – только опции 4-5. С целью усвоения алгоритма симплекс-метода начинающему пользователю рекомендуется выбирать опцию 4, обеспечивающую просмотр процесса решения по шагам.

Выберите опцию 4---- Решение и просмотр всех таблиц. На экране появится информация по каждой итерации, причём для больших задач (наш пример) выдаётся только номер итерации, текущее значение ЦФ, вводимые и выводимые из базиса вектора:

итерация: 1 Новая цф(Мах.)=390+(–3BigM) Вводим: Х4 значение = 3 Выводим: А7 Стр 7

Для небольших задач информация оформлена в виде симплекс-таблицы:

Базис С( j) X1 X2 S1 A1 S2 B( j) B(j) A(i j)
2.000 3.000 –M
A1 S2 –M 2.000 1.000 1.000 5.000 –1.00 1.000 1.000 5.000 20.00 2.500 20.00
C( j)–Z( j)*BigM   2.000 2.000 3.000 1.000 –1.00 –5.00  
Текущее значение целевой функции (Мах.)=0+(–5BigM) <подсвеченные переменные вводим или выводи из базиса> Вводим: Х1 Выводим: А1

В первой колонке указываются имена базисных переменных (естественные переменные обозначаются Х1, Х2,..., или как Вы их обозначили; дополнительные – S1, S2,...; искусственные – А1, А2,...).

Во второй колонке находятся коэффициенты ЦФ, соответствующие базисным переменным.

В заголовках следующих пяти колонок указаны имена переменных и коэффициенты ЦФ (строкой ниже). В колонках 3 и 4 находятся коэффициенты матрицы ограничений модели, а в колонках 5-7 – базисные вектора, образованные путём введения в систему дополнительных и искусственных переменных.

В 8 колонке – столбец свободных членов.

В 9 колонку (кроме начальной таблицы, в которой в 9 колонке помещены нули) заносятся отношения правых частей ограничений к соответствующим координатам вектора, вводимого в базис. Эти отношения необходимы для определения вектора, выводимого из базиса. Из базиса выводится вектор, имеющий наименьшее отношение. Деление на ноль в последней колонке обозначается символом Inf.

В двух последних строках таблицы рассчитываются относительные оценки (колонки 3-7) и в 8 колонке помещается значение ЦФ при данном базисном плане, причём в последней строке считаются оценки и значение ЦФ исходной задачи, а в последней строке – расширенной задачи, полученной путём введения искусственных переменных.

ЦФ расширенной задачи определяется следующим образом: maxL = =, где M(BigM) – достаточно большое положительное число.

Оценки считаются по формуле , где s - множество индексов базисных векторов, s = {1,2,...,m}; C( j) – коэффициенты ЦФ; x(i,j) – коэффициенты разложения векторов матрицы ограничений по единичному базису (i = 1...m; j = 1...n+m). Признаком оптимальности базисного допустимого плана служит наличие неположительных двойственных оценок.

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

Ниже таблицы выдаётся текущее значение ЦФ для данной итерации и указываются имена вводимой в базис и выводимой из базиса переменных. В таблице эти переменные выделены цветом. Под последней симплекс таблицей показано значение ЦФ, вычисленное на оптимальном плане.

Переход от одной итерации к другой осуществляется нажатием любой клавиши, кроме G , при нажатии которой вычислительный процесс пойдёт без остановки до конца.

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

Если найден оптимальный план, то после просмотра процесса решения, согласно выбранному режиму (1-4) или без просмотра итераций (5) система выдаст сообщение «Найдено оптимальное решение. Для продолжения лбая клавиша» и после нажатия любой клавиши выведет меню способов представления полученного решения задачи:

Меню опции <Просмотр/Печать итогового решения> prim1 Варианты работы для просмотра/печати итогового решения Для печати итогового решения подготовьте принтер
пункт 1---- Просмотр итогового решения 2---- просмотр решения и анализ чувствительности 3---- просмотр/печать решения 4---- просмотр/печать решения и анализ чувствительности 5---- Возврат в функциональное меню

Опция 5 позволяет вернуться в функциональное меню без просмотра результатов. Опции 1-4 обеспечивают вывод на экран (а 3-4 – и на принтер) итогового решения и результатов анализа чувствительности коэффициентов ЦФ и коэффициентов правой части ограничений. Аналогичные функции предлагаются в пункте 8 функционального меню.

Выберите опцию 2 – просмотр решения и анализ чувствительности. На экране появится таблица с результатами решения задачи:

итоговые результаты prim1 Стр.: 1
перемен. No. имена Решение Дв. оц. перемен. No. имена Решение Дв. оц.
1 Х1 2 Х2 3 Х3 4 Х4 5 S1 6 S2 7 S3 8 S4 1.0000 0.0000 7.5000 3.0000 4.5000 65.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 15.0000 0.0000 9 A4 10 S5 11 S6 12 A6 13 S7 14 A7 15 A8 0.0000 11.0000 0.0000 0.0000 5.5000 0.0000 0.0000 0.0000 0.0000 20.0000 –20.0000 0.0000 0.0000 –50.0000
Maximum значение ц.ф.= 1350 (из множества реш.) итерац. = 5  

После 5 итераций получен оптимальный план задачи Х*=(1; 0; 7,5; 3). Прибыль от реализации продукции составит 1350 д.е. Пользуясь этой таблицей, можно начать послеоптимизационный анализ задачи, основанный на двойственных оценках (колонки 3 и 6), а именно определить степень дефицитности ресурсов, установить, как изменится значение ЦФ при изменении запасов ресурсов на единицу. Финансы оказались лимитирующим ресурсом (S3=0, двойственная оценка положительна), остальные ресурсы – избыточные. Увеличение финансов приведёт к увеличению прибыли, а рост материальных и трудовых ресурсов – нет. Более подробный анализ решения производится автоматически в двух последующих таблицах.

После нажатия любой клавиши на экране появится таблица, содержащая анализ чувствительности коэффициентов ЦФ к изменению исходных данных:

Анализ чувствительности коэффициентов ц.ф. Стр.: 1
С(j) MinС(j) исходное Max С(j) C(j) Min С(j) исходное Max С(j)
C(1) C(2) –бескон –бескон 60.0000 70.0000 60.0000 90.0000 С(3) С(4) 120.0000 –бескон 120.0000 130.0000 +бескон +бескон

Здесь для каждого коэффициента ЦФ указано его исходное значение, а также нижняя и верхняя граница возможного его изменения с сохранением оптимального плана (т.е., цена П2 может изменяться в интервале [–¥, 90] без изменения оптимального плана).

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

Анализ чувствительности правой части Стр.: 1
B(j) MinB(i) исходное MaxB(i) B(j) MinB(i) исходное MaxB(i)
В(1) В(2) В(3) В(4) 35.5000 45.0000 56.0000 0.0000 40.0000 110.0000 100.0000 1.0000 +бескон +бескон 112.0000 12.0000 В(5) В(6) В(7) В(8) 1.0000 0.0000 –бескон 0.0000 12.0000 0.0000 2.0000 3.0000 +бескон 7.3333 7.5000 6.6667

Здесь для каждого вида ресурса указано его исходное значение, а также нижняя и верхняя граница возможного изменения запасов ресурсов с сохранением структуры оптимального плана (т.е., при изменении запаса третьего ресурса в пределах [56; 112] набор базисных переменных останется неизменным). Проверим данное утверждение, максимально изменив величину запаса третьего ресурса со 100 до 112.

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

 

 

Меню опции <Изменение > prim1
пункт 1---- изменение коэффициентов задачи 2---- изменение ограничения 3---- плюс 1 ограничен. 4---- минус 1 ограничение 5---- плюс переменная 6---- минус переменная 7---- Просмотр/Печать исходных данных 8---- Возврат в функциональное меню

Работа с опциями 1-2 аналогична вводу данных новой задачи. В первом случае предоставляется возможность корректировки коэффициентов задачи, начиная с первого ограничения, а во втором – с заданного пользователем. Опции 3 и 4предназначены для добавления и удаления одного ограничения. Опции 5 и 6 – для добавления и удаления одной переменной. Добавление переменной предполагает ввод её имени и значений коэффициентов ЦФ и ограничений.

Выберите опцию 2 – изменение ограничения. На экране появится запрос (который выдаётся каждый раз при выборе опций 1 –6) на ввод названия задачи.

Нажмите Enter , таким образом, все изменения будут производиться в текущей задаче. Далее появится запрос на ввод номера ограничения.

Наберите на клавиатуре номер ограничения ( 3 ) и нажмите Enter . На экране появится ЭММ задачи (с третьего ограничения).

Переместите курсов к цифре 100 и введите 112 . Для быстрого окончания корректировки нажмите дважды клавишу / .

В появившемся меню выберите опцию 8 – Возврат в функциональное меню.

Решите задачу. Ответ: Х*=(1; 0; 9; 3), L = 1530. Структура оптимального плана не изменилась.

Для окончания работы в функциональном меню выберите опцию 0 – Выход из QSB.

– Конец работы –

Эта тема принадлежит разделу:

Задачи линейного программирования

На сайте allrefs.net читайте: - закрепление теоретических знаний, получаемых студентами на лекционных и самостоятельных занятиях по решению задач линейного программирования;...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: П.2.2. Решение задач линейного программирования

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Общая характеристика задач подготовки и принятия решений в сложных технико-экономических системах
Важнейшая особенность современной научно-технической революции состоит в том, что по мере её развития всё большее значение приобретает учёт факторов сложности технико-экономических систем и комплек

Постановка задачи линейного программирования
При постановке и исследовании задач линейного программирования (ЛП) будем основываться на материалах учебного пособия [10]. Значительная часть задач принятия решения – это задачи р

ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Пример 2.1. Пусть требуется определить план выпуска четырёх видов продукции П1, П2, П3, П4, для изготовления которых необходимы ресу

ПРОВЕРКА СБАЛАНСИРОВАННОСТИ ПЛАНОВ
Представьте себе такую ситуацию. Директор завода вызывает к себе начальника цеха и говорит ему: «Надо сделать 20 болтов, но металл тебе никто не даст». Очевидно, такого быть не может. Все известно,

ТРЕБОВАНИЯ СОВМЕСТНОСТИ УСЛОВИЙ
Вспомним некоторые вопросы из алгебры. Рассмотрим неравенство а´х £ b. Если от неравенства мы хотим перейти к уравнению, то введём дополнительную переменну

ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Вспомним построение линейных зависимостей. Начнём с уравнений. Линейное уравнение с двумя переме

ИДЕЯ СИМПЛЕКС-МЕТОДА
  Пример 2.3. Рассмотрим задачу (табл.2.5) оптимизации плана производства с целью получения максимальной прибыли .   Таблица

Правила составления симплекс-таблиц
Таблица 2.6 Базис Свободные члены Свободные переменные х1 х2

ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Каждой задаче ЛП можно некоторым образом сопоставить другую задачу ЛП, называемую двойственной по отношению к исходной (прямой): Прямая задача (ПЗ)

П.2.3. Решение задач целочисленного программирования
Порядок решения задач ЦП с помощью QSB рассмотрим на примере. Подготовьте ЭММ задачи для решения на ЭВМ, исключив условия неотрицательности переменных:

П.2.4. Решение транспортной задачи
Порядок решения транспортных задач с помощью QSB рассмотрим на следующем примере. Пример. Требуется составить такой план прикрепления трёх потребителей к трём поставщи

П.2.5. Решение задачи о назначениях
Порядок решения задачи о назначениях с помощью QSB рассмотрим на примере. Подготовьте исходные данные задачи для решения на ЭВМ: Кандидаты Затраты времени по ра

П.2.8. Решение задач динамического программирования
Порядок решения сетевых задач с помощью QSB рассмотрим на следующем примере. Подготовьте исходные данные задачи для решения на ЭВМ: определите количество этапов в задаче (4 задачи), тип за

П.2.9. Решение вероятностных моделей
Порядок решения вероятностных моделей с помощью QSB рассмотрим на следующем примере. Выполнить анализ платёжной матрицы .

Поиск оптимальных решений задач линейного программирования с использованием программных средств excel 7.0
(Руководство пользователя) Решение задач линейного программирования с использованием Excel 7.0 осуществляется с помощью инструментального средства Поиск решения

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги