_(3.1) 

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

     Придавая  определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные x₁, x₂, ..., x_r, то решение {b₁, b₂,..., b_r, 0, ..., 0} будет опорным при условии, что b₁, b₂,..., b_r ≥ 0.

     Симплекс-метод  основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.

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

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

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

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

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

     Таким образом, применение симплексного метода распадается на два этапа: нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности; нахождение оптимального решения.

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

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

     Практическая  часть

 

     Постановка  задачи

     Торговое  предприятие планирует организовать продажу 4 видов товара A, B, C, D, учитывая при этом только два вида ресурсов: рабочее время продавцов в количестве 970 часов и площадь товарного зала 290 м². Плановые нормативы затрат ресурсов в расчете на единицу товара каждого наименования и прибыль от их продажи заданы в таблице. 

 

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

     Математическая  модель

 

     Пусть x – количество товара, продажу которого планирует организовать торговое предприятие. Тогда x₁ – товар вида A, x₂ – товар вида B, x₃ – товар вида C и x₄ – товар вида D.

     0,62x₁+0,81x₂+0,71x₃+0,43x₄ – расход рабочего времени на изготовление товара. Так как этот ресурс ограничен, имеем следующее ограничение: 0,62x₁+0,81x₂+0,71x₃+0,43x₄£970.

     0,13x₁+0,22x₂+0,45x₃+0,22x₄ – использование торгового зала на изготовление товара. Так как этот ресурс ограничен, имеем следующее ограничение: 0,13x₁+0,22x₂+0,45x₃+0,22x₄£290.

     Кроме того, количество выпущенной продукции не может быть отрицательной, следовательно, x₁³0, x₂³0, x₃³0, x₄³0.

     Задача  состоит том, чтобы найти значения x₁, x₂, x₃ и x₄ при которых полученная прибыль будет наибольшей. Прибыль обозначим F, тогда 

     F=30x₁+50x₂+62x₃+40x₄Þmax 

     Таким образом, получаем следующую экономико-математическую модель задачи линейного программирования: 

     

     

     Решение задачи в MS Excel

 

     В качестве значений переменных x₁, x₂, x₃, x₄ будем использовать ячейки $B$12:$B$15. Для значения целевой функции будем использовать ячейку $C$16.

     В целевую ячейку $C$16 впишем формулу: B5*B12+C5*B13+D5*B14+E5*B15.

     В ячейку $C$12 впишем формулу прибыли от товара A: B5*B12.

     В ячейку $C$13 впишем формулу прибыли от товара B: C5*B13.

     В ячейку $C$14 впишем формулу прибыли от товара C: D5*B14.

     В ячейку $C$15 впишем формулу прибыли от товара D: E5*B15.

     В ячейку $G$3 впишем формулу ограничения расхода рабочего времени: B3*B12+C3*B13+D3*B14+E3*B15.

     В ячейку $G$4 впишем формулу ограничения использования площади торгового зала: B4*B12+C4*B13+D4*B14+E4*B15. 

     

     Рис. 1 Компьютерная модель задачи 

     Далее выбираем пункт меню Сервис/Поиск  решения: 

     

     Рис. 2 Окно поиска решения 

     Перед нами открывается диалоговое окно Поиск  решения. В нём указываем, что  нам необходимо установить ячейку $C$16 максимальному значению, изменяя ячейки $B$12:$B$15. Далее нажимаем кнопку Добавить для добавления ограничений. И добавляем следующие ограничения:

 

     

     Рис. 3 Добавление ограничений 

     Ограничения по расходу рабочего времени на единицу  товара.

     После ввода каждого ограничения нажимаем кнопку Добавить. После ввода последнего ограничения нажимаем кнопку OK. И диалоговое окно Поиск решения принимает следующий вид: 

     

     Рис. 4 Окно поиска решения, после ввода ограничений 

     Задаем  параметры поиска решения: 

     

     Рис. 5 Измененеие параметров поиска решения

 

     Нажимаем  кнопку Выполнить. И перед нами открывается  диалоговое окно Результаты поиска решения: 

     

     Рис. 6 Выбираем отчет по результатам 

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

     Рис. 7 Результат выполнения поиска решения 

     Отчет по результатам