Симплекс-метод — Информатика. Шпоры | iFREEstore

Симплекс-метод

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

Пусть система ограничений состоит лишь из уравнений

и требуется отыскать минимум линейной функции (7.81). Для отыскания произвольного опорного решения приведем (7.85) к виду, в котором некоторые r неизвестных выражены через остальные, а свободные члены неотрицательны (как это сделать - обсудим позднее):

Неизвестные x1, x2, ..., xr - базисные неизвестные, набор {x1, x2, ..., xr} называется базисом, а остальные неизвестные {xr+1, xr+2, ..., xn} - свободные. Подставляя (7.86) в (7.81), выразим функцию

f через свободные неизвестные: f = c0 + c'r+1xr+1 + c'хr+2 +…+ с'nxn.

Положим все свободные неизвестные равными нулю:

Полученное таким образом допустимое решение

отвечает базису x1, х2, ..., xr, т.е. является базисным решением. Допустим для определенности, что мы ищем минимум f. Теперь нужно отданного базиса перейти к другому с таким расчетом, чтобы значение линейной функции f при этом уменьшилось. Проследим идею симплекс-метода на примере.

-4318010160000Пример 1. Дана система ограничений

x1 – 3x2 + 5x3 – x4 = 2

x1 + x2 + x3 + x4 = 4

Требуется минимизировать линейную функцию f = х2 – x3. В качестве свободных переменных выберем х2 и х3. Тогда данная система ограничений преобразуется к виду

Таким образом, базисное решение (3, 0, 0, 1). Так как линейная функция уже записана в свободных неизвестных, то ее значение для данного базисного решения f = 0. Для уменьшения этого значения можно уменьшить x2 или увеличить x3. Но x2 в данном базисе равно нулю и потому его уменьшать нельзя. Попробуем увеличить x3. Первое из уравнений имеет ограничение x3 = 1 (из условия x1 ≥ 0), второе - не дает ограничений. Далее, берем x3 = 1, х2 не меняем и получаем новое допустимое решение (0, 0, 1, 3), для которого f = -1 - уменьшилось. Найдём базис, которому соответствует это решение (он состоит, очевидно, из переменных x3, x4). Переходим к новой сист.огранич.:

← Предыдущая
Страница 1
Следующая →

Файл

остальные шпоры.docx

остальные шпоры.docx
Размер: 591 Кб

.

Пожаловаться на материал

В информатике совокупность взаимосвязанных данных называется информационной структурой. Компьютерные сети. Языки программирования. Язык разметки HTML. ЭВМ. Информационная система

У нас самая большая информационная база в рунете, поэтому Вы всегда можете найти походите запросы

Искать ещё по теме...

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

Информатика. Шпоры

В информатике совокупность взаимосвязанных данных называется информационной структурой. Компьютерные сети. Языки программирования. Язык разметки HTML. ЭВМ. Информационная система

К данному материалу относятся разделы:

Табличные процессоры

Реляционные БД. Правила Кодда. Аномалии. Нормальные формы

Правил Кодда

Компьютерные сети

Базы данных. Классификация. Архитектура

Парадигмы программирования. Языки программирования. Системы программирования

Язык разметки HTML. Web-страницы. Создание

История развития ВТ

Поколения ЭВМ

Программное обеспечение ЭВМ

Информационная система (ИС)

SQL. Команды определения данных

Язык программирования Delphi

Основные принципы функционирования ЭВМ. Основные структурные элементы современного компьютера. Функции и характеристики

Динамическое программирование

SQL. Команды управления данными

Методы сортировки и поиска. Алгоритмы и программы

Симплекс-метод

Язык JAVA-Script

Исследование операций

Кодирование информации

Компьютерное моделирование в экологии

Машинно-ориентированные языки программирования. Арифметические команды и команды условного перехода в ассемблере

Компьютерное моделирование физических процессов

Массивы в ООП-языках. Примеры использования

Рекурсивно-логическое программирование. Пролог. Основные принципы работы с базами знаний

Работа со списками в Прологе

Основные концепции ООП

Похожие материалы:

Проблема историзма былин в работах В.Я. Проппа и Б.А. Рыбакова

Проблема историзма вызвала острые научные споры и дискуссии в советской фольклористике в связи с вопросом историзма былин.

Декоративно-прикладное искусство ДПИ.

Истоки, история и основные этапы становления и развития ДПИ. Технология изготовления «холодного» батика. Виды народного ДПИ. Его своеобразие и художественная ценность. Технология изготовления горячего батика.

Стоимость товарного знака, факторы на нее влияющие и методы оценки.

Товарный знак является своеобразной гарантией получения добавленной ценности, выгод, которые отсутствуют у товаров компаний-конкурентов.

Автомобільна промисловість

Автомобільна промисловість — галузь транспортного машинобудування, що виробляє моторизовані нерейкові транспортні засоби, зокрема легкові автомобілі, вантажні автомобілі а також автобуси, мотоцикли, тролейбуси, трактори й інші.

Педіатрія. Тест та відповіді

Лікувальна справа. Тестові питання з позначеними зірочкою правильні відповіді