Реферат: Решение задач симплексным методом
Название: Решение задач симплексным методом Раздел: Рефераты по математике Тип: реферат | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Оглавление 1. КРАТКИЙ ОБЗОР АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДАННОГО ТИПА 5 1.1 Математическое программирование 5 1.2 Табличный симплекс - метод 6 1.3 Метод искусственного базиса 7 1.4 Модифицированный симплекс - метод 7 2.СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ 9 3.РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ 10 3.1 Построение математической модели задачи 10 Список использованных источников 30 Проникновение математики в экономическую науку связано с преодолением значительных трудностей. В этом отчасти была "повинна" математика, развивающаяся на протяжении нескольких веков в основном в связи с потребностями физики и техники. Но главные причины лежат все же в природе экономических процессов, в специфике экономической науки. Большинство объектов, изучаемых экономической наукой, может быть охарактеризовано кибернетическим понятием сложная система. Наиболее распространено понимание системы как совокупности элементов, находящихся во взаимодействии и образующих некоторую целостность, единство. Важным качеством любой системы является эмерджентность - наличие таких свойств, которые не присущи ни одному из элементов, входящих в систему. Поэтому при изучении систем недостаточно пользоваться методом их расчленения на элементы с последующим изучением этих элементов в отдельности. Одна из трудностей экономических исследований - в том, что почти не существует экономических объектов, которые можно было бы рассматривать как отдельные (внесистемные) элементы. Сложность системы определяется количеством входящих в нее элементов, связями между этими элементами, а также взаимоотношениями между системой и средой. Экономика страны обладает всеми признаками очень сложной системы. Она объединяет огромное число элементов, отличается многообразием внутренних связей и связей с другими системами (природная среда, экономика других стран и т.д.). В народном хозяйстве взаимодействуют природные, технологические, социальные процессы, объективные и субъективные факторы. Сложность экономики иногда рассматривалась как обоснование невозможности ее моделирования, изучения средствами математики. Но такая точка зрения в принципе неверна. Моделировать можно объект любой природы и любой сложности. И как раз сложные объекты представляют наибольший интерес для моделирования; именно здесь моделирование может дать результаты, которые нельзя получить другими способами исследования. Потенциальная возможность математического моделирования любых экономических объектов и процессов не означает, разумеется, ее успешной осуществимости при данном уровне экономических и математических знаний, имеющейся конкретной информации и вычислительной технике. И хотя нельзя указать абсолютные границы математической формализуемости экономических проблем, всегда будут существовать еще неформализованные проблемы, а также ситуации, где математическое моделирование недостаточно эффективно. 1. КРАТКИЙ ОБЗОР АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДАННОГО ТИПА 1.1 Математическое программирование Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом : найти экстремум некоторой функции многих переменных f ( x1, x2, ... , xn ) при ограничениях gi ( x1, x2, ... , xn ) * bi , где gi - функция, описывающая ограничения, * - один из следующих знаков Ј , = , і , а bi - действительное число, i = 1, ... , m. f называется функцией цели ( целевая функция ). Линейное программирование - это раздел математического программирования, в котором рассматриваются методы решения экстремальных задач с линейным функционалом и линейными ограничениями, которым должны удовлетворять искомые переменные. Задачу линейного программирования можно сформулировать так . Найти max при условии : a11 x1 + a12 x2 + . . . + a1n xn Ј b1 ; a21 x1 + a22 x2 + . . . + a2n xn Ј b2 ; . . . . . . . . . . . . . . . . . . . . . . . . . . . . am1 x1 + am2 x2 + . . . + amn xn Ј bm ; x1 і 0, x2 і 0, . . . , xn і 0 . Эти ограничения называются условиями неотрицательности. Если все ограничения заданы в виде строгих равенств, то данная форма называется канонической. В матричной форме задачу линейного программирования записывают следующим образом. Найти max cT x при условии A x Ј b ; x і 0 , где А - матрица ограничений размером ( mґn), b(mґ1) - вектор-столбец свободных членов, x(n ґ 1) - вектор переменных, сТ = [c1, c2, ... , cn ] - вектор-строка коэффициентов целевой функции. Решение х0 называется оптимальным, если для него выполняется условие сТ х0 і сТ х , для всех х О R(x). Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации. Для решения задач данного типа применяются методы: 1) графический; 2) табличный ( прямой, простой ) симплекс - метод; 3) метод искусственного базиса; 4) модифицированный симплекс - метод; 5) двойственный симплекс - метод. 1.2 Табличный симплекс - метод Для его применения необходимо, чтобы знаки в ограничениях были вида “ меньше либо равно ”, а компоненты вектора b - положительны. Алгоритм решения сводится к следующему : Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам. Если в исходной системе ограничений присутствовали знаки “ равно ” или “ больше либо равно ”, то в указанные ограничения добавляются искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума. Формируется симплекс-таблица. Рассчитываются симплекс-разности. Принимается решение об окончании либо продолжении счёта. При необходимости выполняются итерации. На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом. 1.3 Метод искусственного базиса Данный метод решения применяется при наличии в ограничении знаков “ равно ”, “ больше либо равно ”, “ меньше либо равно ” и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами m , а в задачи минимизации - с положительными m . Таким образом из исходной получается новая m - задача. Если в оптимальном решении m - задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении m - задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима. 1.4 Модифицированный симплекс - метод В основу данной разновидности симплекс-метода положены такие особенности линейной алгебры , которые позволяют в ходе решения задачи работать с частью матрицы ограничений. Иногда метод называют методом обратной матрицы. В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений по частям, соответствующим текущим базисным векторам. Указанная способность делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени счёта. Хорош для ситуаций, когда число переменных n значительно превышает число ограничений m. В целом, метод отражает традиционные черты общего подхода к решению задач линейного программирования, включающего в себя канонизацию условий задачи, расчёт симплекс-разностей, проверку условий оптимальности, принятие решений о коррекции базиса и исключение Жордана-Гаусса. Особенности заключаются в наличии двух таблиц - основной и вспомагательной, порядке их заполнения и некоторой специфичности расчётных формул. 2.СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ Для производства двух видов изделий А и В используется три типа технологического оборудования. На производство единицы изделия А идёт времени, часов : оборудованием 1-го типа - а1 , оборудованием 2-го типа - а2 , оборудованием 3-го типа - а3 . На производство единицы изделия В идёт времени, часов : оборудованием 1-го типа - b1 , оборудованием 2-го типа - b2 ,, оборудованием 3-го типа - b3 . На изготовление всех изделий администрация предприятия может предоставить оборудование 1-го типа не более, чем на t1 , оборудование 2-го типа не более, чем на t2 , оборудование 3-го типа не более, чем на t3 часов. Прибыль от реализации единицы готового изделия А составляет a рублей, а изделия В - b рублей. Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации. Решить задачу простым симплекс-методом. Дать геометрическое истолкование задачи, используя для этого её формулировку с ограничениями-неравенствами. а1 = 1 b1 = 5 t1 = 10 a = 2 а2 = 3 b2 = 2 t2 = 12 b = 3 а3 = 2 b3 = 4 t3 = 10 3.РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ 3.1 Построение математической модели задачи
Построение математической модели осуществляется в три этапа : 1. Определение переменных, для которых будет составляться математическая модель. Так как требуется определить план производства изделий А и В, то переменными модели будут: x1 - объём производства изделия А, в единицах; x2 - объём производства изделия В, в единицах. 2. Формирование целевой функции. Так как прибыль от реализации единицы готовых изделий А и В известна, то общий доход от их реализации составляет 2x1 + 3x2 ( рублей ). Обозначив общий доход через F, можно дать следующую математическую формулировку целевой функции : определить допустимые значения переменных x1 и x2 , максимизирующих целевую функцию F = 2x1 + 3x2 . 3. Формирование системы ограничений. При определении плана производства продукции должны быть учтены ограничения на время, которое администрация предприятия сможет предоставить на изготовления всех изделий. Это приводит к следующим трём ограничениям : x1 + 5x2 Ј 10 ; 3x1 + 2x2 Ј 12 ; 2x1 + 4x2 Ј 10 . Так как объёмы производства продукции не могут принимать отрицательные значения, то появляются ограничения неотрицательности : x1 і 0 ; x2 і 0 . Таким образом, математическая модель задачи представлена в виде : определить план x1 , x2 , обеспечивающий максимальное значение функции : max F = max ( 2x1 + 3x2 ) при наличии ограничений : x1 + 5x2 Ј 10 ; 3x1 + 2x2 Ј 12 ; 2x1 + 4x2 Ј 10 . x1 і 0 ; x2 і 0 . 3.2 Решение задачи вручную Табличный метод ещё называется метод последовательного улучшения оценки. Решение задачи осуществляется поэтапно. 1. Приведение задачи к форме : x1 + 5x2 Ј 10 ; 3x1 + 2x2 Ј 12 ; 2x1 + 4x2 Ј 10 . x1 і 0 ; x2 і 0 . 2. Канонизируем систему ограничений : x1 + 5x2 + x3 = 10 ; 3x1 + 2x2 + x4 = 12 ; 2x1 + 4x2 + x5 = 10 . x1 і 0 ; x2 і 0 . A1 A2 A3 A4 A5 A0 3. Заполняется исходная симплекс-таблица и рассчитываются симплекс-разности по формулам : d0 = - текущее значение целевой функции
di = - расчёт симплекс-разностей, где j = 1..6 . Так как при решении задачи на max не все симплекс-разности положительные, то оптимальное решение можно улучшить. 4. Определяем направляющий столбец j*. Для задачи на max он определяется минимальной отрицательной симплекс-разностью. В данном случае это вектор А2 5. Вектор i*, который нужно вывести из базиса, определяется по отношению : min при аi j > 0 В данном случае сначала это А3 . 5. Заполняется новая симплекс-таблица по исключеню Жордана - Гаусса : а). направляющую строку i* делим на направляющий элемент : a i j = a i j / a i j , где j = 1..6 б). преобразование всей оставшейся части матрицы : a ij = aij - a i j Ч aij , где i № i* , j № j*
В результате преобразований получаем новую симплекс-таблицу : Повторяя пункты 3 - 5, получим следующие таблицы :
Так как все симплекс-разности положительны, то оптимальное решение найдено : X = ( 7/2 , 3/4 , 11/4 , 0 , 0 ) ( единиц ) max F = 9 1/4 ( рублей ) 4.НАЗНАЧЕНИЕ ПРОГРАММЫ Программа предусмотрена для решения систем линейных неравенств табличным методом, а так же для попытки оптимизации различных экономических, социальных и т. д. проблем. Метод, описанный в программе, может применяться на государственных и частных предприятиях для улучшения эффективности производства. Задание условий Все условия задаются в колонке “A” первого листа(программа результат помещает в лист 2) В третьей строке(”A3″) необходимо записать целеыую функцию на минимум или максимум(min или max после =) например: 3Ч1+2Ч2+4Ч3+2Ч4=min В 5 строке необходимо записать количество знаков в дробной части чисел(или ничего то есть пусто или пробел(ы) ) начиная с 9 строки записываются ограничения по одной строке на каждое ограничениe. Hапример: 6Ч2+6Ч3+4Ч4=60 Во всех, не занятых условием задачи ячейках, можно писать что угодно. После ввода условий задачи клацните по кнопке, которую вы первую занесли на лист Excel. Получение результата Результат работы располагается на втором листе книги. Вначале там помещается таблица изображающая условие задачи в каноническом виде, а затем очередная итерация. Любую таблицу(начальную или после очередной итерации) можно как угодно оформить для печати и распечатать. все изменения сделанные в это время на этом листе никак не влияют на следующую итерацию. При следующей итерации второй лист полностью очищается и формируются результаты новой итерации. Для получения новой итерации следует перейти на первый лист(он называется “Initial data” и нажать кнопку для получения следующей итерации. Если промежуточные результаты не нужны, то следует последовательно нажимать на кнопку получения новой итерации, не переходя на второй лист и перейти на него только для просмотра окончательного результата. 6. ТЕКСТ ИСХОДНОГО МОДУЛЯ Dim Ftarget As String ’целевая функция target function Dim MaxX As Integer ‘максимальный индех Х в целевой функции Dim MaxLi As Boolean ‘true-max; False-min Dim AmRest As Integer ‘ Количество строк ограничений (Amount of the restrictions) Private Type Tmy IndX As Integer KoefX As Double End Type ‘Номер очередного обрабатываемого символа в строке Dim Icurrent As Integer Dim BgRight As Integer ’Номер байта начала правой части ограничения, иначе 0; ‘The Number of the byte begin right part of restriction, otherwise 0; Dim Isx As String Dim Rez() As Tmy Dim NumIter As Integer ‘Номер итерации. Если равен нулю, канонический вид симплекс таблицы ‘Number to iterations. If is a zero, canonical type simplex tables Dim MiCiXiAi() As Double ‘Два первых столбца этого массива заменяют первый столбец симплексной таблицы. ‘Первый столбец, это множитель “М”, вводимый для искуственных переменных для ограничений “>” или “=” ‘Второй столбец, это коэфициенты переменных в целевой функции ‘(номера этих переменных указаны в третьем столбце массива MiCiXiAi) ‘Четвертый столбец массива MiCiXiAi(”Alfa”), это последний столбец симплексной таблицы равный X0/Хi ‘Two first columns of this array change the first column of the simplex table. ‘First column, this multiplier “M”, introduced for illusory variables for restrictions “>” or “=” ‘Second column, this values from target function ‘Second column is values variables in target function ‘(number these variables is specified in one third column array MiCiXiAi) ‘Fourth column of the array MiCiXiAi(”Alfa”), this last column of the simplex table equal X0/Hi Dim Tsimp() As Double ‘ the simplex table Dim CleaDoub() As Double Dim CleaTMY() As Tmy Dim Icol As Integer ’ Ключевой столбец.The Key column. Dim Irow As Integer ’ Ключевая строка. The Key line. Dim AllPlans As String ’Все планы в текущей задаче. All plans in the current task. Dim DirectCycle As Boolean ‘True-Прямой цикл; True-Direct cycle; Private Sub ProcString(Strin As String, Ans() As Tmy, CalcMaxX As Boolean) ‘Выделение из “Strin” числовых данных. Одновременно вычисляем махимальный индех переменно Х ‘Separation from “Strin” numeric data. Simultaneously we calculate the Largest number variable X. Dim Awork() As Tmy Dim VaLi As Double Dim i As Integer ’ index in awork Strin = Replace(Strin, ” “, “”) ‘ Убрали лишьние пробелы в целевой функции Strin = Trim(Strin) Strin = Replace(Strin, “X”, “x”) ‘Заменим все х на маленькое английское Strin = Replace(Strin, “Х”, “x”) ‘Русское большое на маленькое английское x Strin = Replace(Strin, “х”, “x”) ‘Русское маленькое на маленькое английское x Strin = Replace(Strin, “>=”, “>”) ‘ Strin = Replace(Strin, “<=”, “<”) ‘ BgRight = 0 i = 0 Icurrent = 1 Do While BgRight = 0 i = i + 1 ReDim Preserve Awork(i) VaLi = ExtractDbl(Strin, Icurrent) Awork(i).KoefX = VaLi VaLi = ExtractDbl(Strin, Icurrent) Awork(i).IndX = CInt(VaLi) If CalcMaxX Then If MaxX < CInt(VaLi) Then MaxX = CInt(VaLi) Loop Ans = Awork End Sub Private Sub CommandButton1_Click() Dim i As Integer Dim j As Integer Dim K As Integer Dim Acell As String Dim St1 As String * 1 Dim Vdbl As Double NumIter = 0 MaxX = 0 AllPlans = “” DirectCycle = True CommandButton1.ForeColor = &H40C0& ’Оранжевый CommandButton1.Caption = “Привести к каноническому виду” CommandButton1.Font = Bold CommandButton1.Font.Size = 12 CommandButton1.Top = 1.5 CommandButton1.Left = 0.75 CommandButton1.Height = 24 CommandButton1.Width = 204 CommandButton2.ForeColor = &H8000& ’Зеленый CommandButton2.Font = Bold CommandButton2.Font.Size = 12 CommandButton2.Top = 1.5 CommandButton2.Left = 204 CommandButton2.Height = 24 CommandButton2.Width = 186 MiCiXiAi = CleaDoub Rez = CleaTMY Tsimp = CleaDoub CommandButton2.Visible = False Sheets(2).Name = “Пусто” Sheets(2).Tab.ColorIndex = 6 ‘Скроем все листы кроме первого. Первый лист переименуем в исходные данные. ‘We shall Hide all sheets except the first. The First sheet shall name “Initial data”. ‘For i = 3 To Sheets.Count ‘ Sheets(i).Visible = False ‘ Sheets(i).Visible = True ‘Next i Sheets(1).Name = “Initial data” ‘определение количество строк с ограничениями ‘вычисление максимального индеха переменной Х (записіваем в MaxX). ‘Determination amount lines with restrictions ‘calculation the largest number variable X (record in MaxX). Ftarget = Range(”A3″).Value ProcString Ftarget, Rez, True i = i Isx = Trim(Range(”A9″).Value) Do While Isx <> “” ProcString Isx, Rez, True ’if True, then calculate MaxX i = i + 1 Acell = “A” & CStr(i + Isx = Trim(Range(Acell).Value) Loop AmRest = i - 1 ‘Получение значений целевой функции в массиве Rez ‘Reception of importances of the target function in array Rez Ftarget = Range(”A3″).Value ProcString Ftarget, Rez, False i = InStr(Ftarget, “=”) If i = 0 Then MsgBox (”В целевой функции нет знака = “) End End If If Mid(Ftarget, i + 1, 3) = “min” Then MaxLi = False ElseIf Mid(Ftarget, i + 1, 3) = “max” Then MaxLi = True Else MsgBox (”В целевой функции нет ни ‘max’ ни ‘min’ “) End End If ‘ Запись значений целевой функции в симплекс таблицу ‘We write values of the target function in simplex table ReDim Preserve Tsimp(AmRest + 3, MaxX) ReDim Preserve MiCiXiAi(AmRest, 4) For i = 1 To UBound(Rez) j = Rez(i).IndX Tsimp(0, j) = Rez(i).KoefX Next ‘Получение значений условий в массиве Rez и запись их значения в симплекс таблицу ‘Reception of importances of the conditions in array Rez and record of their values in simplex table For K = 1 To AmRest Acell = “A” & CStr(K + Isx = Range(Acell).Value ProcString Isx, Rez, False For i = 1 To UBound(Rez) j = Rez(i).IndX Tsimp(K, j) = Rez(i).KoefX Next i Tsimp(K, 0) = Mid(Isx, BgRight) ’Правая часть ограничения. Right part of restriction. St1 = Mid(Isx, BgRight - 1, 1) ‘ Если свободный член отрицателен, то следует изменить все значения на линии “K” в противоположном значении. ‘ If free member negative, that follows to change all importances on lines “K” in opposite importance If Tsimp(K, 0) < 0 Then For i = 0 To AmRest Tsimp(K, i) = -Tsimp(K, i) Next i If St1 = “>” Then St1 = “<” ElseIf St1 = “<” Then St1 = “>” End If End If If St1 = “>” Then ‘ Если больше добавим 2 искуственных неизвестных MaxX = MaxX + 2 ReDim Preserve Tsimp(AmRest + 3, MaxX) Tsimp(K, MaxX - 1) = -1 Else ’Ограничение на равно или меньше MaxX = MaxX + 1 ReDim Preserve Tsimp(AmRest + 3, MaxX) End If Tsimp(K, MaxX) = 1 If MaxLi And (St1 = “>” Or St1 = “=”) Then ’ Если махимум, в целевую функцию добавляем -Mxi, иначе +Mxi Tsimp(AmRest + 3, MaxX) = -1 ‘ для > или = ElseIf (Not MaxLi) And (St1 = “>” Or St1 = “=”) Then Tsimp(AmRest + 3, MaxX) = 1 End If MiCiXiAi(K, 1) = Tsimp(AmRest + 3, MaxX) MiCiXiAi(K, 3) = MaxX Next K ‘ Вычисление оценки For j = 0 To MaxX Vdbl = 0 For i = 1 To AmRest Vdbl = Vdbl + MiCiXiAi(i, 1) * Tsimp(i, j) Next i Tsimp(AmRest + 1, j) = Vdbl - Tsimp(AmRest + 3, j) Tsimp(AmRest + 2, j) = -Tsimp(0, j) Next j FRowCol If Cycle() Then MsgBox (”Неизвестная ошибка”) End If If Icol > 0 And Irow > 0 Then LookResult “Каноническая таблица”, 31 ElseIf Icol > 0 And Irow <= 0 Then LookResult “Функция не ограничена”, 28 Else LookResult “Итерация невозможна”, 3 End If End Sub Private Sub LookResult(Sname As String, Fcolor As Integer) ‘Sheets(2).Tab.ColorIndex = 4 ‘ Fcolor= 4-зеленый, 3-Красный, 37-Серосиний, 6-Желтый ‘ На втором листе начиная с ячейки A11 построим симплекс таблицу ‘ Вначале сделаем рамку ‘CreFrame(Vtop As Integer, Vleft As Integer, Vbottom As Integer, Vright As Integer) Dim i As Integer, j As Integer Dim Stk As String Dim Sround As String Sheets(2).Name = Sname Sheets(2).Tab.ColorIndex = Fcolor Sheets(2).Range(”a:iv”).Clear CreFrame 11, 4, 11, MaxX + 3 CreFrame 12, 1, 12, MaxX + 4 CreFrame 12, 1, 12, 2 CreFrame 12, 4, 12, MaxX + 3 CreFrame 13, 1, 12 + AmRest, MaxX + 4 CreFrame 13, 4, 12 + AmRest, MaxX + 3 CreFrame 13, 3, 12 + AmRest, 3 CreFrame 13 + AmRest, 3, 13 + AmRest, MaxX + 4 CreFrame 13 + AmRest, 4, 13 + AmRest, MaxX + 3 CreFrame 14 + AmRest, 3, 14 + AmRest, MaxX + 4 CreFrame 14 + AmRest, 4, 14 + AmRest, MaxX + 3 ‘Заполнение шапки симплексной таблицы ‘Filling the hat of the simplex table For i = 0 To MaxX Sheets(2).Cells(12, i + 3).Value = “X” + CStr(i) Next i If MaxLi Then Sheets(2).Cells(11, 3).Value = “F(Max)” Else Sheets(2).Cells(11, 3).Value = “F(Min)” Sheets(2).Cells(12, 1).Value = “Сi” Sheets(2).Cells(12, 2).Value = “P” + CStr(NumIter - 1) Sheets(2).Cells(12, MaxX + 4).Value = “Alfa” Sheets(2).Cells(13 + AmRest, 2).Value = “M–>” ‘Заполнение симплексной таблицы коэффициентами целевой функции ‘Filling the simplex table factor to target function For j = 1 To MaxX If Tsimp(AmRest + 3, j) = 0 Then Sheets(2).Cells(11, j + 3).Value = Tsimp(0, j) Else If Tsimp(AmRest + 3, j) > 0 Then Sheets(2).Cells(11, j + 3).Value = ” M” Else Sheets(2).Cells(11, j + 3).Value = ” -M” End If Next j ‘Формирование первой, второй и последней колонок симплексной таблицы ‘Shaping first, second and last columnы of the simplex table For i = 1 To AmRest If MiCiXiAi(i, 1) = 0 Then Sheets(2).Cells(12 + i, 1).Value = MiCiXiAi(i, 2) ElseIf MiCiXiAi(i, 1) > 0 Then Sheets(2).Cells(12 + i, 1).Value = ” M” Else Sheets(2).Cells(12 + i, 1).Value = ” -M” End If Sheets(2).Cells(12 + i, 2).Value = MiCiXiAi(i, 3) Sheets(2).Cells(12 + i, MaxX + 4).Value = MiCiXiAi(i, 4) Next i ‘Заполнение симплексной таблицы коэфициентами ограничений ‘Filling the simplex table koefficient restrictions For i = 1 To AmRest + 2 For j = 0 To MaxX Sheets(2).Cells(12 + i, j + 3).Value = Tsimp(i, j) Next j Next i If Icol > 0 Then ‘ColourFrame(Vtop, Vleft, Vbottom, Vright, Vcolour=34) ColourFrame 11, Icol + 3, AmRest + 14, Icol + 3, 34 End If If Irow > 0 Then ColourFrame Irow + 12, 2, Irow + 12, MaxX + 4, 34 End If ‘Информация об итерации или канонической таблице ‘Information on iterations or canonical table If Fcolor = 31 Or Fcolor = 3 Then Stk = “Начальная симплекс таблица задачи на ” Stk = Stk & IIf(MaxLi, “максимум”, “минимум”) & “, приведенной к каноническому виду.” With Sheets(2).Range(”A1″) .Font.FontStyle = “Bold” .Value = Stk End With Stk = IIf(Fcolor = 31, “Возможно улучшение плана.”, “Итерация невозможна(Видимо протероречивые условия).”) Sheets(2).Range(”A2″).Value = Stk Stk = “Разрешающий столбец определяется по двум последним строкам таблицы.” Sheets(2).Range(”A3″).Value = Stk Stk = “В пересечении колонок Х0-Х” & CStr(MaxX) Stk = Stk & IIf(MaxLi, “(выбирается максимальное по модулю отрицательное число).”, “(выбирается максимальное положительное число).”) Sheets(2).Range(”A4″).Value = Stk Stk = “Сначала просматривается строка помеченная знаком “”M–>”" ” Sheets(2).Range(”A5″).Value = Stk Stk = ” и если в ней нет ” & IIf(MaxLi, “отрицательных”, “положительных”) & “чисел, просматривается последняя строка.” Sheets(2).Range(”A6″).Value = Stk Stk = “Если разрешающий столбец не нашли, то в таблице представлен оптимальный план.” Sheets(2).Range(”A7″).Value = Stk Stk = “Разрешающая строка определяется по минимальному не отрицательному отношению ” Sheets(2).Range(”A8″).Value = Stk Stk = “коэффициентов столбца Х0 и разрешающего столбца(что представлено в столбце Alfa).” Sheets(2).Range(”A9″).Value = Stk ElseIf Fcolor = 50 Then Sheets(2).Range(”A1:A10″).Clearcatchword Stk = “После итерации №” & CStr(NumIter - 1) & “(возможно улучшение плана) ” With Sheets(2).Range(”A6″) .Font.FontStyle = “Bold” .Value = Stk End With i = IIf(Tsimp(AmRest + 1, Icol) = 0, 1, 2) Stk = “Так как в ” & IIf(i = 1, “последней”, “предпоследней”) & “строке(начиная с колонки Х1)” Sheets(2).Range(”A7″) = Stk Stk = IIf(MaxLi, “(имеется максимальное по модулю отрицательное число).”, “(имеется максимальное положительное число).”) Sheets(2).Range(”A8″) = Stk Stk = “А в столбце “”Alfa”" имеется не отрицательное число(выбрано минимальное)” Sheets(2).Range(”A9″) = Stk ElseIf Fcolor = 37 Then Stk = “После итерации №” & CStr(NumIter - 1) & ” получили оптимальный план. ” j = IIf(Trim(CStr(Sheets(1).Range(”A5″).Value)) <> “”, CInt(Sheets(1).Range(”A5″).Value), -1) ‘j=-1 Without truncation With Sheets(2).Range(”A5″) .Font.FontStyle = “Bold” .Value = Stk End With Sround = IIf(j = -1, CStr(Tsimp(AmRest + 2, 0)), CStr(Round(Tsimp(AmRest + 2, 0), j))) Stk = “Для функции ” & Ftarget & ” результат равный ” & Sround Sheets(2).Range(”A6″).Value = Stk Stk = “Достигается при ” For i = 1 To AmRest If MiCiXiAi(i, 2) <> 0 Then Sround = IIf(j = -1, CStr(Tsimp(i, 0)), CStr(Round(Tsimp(i, 0), j))) Stk = Stk & “X” & CStr(MiCiXiAi(i, 3)) & “=” & Sround & “;” End If Next i Sheets(2).Range(”A7″).Value = Stk Stk = “Номера переменных Х и их значения находятся, соответственно, во второй и третьей колонках симплекс таблицы” Sheets(2).Range(”A8″).Value = Stk Stk = “Оптимальный план находится в первой ячейке последней строки симплекс таблицы” Sheets(2).Range(”A9″).Value = Stk End If ‘Округление Truncation ‘Количество знаков в дробной части в символьном виде ‘Amount sign in fractional part in symbol type If Trim(CStr(Sheets(1).Range(”A5″).Value)) <> “” Then j = CInt(Sheets(1).Range(”A5″).Value) Sround = “0.” For i = 1 To j Sround = Sround & “0″ Next i Stk = “C13:” & R1C1_to_A1(AmRest + 12, MaxX + 3) Sheets(2).Range(Stk).NumberFormat = Sround Stk = R1C1_to_A1(AmRest + 14, 3) Sheets(2).Range(Stk).NumberFormat = Sround End If ‘Viewing Canonical type End Sub Function ExtractDbl(Stk As String, ByVal iBg As Integer) As Double ‘поиск номера неизвестного xi(то есть вычисление i) ‘ номер i начинается от символа с номером iBg(включительно) и продолжается до одного из символов: +, -, =, >, < ‘Searching for of the number unknown xi(that is to say calculation i). ‘Number i begins from symbol with number iBg(inclusive) and lasts before one of the symbol: +, -, =, >, < Dim SimIbg As String * 1 Dim i As Integer Dim St1 As String * 1 For i = iBg To Len(Stk) St1 = Mid(Stk, i, 1) If i = iBg Then SimIbg = St1 If St1 = “x” Then Icurrent = i + 1 Exit For ElseIf (St1 = “+” Or St1 = “-”) And i <> iBg Then Icurrent = i Exit For ElseIf St1 = “=” Or St1 = “>” Or St1 = “<” Then Icurrent = i + 1 BgRight = i + 1 Exit For End If Next i If i > Len(Stk) Then MsgBox (”osibka in “”" & Stk & “”"”) End End If If iBg = i Then ExtractDbl = 1 ElseIf (i - iBg) = 1 And (SimIbg = “+” Or SimIbg = “-”) Then If SimIbg = “+” Then ExtractDbl = 1 Else ExtractDbl = -1 Else ExtractDbl = CDbl(Mid(Stk, iBg, i - iBg)) End If End Function ‘Процедура CreFrame обрамляет область листа заданную кординатами ‘верхнего левого угла и координатами нижнего правого угла ‘ Procedure CreFrame does frame of the area of the sheet ‘given by coordinates of the upper left corner and coordinates of the right lower corner Sub CreFrame(Vtop As Integer, Vleft As Integer, Vbottom As Integer, Vright As Integer) Dim Stk As String Stk = R1C1_to_A1(Vtop, Vleft) & “:” & R1C1_to_A1(Vbottom, Vright) With Sheets(2).Range(Stk) .Borders(xlEdgeLeft).Weight = xlThick .Borders(xlEdgeRight).Weight = xlThick .Borders(xlEdgeTop).Weight = xlThick .Borders(xlEdgeBottom).Weight = xlThick .Borders(xlInsideVertical).Weight = xlThin .Borders(xlInsideHorizontal).Weight = xlThin End With End Sub ‘Процедура ColourFrame заполняет цветом область листа заданного координатами ‘верхнего левого угла и координатами правого нижнего угла ‘ The Procedure ColourFrame fills the colour an area sheet given by coordinates ‘ of the upper left corner and coordinates of the right lower corner. Sub ColourFrame(Vtop As Integer, Vleft As Integer, Vbottom As Integer, Vright As Integer, Vcolour As Integer) Dim Stk As String Stk = R1C1_to_A1(Vtop, Vleft) & “:” & R1C1_to_A1(Vbottom, Vright) Sheets(2).Range(Stk).Interior.ColorIndex = Vcolour ’Vcolour есть номер цвета в цветовой схеме. ‘ .ColorIndex = 34 ‘Vcolour there is number of the colour in color scheme. End Sub Function R1C1_to_A1(Vrow As Integer, Vcol As Integer) As String V26 = “ABCDEFGHIJKLMNOPQRSTUVWXVZ” Dim Stk As String If Vcol > 26 Then Stk = Mid(V26, Int(Vcol / 26), 1) + Mid(V26, (Vcol Mod 26), 1) + CStr(Vrow) Else Stk = Mid(V26, Vcol, 1) + CStr(Vrow) End If R1C1_to_A1 = Stk End Function Private Sub CalcColB() ‘Вычисление ключевого столбца по найбольшей оценке(когда min) ‘Calculation key column on the largest estimation(when min) Dim i As Integer Dim WrcM As Double, IrcM As Integer Dim WrcC As Double, IrcC As Integer WrcM = 0 WrcC = 0 For i = 1 To MaxX If Tsimp(AmRest + 1, i) > WrcM Then WrcM = Tsimp(AmRest + 1, i) IrcM = i ElseIf Tsimp(AmRest + 2, i) > WrcC And Tsimp(AmRest + 1, i) = 0 Then WrcC = Tsimp(AmRest + 2, i) IrcC = i End If Next i If WrcM > 0 Then Icol = IrcM ElseIf WrcC > 0 Then Icol = IrcC Else Icol = 0 End If End Sub Private Sub CalcColL() ‘Вычисление ключевого столбца по отрицательной(максимальной по модулю) оценке(когда max) ‘Calculation key column on negative(maximum modulo) to estimation(when max) Dim i As Integer Dim WrcM As Double, IrcM As Integer Dim WrcC As Double, IrcC As Integer WrcM = 0 WrcC = 0 For i = 1 To MaxX If Tsimp(AmRest + 1, i) < 0 And Abs(Tsimp(AmRest + 1, i)) > WrcM Then WrcM = Abs(Tsimp(AmRest + 1, i)) IrcM = i ElseIf (Tsimp(AmRest + 2, i) < 0) And (Abs(Tsimp(AmRest + 2, i)) > WrcC) And (Tsimp(AmRest + 1, i) = 0) Then WrcC = Abs(Tsimp(AmRest + 2, i)) IrcC = i End If Next i If WrcM > 0 Then Icol = IrcM ElseIf WrcC > 0 Then Icol = IrcC Else Icol = 0 End If End Sub Private Sub CalcRow() ‘Вычисление ключевой строки по положительному минимум отношения X0/Xi ‘Calculation of the key line on positive minimum relations X0/Xi Dim Cslave As Double, Islave As Integer Dim Wrk As Double If Icol = 0 Then For i = 1 To AmRest MiCiXiAi(i, 4) = -1 ‘MiCiXiAi(i, 4) = Nothing Next i Irow = 0 Else Cslave = -1 Islave = 0 For i = 1 To AmRest If Tsimp(i, Icol) <> 0 Then If Tsimp(i, 0) = 0 Then Wrk = IIf(Sgn(Tsimp(i, Icol)) = 1, 0, -1) Else Wrk = Tsimp(i, 0) / Tsimp(i, Icol) End If MiCiXiAi(i, 4) = Wrk If Wrk >= 0 And Islave = 0 Then Cslave = Wrk Islave = i ElseIf Wrk >= 0 Then If DirectCycle Then If Wrk < Cslave Then ’оставлять из равных первый Cslave = Wrk Islave = i End If Else If Wrk <= Cslave Then ‘оставлять из равных последний Cslave = Wrk Islave = i End If End If End If Else MiCiXiAi(i, 4) = -1 End If Next i Irow = Islave End If End Sub Private Sub CommandButton2_Click() ‘Совершить итерацию Dim Welm As Double MiCiXiAi(Irow, 1) = Tsimp(AmRest + 3, Icol) MiCiXiAi(Irow, 2) = Tsimp(0, Icol) MiCiXiAi(Irow, 3) = Icol Welm = Tsimp(Irow, Icol) For i = 1 To AmRest + 2 If i <> Irow Then For j = 0 To MaxX If j <> Icol Then Tsimp(i, j) = Tsimp(i, j) - (Tsimp(i, Icol) / Welm) * Tsimp(Irow, j) End If Next j End If Next i For j = 0 To MaxX Tsimp(Irow, j) = Tsimp(Irow, j) / Welm Next j For i = 1 To AmRest + 2 Tsimp(i, Icol) = 0 Next i Tsimp(Irow, Icol) = 1 FRowCol If Cycle() Then LookResult “Итерации зациклились на итерации №” & CStr(NumIter - 1), 11 ElseIf Icol > 0 And Irow > 0 Then LookResult “Смотри итерацию №” & CStr(NumIter - 1), 50 ElseIf Icol > 0 And Irow <= 0 Then LookResult “Функция не ограничена”, 28 Else LookResult “Оптимальный план”, 37 End If End Sub Private Sub FRowCol() ‘Поиск разрешающих строки и столбца If MaxLi Then CalcColL ’max Else CalcColB ’ min End If CalcRow ’X0/Xi If Icol > 0 And Irow > 0 Then CommandButton2.Visible = True NumIter = NumIter + 1 CommandButton2.Caption = “Произвести итерацию №” & CStr(NumIter) Else NumIter = NumIter + 1 CommandButton2.Visible = False End If End Sub Private Function Cycle() As Boolean ‘Если “Верно” зациклились. If “True” were looped. Dim CurrentPlan As String Dim i As Integer Cycle = False CurrentPlan = “” For i = 1 To AmRest CurrentPlan = CurrentPlan & CStr(MiCiXiAi(i, 3)) Next i If InStr(AllPlans, CurrentPlan) > 0 Then If DirectCycle = True Then DirectCycle = False Else Cycle = True End If AllPlans = “” Else AllPlans = AllPlans & ” ” & CurrentPlan End If End Function Заключение В данной работе рассматриваются два способа решения исходной задачи линейного программирования. Первый заключается в том, что сначала решается вспомогательная задача (L-задача), позволяющая построить начальный опорный план, затем на основе этого найденного плана решается исходная задача (определяется ее оптимальный план). Второй способ является объединением двух этапов и состоит в решении расширенной задачи (M-задачи), также приводящей к нахождению оптимального плана исходной задачи. Вычислительную основу этих двух способов решения составляют соответственно первый и второй алгоритмы симплекс-метода. Один из параметров, по которому может быть оценен любой итерационный алгоритм – количество шагов, приводящих к решению задачи или установлению ее неразрешимости. Для данной задачи наиболее эффективным методом оказался первый метод(L-задача + исходная задача), т.к. он привел к решению за 4 шага, а второй метод (M-задача) за 5 шагов. Разница в числе шагов, вероятно, обусловлена неоднозначность выбора разрешающего элемента в исходной таблице L-задачи. Сравнение количества вычислений на каждой итерации приводит к следующим оценочным результатам рассматриваемых алгоритмов. Преимущественная часть вычислений на каждом шаге алгоритмов определяется размерностью главной части таблицы (в первом алгоритме) или основной таблицы (во втором алгоритме). В первом случае она имеет размерность (m+1)x(n+1), во втором - (m+1)x(m+1). Даже учитывая, что второй алгоритм требует построения вспомогательной таблицы, он оказывается более компактным. Еще одно несомненное достоинство второго алгоритма заключается в возможности определения оптимального плана двойственной задачи из (m+1)-й строки основной таблицы, соответствующей последней итерации, без всяких дополнительных вычислений. Список использованных источников Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Высшая школа, 2001. Аронович А.Б., Афанасьев М.Ю., Суворов Б.П. Сборник задач по исследованию операций. – М.: Издательство Московского университета, 1997. Исследование операций в экономике /Под ред. Кремер. – М.: ЮНИТИ, 1997. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. – М.: Высшая школа, 1986. Шикин Е.В., Чхартишвили А.Г. Математические методы и модели управления. – М.: Дело, 2000. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. – М.: Мир, 1984. Липски В. Комбинаторика для программистов. – М.: Мир, 1988. 30 |