Разработка программы, решающей базовую задачу линейного программирования симплекс-методом с помощью симплекс-таблиц. Выбор языка программирования и среды разработки, программные модули и их взаимодействие между собой. Листинг разработанной программы.
Аннотация к работе
Симплекс-метод - алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан советским математиком Канторовичем Л.В. в 1937 году. Решить данные задачи графически, когда количество переменных более 3 весьма затруднительно. Затем нужно проверить это решение на оптимальность. Надо заметить, что при переходе от одной вершины к другой значение целевой функции убывает (в задаче на минимум) или возрастает (в задаче на максимум). Первым исследованием по линейному программированию является работа Л.В. Канторовича “Математические методы организации и планирования производства”, опубликованная в 1939 г. В нем дана постановка задач линейного программирования, разработан метод разрешающих множителей решения задач линейного программирования и дано его теоретическое обоснование. Симплексный метод является универсальным, так как позволяет решить практически любую задачу линейного программирования, записанную в каноническом виде. 1.1 Постановка задачи линейного программирования Задача линейного программирования 0, называется базисом опорного плана и обозначается через Бx. Записав всю исходную информацию о задаче в таблицу, получим исходную (нулевую) симплексную таблицу (Таблица 1). (9) В последующие клетки (m 1)-й строки записываются значения оценок векторов условий Aj (величины Dj), которые вычисляются по формуле (10) Базисные разности Dsi=0. Составить план, обеспечивающий наибольшую прибыль производству: - записать математическую модель; - решить задачу симплекс-методом; Решение: Математическая модель. x1 - производство цемента первого вида; x2 - производство цемента второго вида; Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.