Симплекс-метод — Информатика. Шпоры | 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

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

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

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

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

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

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

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

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

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

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

Методичні вказівкипо виконанню методичної частини дипломних робіт для студентів інженерно-педагогічних спеціальностей

Питання методики професійного навчання – обов’язкова складова дипломних робіт студентів інженерно-педагогічних спеціальностей. Вони мають проектувальний характер і вирішують проблему кадрового забезпечення технічного об’єкту.

Мотив. Мотив человека и личности. Мотивация. Мотивирование

Потребности человека условны, подвижны, носят виртуальный характер. Мотив — это то, что побуждает человека к деятельности, направляя его на удовлетворение определенной потребности. Мотивация - это совокупность внутренних и внешних движущих сил

Иммунитет и его виды. Реферат

Формы иммунитета Механизмы иммунитета Воспаление и фагоцитоз Иммунологическая реактивность

Вопросы для подготовки к экзамену по дисциплине «Архитектура ЭВМ, сети и ассемблеры»

Растениеводство

Аграрная промышленность. Агропромышленный комплекс АПК. Задачи сельского хозяйства, растениеводства. Практика сельскохозяйственного производства. Особенности биологии и агротехники: озимой пшеницы, яровой пшеницы, ячменя, овса, проса, гречихи, гороха. Сорта.