Линейное программирование
Задача математического программирования. Совокупность граничных условий как типичная задача линейного программирования. Основа симплекс-метода. Поиск базовых решений, при которых значение целевой функции последовательно приближается к максимальному.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 07.04.2015 |
| Размер файла | 1007,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Линейное программирование
Задача 1.
1. Нефтяная компания "РТ" для улучшения эксплуатационных качеств и снижения точки замораживания дизельного топлива, которое она производит, добавляет в него определенные химикаты. В каждом бензобаке объемом 1000 л должно содержаться не менее 40 мг химической добавки X, не менее 14 мг химической добавки Y и не менее 18 мг химической добавки Z. Необходимые химические добавки в форме готовых смесей поставляют "РТ" две химические компании А и В. В нижеследующей таблице приведено содержание химических добавок в каждом продукте, поставляемом указанными компаниями.
|
Продукт |
Химические добавки, мг/л |
|||
|
X |
У |
Z |
||
|
А В |
4 5 |
2 1 |
3 1 |
Стоимость продукта А - 1,50 ф. ст. за 1 л, а продукта В - 3,00 ф. ст. за 1 л. Требуется: найти ассортиментный набор продуктов А и В, минимизирующий общую стоимость добавленных в топливо химикатов.
Решение:
Введем переменные:
x1 - количество продукта A;
x2 - количество продукта B.
Формальная постановка данной задачи имеет вид:
(1)
Метод решения задачи.
Совокупность граничных условий представляет собой типичную задачу линейного программирования. Одним из наиболее распространенных методов решения является симплекс-метод. Основу метода составляет поиск оптимальных и базовых решений, при которых значение целевой функции последовательно приближается к максимальному (или минимальному, в зависимости от направления поисков). В отличие от графического метода, симплекс-метод не обладает наглядностью, но отличается хорошей пригодностью для автоматизированной обработки результатов. В данной работе будет использован алгоритм последовательного приближения, который встроен в функцию табличного процессора MS Exel.
Ввод исходных данных
Создание экранной формы и ввод исходных данных
- для ввода переменных x1 и x2, используются ячейки B4 -D4;
- для отображения значения целевой функции используется ячейка B8, при этом коэффициенты целевой функции введены в ячейки B6-D6;
- коэффициенты уравнений системы ограничений введены в ячейках B12-B14 и C12-C14.
Ввод зависимостей из формальной постановки задачи в экранную форму. математический программирование линейный
Ввод зависимостей производится с использованием встроенных функций MS Exel. В данном примере использована функция СУММПРОИЗВ которая вычисляет сумму попарных произведений двух или более массивов.
Рис. 2
На рис. 2 представлена экранная форма ввода функции СУММПРОИЗВ.
Целевая функция представляет собой сумму произведений содержимого ячеек: B8:D8
Левые части ограничений задачи (1) представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B5, C5, D5), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения (B12, C12 - 1-е ограничение; B13, С 13 - 2-е ограничение и B14, С 14 - 3-е ограничение). Формулы, соответствующие левым частям ограничений, представлены в табл.1.
Формулы, описывающие ограничения модели (1)
|
Левая часть ограничения |
Формула Excel |
|
|
или |
=СУММПРОИЗВ(B4:B4;B12:C12) |
|
|
или |
=СУММПРОИЗВ(C4:C5;B13:C13) |
|
|
или |
=СУММПРОИЗВ(D4:D5;B14:C14) |
Задание целевой функции.
Для работы в надстройке "Поиск решения", необходимо выбрать и загрузить данную надстройку из меню "Сервис".
Рис. 3
На рис. 3 изображена экранная форма заполненной таблицы надстройки "Поиск решения". При этом выбрана ячейка B8, значение в которой соответствует целевой функции. Установлено направление поиска как минимизация целевой функции. Указаны ячейки B4, D5, изменения в которых предполагают изменение целевой функции. С помощью кнопки "добавить" вводится условие очередного ограничения.
Установка параметров решения задачи.
Для решения данной задачи использовались значения, установленные по умолчанию (Рис. 4), т.к. увеличение количества итераций не приводит к увеличению точности расчетов.
Рис. 4
Ответ: Наиболее экономным является вариант закупки 10 литров продукции компании А на каждые 1000 литров бензина, что обойдется в 15 ф.ст.
Размещено на Allbest.ru
...Подобные документы
Оптимизационные исследования задач линейного и нелинейного программирования при заданных математических моделях. Решение задач линейного программирования и использование геометрической интерпретации и табличного симплекс-метода, транспортная задача.
курсовая работа [408,7 K], добавлен 13.06.2019Классификация задач математического программирования. Сущность графического метода решения задач линейного программирования, алгоритм табличного симплекс-метода. Описание логической структуры и текст программы по решению задачи графическим методом.
курсовая работа [263,5 K], добавлен 27.03.2011Изучение экстремальных задач и поиск их решений. Выбор метода решения и приведения задачи к каноническому виду и к задаче линейного программирования. Метод искусственного базиса. Модифицированный симплекс-метод. Написание программы на языке С++Builder 6.
курсовая работа [343,0 K], добавлен 28.11.2010Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Постановка задачи линейного программирования. Решение системы уравнений симплекс-методом. Разработка программы для использования симплекс-метода. Блок-схемы основных алгоритмов. Создание интерфейса, инструкция пользователя по применению программы.
курсовая работа [1,7 M], добавлен 05.01.2015Методы определения оптимального плана производства (приобретения) продукции с учетом ограниченного обеспечения ресурсами различного вида. Технология поиска оптимального решения задач линейного программирования (ЗЛП) с помощью итоговой симплекс-таблицы.
лабораторная работа [42,8 K], добавлен 11.03.2011Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.
курсовая работа [280,8 K], добавлен 17.11.2011Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015Решение общей задачи линейного программирования симплексным методом, графическое построение целевой функции. Его проверка с помощью встроенной функции "Поиск решения" MS Excel. Определение плана перевозок при наименьших суммарных транспортных затрат.
контрольная работа [362,3 K], добавлен 03.11.2011Задачи оптимизации. Ограничения на допустимое множество. Классическая задача оптимизации. Функция Лагранжа. Линейное программирование: формулировка задач и их графическое решение. Алгебраический метод решения задач. Симплекс-метод, симплекс-таблица.
реферат [478,6 K], добавлен 29.09.2008Широкое применение вычислительной техники как в общей математике, так и в одном из её разделов – математических методах. Ознакомление с решением задач линейного программирования симплекс-методом и графически. Составлена программа на языке Delphi.
курсовая работа [57,1 K], добавлен 04.05.2010Алгоритм симплекс-метода. Задача на определение числа и состава базисных и свободных переменных, построение математической модели. Каноническая задача линейного программирования. Графический метод решения задачи. Разработки математической модели в Excel.
курсовая работа [1,1 M], добавлен 18.05.2013Оптимизационная задача линейного программирования. Виды задач линейного программирования. Принятие решений на основе количественной информации об относительной важности критериев. Выбор средств разработки. Программный комплекс векторной оптимизации.
дипломная работа [1,3 M], добавлен 27.03.2013Решение базовых задач линейного программирования симплекс-методом, их реализация на языке программирования С++. Математическое обеспечение; разработка алгоритма программы, решающей задачу с помощью симплекс-таблиц с произвольными свободными членами.
курсовая работа [217,8 K], добавлен 25.05.2014Постановка задачи линейного программирования и формы ее записи. Понятие и методика нахождения оптимального решения. Порядок приведения задач к каноническому виду. Механизмы решения задач линейного программирования аналитическим и графическим способами.
методичка [366,8 K], добавлен 16.01.2010Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.
курсовая работа [88,9 K], добавлен 11.02.2011Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Характеристика основных методов линейного программирования с n- переменными, в частности, графического и симплекс-метода. Способы решения задачи по определению оптимальной структуры товарооборота, обеспечивающей торговому предприятию максимум прибыли.
курсовая работа [678,7 K], добавлен 03.04.2011Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.
курсовая работа [100,0 K], добавлен 31.10.2014
