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

Разработка  учебно-методического комплекса (умк)  по разделу «решение задач линейного программирования» 

Моделирование является одним из способов изучения окружающей действительности. Человек сможет мыслить образами, приближенно отражающими реальность. Любое абсолютное знание, абсолютная истина познаются через бесконечную цепочку относительных приближенно отражающих те или иные черты объективной реальности истин - моделей.

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

Математические знания необходимы и будущим биологам, и филологам, экономистам и юристам, агрономам и инженерам.

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

Таким образом, наряду с изучением основных разделов математики, становится актуальным вопрос о приложении математики.

Основная часть математических моделей, рассматриваемых в данном курсе, базируется на материале, не входящем в школьную программу 10-11-х классов. Это простейшие задачи линейного программирования, транспортные задачи, а также задачи экономического содержания. Вместе с тем они основываются на традиционном материале курса математики (функциях, уравнениях, неравенствах, последовательностях), что способствует развитию

математических знаний и умений по темам «Неравенства», «Функция», «Прогрессия».

2.1. Пояснительная записка

Моделирование процессов оптимального планирования (19 ч)

По мере развития науки и техники перед человеком все чаще встает вопрос: «Как найти правильное решение?». Для облегчения решения этой задачи реальные процессы (или объекты) заменяют их аналоговыми или моделями.

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

В сфере управления сложными системами (например, в экономике) применяется оптимизационное моделирование, в процессе которого осуществляется поиск  наиболее оптимального пути развития системы.

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

Использование компьютера для исследования информационных моделей различных объектов и систем позволяет изучить их в зависимости от значения тех или иных параметров. Процесс разработки моделей и их исследование на компьютере можно разделить на несколько этапов:

• построение описательной информационной модели;
• формализация модели;
• построение компьютерной модели;
• проведение компьютерного эксперимента;
• анализ полученных результатов.

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

Основная цель : сформировать умения решать основные задачи линейного программирования основными методами математического исследования.

Задачи:

1. Познакомить студентов с методами математического исследования.

2. Сформировать умения и навыки:

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

3. Способствовать:

• формированию мотивации;
• развитию логического мышления, самообразования

Категория обучаемых: студенты колледжа,   специальности 050202 «Информатика» и 230701 «Прикладная информатика по отрасли «Образование)»  и также студенты и учащиеся старших классов, интересующиеся математическими методами решения экономических, производственных и управленческих задач. 

Лекционно-семинарская форма занятий позволяет студенту адаптироваться к вузовскому изложению материала и помогает ему получить основные навыки вузовской учебной деятельности.

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

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

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

Оценка «5» демонстрирует сознательное и ответственное отношение, сопровождающееся ярко выраженным интересом к учению, освоение теоретического материала и получение навыков решения основных задач ЛП, показал умение работать самостоятельно.

Оценка «4» показывает, что учащийся может справиться со стандартом, выполнить данные задачи прилежно (без проявления творческих способностей).

Оценка «3» определяет освоение наиболее простых идей и методов курса, умение выполнять простые задания.

Оценка «2» оценивает учащихся, не проявляющих интереса и не справляющихся с решением простых задач.

Учебно-тематический план.

Содержание курса. 

Введение

Тема 1. Постановка задач оптимального планирования. Линейное программирование — введение.

Понятие математических моделей. Определение математического моделирования. Понятие целевой функции, системы ограничений.

Тема 2: Определение линейного программирования. Существование и единственность решения.

Графический метод

Тема 3. Графический метод решения задач.

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

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

Использование программных средств при решении задач

Тема 5. Возможности табличного процессора Excel для решения задач линейного программирования, встроенные функции.

Тема 6. Возможности математического пакета MathCAD для решения задач линейного программирования.

Симплексный метод

Тема 7. Симплекс-метод.

Идея симплексного метода как метода последовательного улучшения. Понятие базисного решения. Фундаментальная теорема линейного программирования. Симплексная таблица. Отыскивание начального базиса, понятие искусственного базиса.

Тема 8.         Алгоритм решения задач симплексным методом.

Тема 9. Использование языков программирования (Visual Basic, Turbo Pascal) для реализации симплекс-метода.

2. 2. Разработки занятий

Тема: Постановка задач оптимального планирования. Линейное программирование: введение.

Планирование является важным элементом экономической деятельности при любых принципах организации экономики.

Для решения конкретной экономической проблемы планирования существует много способов, и отбор наилучшего из них (согласно заданным требованиям) является важной задачей. Указанный наилучший способ называется оптимальным. Объектом планирования может быть деятельность отдельного предприятия, отрасли промышленности, и даже государства в целом.

Постановка задачи планирования выглядит следующим образом:

• имеется набор плановых показателей {Х};
• имеется набор ресурсов {R} , за счет которых эти плановые показатели могут быть достигнуты, и заданы ограничения по каждому виду ресурсов;
• имеется определенная стратегическая цель, зависящая от значения плановых показателей, на которую следует ориентировать планирование.

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

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

Приведем несколько примеров.

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

Рассмотрим простой пример, из которого можно получить представление о математическом моделировании в задачах оптимального планирования.

Пусть станция технического обслуживания автомобилей выполняет два вида обслуживания: ТО-1 и ТО-2. Автомобили принимаются в начале рабочего дня и выдаются клиенту в конце дня. В силу ограниченности площади стоянки за день можно обслужить в совокупности не более 140 автомобилей. Рабочий день длится 8 часов. Если бы все автомобили проходили только ТО-1, то мощности станции позволили бы обслужить 200 автомобилей в день, если бы все автомобили проходили только ТО-2, то 50 автомобилей в день. Стоимость (для клиента) ТО-2 вдвое выше, чем ТО-1. Реально за день часть автомобилей проходит ТО-1, а часть – ТО-2. Требуется составить такой дневной план обслуживания, чтобы обеспечить предприятию наибольшие денежные поступления.

Построим математическую формулировку задачи. Плановыми показателями являются:

х - дневной план выполнения ТО-1;

у -  дневной план выполнения ТО-1.

Из условий задачи ресурсами являются:

• длительность рабочего дня – 8 часов;
• вместимость стоянки – 140 мест.

Из постановки задачи следует, что на ТО-2 затрачивается в 4 раза больше времени, чем на ТО-1. Если обозначить продолжительность ТО-1 как t минут, то продолжительность ТО-2 составит 4t минут. Отсюда следует, что суммарное время на выполнение x обслуживаний ТО-1 и y обслуживаний ТО-2 равно:

tx + 4ty = (x + 4y)t.

Но это время не может быть больше длительности рабочего дня. Отсюда следует:

(x +4y)t < 8*60 (минут)

Подсчитаем время t  для выполнения ТО-1. Поскольку за рабочий день обслуживаний вида ТО-1 может быть выполнено 200, то на одно ТО-1 тратится 480/200 = 2,4 (минут). Подставляя значение в неравенство, получим:

(x + 4y) * 2,4 <480

x + 4y < 200.

Полученное значение 2,4 минуты является не физическим временем выполнения одного ТО-1, поскольку оно требует гораздо большего времени, а среднем временем для данной станции, имеющей несколько боксов.

Составим ограничение на вместимость стоянки:

x +y < 140

К двум полученным неравенствам следует добавить условия положительности значений величин x и y (число автомобилей не может быть отрицательным). В конечном итоге получим систему неравенств:

А теперь перейдем к формализации стратегической цели: получить максимальные денежные поступления. Пусть стоимость выполнения одного ТО-1 составляет r рублей. По условиям задачи стоимость выполнения одного ТО-2 в два раза больше, т.е. 2r рублей. Отсюда полная выручка предприятия за день равна

rx + 2ry = r(x +2y).

Поскольку r – константа, то максимальное значение полной выручки будет достигнуто при максимальном значении

f(x,y) = x+2y.

В задачах оптимизации функцию, экстремум которой необходимо найти, называют целевой функцией, а систему неравенств (или уравнений) – системой ограничений.

Получение оптимального плана свелось к следующей математической задачи: найти значения плановых показателей x и y, удовлетворяющих системе ограничений и придающих максимальное значение целевой функции.

Математическая дисциплина, которая посвящена решению задач данного типа, называется математическим программированием. Внутри этой дисциплины выделяется линейное программирование, предназначенное для решения класса задач, в которых в целевую функцию и в систему ограничений  переменные входят линейно.

Тема: Общая формулировка и существование решения задач линейного программирования.

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

• эти значения были неотрицательны;
• эти значения удовлетворяли системе линейных уравнений или линейных неравенств;
• при этих значениях некоторая линейная функция имела минимум (или максимум).

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

Запишем это определение с помощью формул. Дана система линейных уравнений и неравенств:

и линейная функция         

Требуется найти такое неотрицательное решение   

системы, чтобы функция f  принимала наименьшее (или наибольшее) значение.

Существование и единственность решения задач линейного программирования.

Рассмотрим на примере задачи с двумя переменными, как может сложиться ситуация с разрешимостью задач линейного программирования. Пусть переменные x, y  удовлетворяют m ограничениям-неравенствам

 и стандартным ограничениям

Требуется отыскать экстремум линейной функции f = ax+by.

 Каждое из неравенств на координатной плоскости выделяет полуплоскость; то же делают стандартные ограничения.

Возможны лишь три разных случая расположения этих полуплоскостей:

• система ограничений не имеет общих решений (несовместна);
• система ограничений совместна и порождает замкнутую область;
• система ограничений совместна и порождает незамкнутую область.

Рис. 1 Иллюстрация к различным ситуациям системы ограничений

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

На рис.1,б пересечение полуплоскостей образуют многоугольник. Будем перебирать значения f в уравнении f =ax+by и получим семейство параллельных прямых, одна из которых будет соответствовать наибольшему, а другая - наименьшему значению f с учетом наличия ограничений. В этом случае могут быть две разные ситуации (рис.2,а,б).

М

М

Рис.2 Иллюстрации к единственности и множественности решений.

Пунктирные линии на рис.2 – семейство прямых  f=ax+by, при возрастании значения f прямые смещаются вправо: искомая прямая соприкасается с многоугольником лишь с одной вершиной или вдоль стороны. В случае, показанном на рис.2,а, задача имеет единственное решение, соответствующей точке касания пунктирной прямой многогранника в его вершине, в случае на рис.2,б – бесконечное множество решений: координаты любой из точек линий соприкосновения, если пунктирная прямая оказалась параллельной стороне многогранника.

В случае, изображенном на рис.1,в (неограниченная многоугольная область), возможны как варианты, подобные изображенным на рис.2,а,б, так и еще один: пунктирные прямые, смещаясь с увеличением f, никогда не  выйдут за пределы многогранника.  В этом случае задача линейного программирования не имеет решения – линейная функция не ограничена сверху.

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

• единственное решение;
• бесконечное множество решений, соответствующих одному и тому же (оптимальному) значению линейной функции;
• не имеет решения по одной из двух причин: несовместности системы ограничений или неограниченности линейной функции.

Тема: Графический метод решения задач линейного программирования.

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

Неравенство  определяет граничную прямую , которая делит плоскость на две полуплоскости: положительную и отрицательную .

Для того чтобы построить ограничение-неравенство, необходимо построить граничную прямую  по двум точкам, а затем определить полуплоскость, удовлетворяющую данному неравенству. Если полуплоскость не проходит через начало координат, то удобно в неравенство подставить координаты точки начала координат – О (0;0). Если неравенство при этом выполняется, то начало координат входит в полуплоскость. При невыполнении неравенства начало координат не входит в искомую полуплоскость. Если начало координат принадлежит граничной прямой, то для определения искомой полуплоскости подставляю в данное неравенство координаты любой точки, не принадлежащей граничной прямой.

Пример:

Необходимо определить полуплоскость для неравенства . На плоскости координат строим граничную прямую, определяемую равенством , по двум точкам А (0; 3) и В (2; 0). Граничная прямая не проходит через начало координат, поэтому подставляем координаты точки О (0; 0) в неравенство. Получаем верное неравенство 3*0+2*0<6 (0<6), следовательно, начало координат входит в полуплоскость неравенства . Полуплоскость, удовлетворяющую неравенству, будем отмечать штриховкой.

Область допустимых решений.

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

Пример.

Требуется определить область допустимых решений в задаче:

Совхоз для производства двух видов продукции использует четыре вида производственных ресурсов.

  Ресурсы могут быть недоиспользованы. Найти такое соотношение видов продукции, которое обеспечит максимальный выход продукции.

Введем обозначения:          x1 – продукции I вида,

                        x2 – количество продукции II вида,

                        Z – целевая функция.

Составим с помощью математических выражений условие задачи        

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

Первая граничная прямая проходит через точки (0; 6) и (6; 0). Начало координат входит в полуплоскость первого неравенства. Вторая граничная прямая проходит через точку (0; 5) и (8; 0).  Начало координат входит в полуплоскость второго неравенства. Третья граничная прямая проходит через точки (0; 4) и (10; 0). Начало координат принадлежит полуплоскости третьего неравенства. Четвертая прямая проходит через точку (5; 0) параллельно оси Ох2. Условию неотрицательности переменных (5) и (6) соответствует первая четверть координатной прямой. Областью допустимых решений является прямоугольник ОАВСД.

Целевой функции Z можно придать любое значение и построить прямую, соответствующую полученному выражению. Прямая, полученная таким способом, называется линией уровня. Так как целевой функции можно придать бесчисленное множество значений (действительных), то можно построить бесчисленное множество линий уровня. Все линии уровня параллельны между собой. Направление максимизации целевой функции показывает вектор-градиент. Начальная точка вектора-градиента совпадает с началом координат плоскости. Координаты конечной точки равны частным производным выражения целевой функции . Вектор-градиент и линия уровня взаимно перпендикулярны между собой. Существует два способа направления вектора-градиента и линий уровня.

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

Второй способ. Целевой функции придаем два различных действительных значения. Для полученных выражений строим две линии уровня. В любой точке любой линии уровня строим вектор, перпендикулярный линии уровня и показывающий направление максимизации целевой функции.

В нашей задаче придаем целевой функции значения Z=10 и Z=20. Получаем уравнения прямых: 2х1+5х2=10 и 2х1+5х2=20.

Оптимальное решение.

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

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

У нас в рассматриваемой задаче оптимальное решение достигается на отрезке АВ. Координаты точки А легко определить по чертежу. Найдем координаты точки В. Решим совместно уравнения тех прямых, которые пересекаются в данной точке. В точке В пересекаются первая и третью граничные прямые, поэтому решим совместно первое и третье уравнения:

Вычтем из второго уравнения первое, получим 1,5х2=4, откуда , .

Значение целевой функции в точке А (0; 4) Z=2·0 + 5·4=20, это же значение имеет целевая функция в точке : . Значение Z=20 является наибольшим из всех возможных.

Если линия уровня в своем крайнем положении параллельна одной из сторон области допустимых решений, то параллельность необходимо проверить: коэффициенты при перемещении у параллельных прямых пропорциональны. В нашей задаче линия уровня параллельна третьей граничной прямой, коэффициенты переменных у них пропорциональны: Z= 2x1 + 5x2 и х1 +2,5х2 = 10        2:1 = 2; 5:2,5 = 2.

Выводы:

1. Областью решения задачи линейного программирования является, либо ограниченный выпуклый многоугольник, либо неограниченная выпуклая многогранная область.

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

3. Если задача линейного программирования не имеет решения, то это происходит:

а) из-за несовместимости системы ограничений;

б) из-за неограниченности целевой функции.

Тема: Графо-аналитический метод решения задач линейного программирования с помощью Ms Excel.

Самостоятельная работа.

Задание: решить графическим методом.

1.                         2.                         3.

(Ответы: 1). Zmax=2, x1=0, x2=2        2). Zmax= - 0,6; x1=2, x2=1,8        3). Zmax=2, x1=0, x2=2).        

Задача линейного программирования состоит в нахождении наибольшего или наименьшего значения линейной целевой функции F=C1X1+ …+CnXn в области n-мерного пространства, заданной посредствам системы неравенств:

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

Лабораторная работа №1.

Рассмотрим применение Ms Excel при моделировании  решения задач графо-аналитическим методом при n=2.

Пусть область допустимых решений имеет форму треугольника (m=3).

Целевая функция  f=2x1+x2

а область допустимых решений задана неравенствами:         

Требуется найти минимальное значение целевой функции F  при заданных ограничениях.

По условию задачи область решений полностью находится в первом квадранте системы координат. Заменяя в неравенствах знаки «меньше» и «больше» на знак равенства, получаем уравнения прямых границ области допустимых решений

Для построения границ области достаточно определить координаты вершин треугольной области допустимых решений. Группируем попарно уравнения и решаем системы с помощью формул Крамера для нахождения координат пересечения прямых.

Например, для системы уравнений в общем виде:

a11x1+a12x2 = b1   

a21x1+a22x2 = b2   

решения получаем по формулам:

x1 = (b1a22 – b2a12)/ (a11a22 – a21a12)

x2 = (b1a11 – b2a21)/ (a11a22 – a21a12)

В таблицу занесены коэффициенты прямых и координаты точек пересечения первой и второй прямых, второй и третьей, третьей и первой  (D4:E6):

- в ячейку D4 занесена формула =(C4*B5-C5*B4)/(A4*B5-A5*B4)

• в ячейку E4 =(C5*A4-C4*A5)/(A4*B5-A5*B4)

 Для замыкания контура треугольника на графике в конце перезаписываем координаты первой расчетной точки пересечения прямых (D7:E7):

- в ячейку D7 записана формула =D4

- в ячейку E7:  =E4 

Перед обращением к Мастеру диаграмм выделяем диапазон ячеек D4:E10 с учетом построения в дальнейшем линии уровня целевой функции. Выбираем тип диаграммы Точечная и вид, где значения соединены отрезками. Чтобы графики и линии были отображены раздельно, ячейки с их координатами отделяем строкой.  

Для построения линии уровня целевой функции задаем начальное значение функции F0 (C13). Записав значение  коэффициентов С1 и С2 целевой функции и начальное значение, можно по заданному значению Х1 вычислить соответствующие координаты Х2 с помощью формулы Х2 = (F0 – C1X1)/C2  для двух концов линии уровня. 

Определим координаты концов линии уровня (D9:E10):

- в ячейки D9 и D10 введем произвольные значения

- в ячейку F9 введена формула =($C$13-$A$13*D9)/$B$13 и скопирована в ячейку F10

 получим изображение линии на графике.

Выбранное значение Х1 можно откорректировать для обеспечения более наглядного расположения линии уровня относительно области допустимых решений. Теперь остается изменять значение F0 для моделирования перемещения линии уровня функции в сторону области решения. При этом линия уровня целевой функции будет смещается параллельно своему начальному положению. Смещение производится до первого соприкосновения с областью допустимых решений. В нашем случае минимальное значение целевой функции равно 3,75, при х1=0 и х2=3,75.

Тема: Использование средства «Поиск решения» табличного процессора Excel для решения задач линейного и нелинейного программирования.

Решение задач оптимального планирования небольшого объема возможно без использования компьютера. Однако практически все важные задачи чаще всего содержат большое число переменных и ограничений, и «ручное» решение становится практически невозможным. Следует либо самостоятельно составить программу для компьютера на одном из языков программирования высокого уровня, либо прибегнуть к использованию готовой программы.

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

Средство, в состав которого входит программа оптимизации, называется Поиск решения. Соответствующая команда находится в меню Сервис. Поиск решения – одно из самых мощных средств табличного процессора Excel.

Лабораторная работа №2.

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

Пусть станция технического обслуживания автомобилей выполняет два вида обслуживания: ТО-1 и ТО-2. Автомобили принимаются в начале рабочего дня и выдаются клиенту в конце дня. В силу ограниченности площади стоянки за день можно обслужить в совокупности не более 140 автомобилей. Рабочий день длится 8 часов. Если бы все автомобили проходили только ТО-1, то мощности станции позволили бы обслужить 200 автомобилей в день, если бы все автомобили проходили только ТО-2, то 50 автомобилей в день. Стоимость (для клиента) ТО-2 вдвое выше, чем ТО-1. Реально за день часть автомобилей проходит ТО-1, а часть – ТО-2. Требуется составить такой дневной план обслуживания, чтобы обеспечить предприятию наибольшие денежные поступления.

Система ограничений имеет вид

Целевая функция f(x,y) = x+2y

Вначале подготовим таблицу для решения задачи оптимального планирования. Таблица отображена в режиме отображения формул.

Ячейки В5 и С5 зарезервированы для значений x (план по выполнению ТО-1) и y (план по выполнению ТО-2). Ниже в электронной таблице представлена система неравенств, определяющая ограничения на искомое решение. Неравенства разделены на левую часть (столбец В) и правую часть (столбец   D). Знаки неравенств в столбце С записаны в целях иллюстрации, для понятности. Целевая функция занесена в ячейку В15.

Теперь вызовем программу оптимизации. Для этого выполним команду Сервис – Поиск решения. На экране появится соответствующая форма (рис.1).

Рис.1 Начальное состояние формы Поиск решения.

Выполним следующую последовательность действий:

• введем адрес ячейки с целевой функцией. В нашем случае это В15 (если перед этим установить курсор на ячейку В15, то ввод произойдет автоматически);
• установим флажок максимальному значению, т.е. сообщим программе, что нас интересует нахождение  максимума целевой функции;
• в поле Изменяя ячейки введем $B5:$C5, т.е. сообщим, какое место в таблице отведено под значения переменных – плановых показателей;
• в поле Ограничения надо ввести информацию о неравенствах-ограничениях, которые имеют вид: $D10<=$D10; $D11<=$D11; $B12>=$D12; $B13>=$D13.  Ограничения вводятся следующим образом:

• щелкнуть по кнопке Добавить;
• появится диалоговое окно Добавление ограничения

•  в данном окне ввести ссылку на ячейку В10, выбрать в меню знак неравенства <=  и ввести ссылку на ячейку D10;
• снова щелкнуть по кнопке Добавить и аналогично ввести второе ограничение $B11<=$D11 и т.д.;
• когда будут добавлены все ограничения, щелкнуть по кнопке ОК;

• закроем диалоговое окно Добавление ограничения. Перед нами снова появится окно Поиск решения (см.рис.2);

Рис. 2 Форма Поиск решения после ввода информации

• теперь надо дать последние указания: задача является линейной. Для этого щелкнем на кнопке Параметры; появится форма Параметры поиска решения (см.рис.3);

установим флажок Линейная модель. Вместо ввода двух последних ограничений (см.рис.3), указывающих на неотрицательность значений переменных, можно установить флажок Неотрицательные значения. Щелкнем по кнопке ОК, снова появится форма Поиск решения;

Рис.3 Форма Параметры поиска решения

• щелкнем по кнопке Выполнить – в ячейках В5 и С5 появится оптимальное решение (числа 120 и 20), а также в ячейке В15 появится число 160 – максимальное значение целевой функции. Результат проиллюстрирован на рис.4.

Рис.4 Результат решения задачи.

• после нажатия на кнопку Выполнить появится еще одна форма: Результат поиска решения (см.рис.5); нажать кнопку ОК.

Рис.9 Форма Результат поиска решения

В результате применения инструмента Поиск решения получен следующий план дневной работы станции технического обслуживания: нужно выполнить 120 ТО-1 и 20 ТО-2. Если подставить полученные значения x и y в целевую функцию f(x,y)= x+2y, то получим f(120,20) = 120+2*20 =160.

Проведите эксперимент:

- измените длину рабочего дня;

- общее число ремонтов сделайте равным 185.

Тема: Использование средства «Поиск решения» табличного процессора Excel для решения задач линейного программирования.

Лабораторная работа №3.

Задание 1.

Пусть региональный орган управления образованием имеет возможность оказать финансовую поддержку организации экскурсий учащихся для четырех подведомственных учебных заведений. Обозначим эти учебные заведения Р1…Р4.

                                                                        Таблица 1

Число учащихся-экскурсантов

Экскурсии состоятся в пять разных городов, обозначим их Q1 …Q5 , причем каждый учащийся-экскурсант может поехать только в один город. Туристическое агентство, которому поручена организация экскурсий, располагает возможностями распределения учащихся-экскурсантов по городам, отображенными в табл.2. Условие поездки каждого учащегося-экскурсанта ровно в один город отражено в равенстве общего числа учащихся-экскурсантов во всех учебных заведениях общему числу экскурсантов, принимаемому всеми городами.

                                                                                Таблица 2

Число экскурсантов, едущих в каждый город

Данные о стоимостях  экскурсии представлены в табл.3.        

                                                                                                                                                                        Таблица 3

Стоимости экскурсий (для одного ученика)

Число 400 в ячейке, стоящей на пересечении строки Р2 и Q3, означает, что стоимость путешествия одного учащегося из учебного заведения Р2 в город Q3 равна 400 рублей.

Следующая таблица (см. табл.4) – план распределения студентов по экскурсиям, который требуется разработать. Число в последней строке и последнем столбце – сумма чисел по соответствующим строкам и столбцам.

                                                                                                                                Таблица 4

Сводный план распределения учащихся по экскурсии

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

В этой задаче 20 переменных и 9 ограничений-уравнений:

Целевая функция, минимум которой нужно найти, выглядит следующим образом:

S=500x11+700x12+750x13++1000x14+1100x15+700x21+600x22+400x23+500x24+800x25+1200x31+1000x32+800x33+700x34+750x35+1300x41+1200x42+1100x43+900x44+1000x45

Исходные данные:

Матрица переменных занимает массив ячеек А2:Е5. Матрица стоимости перевозок – массив G2:K5. При записи системы ограничений в ячейки А8:А11 и А12:А17, а также целевой функции в ячейку А19 использованы стандартные функции программы Excel – СУММ (сумма) и СУММПРОИЗ (сума произведений).

Воспользуемся сервисом Поиск решения (рис.1)

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

Рис. 1 Форма Поиск решения  (в окне Ограничения         видна только часть соответствующих равенств)

После ввода данных запускаем программу на выполнение. Результат представлен на рис.2.

Рис. 2 Результат работы Поиск решения.

Из учебного заведения Р4 в город Q4 может поехать 150 учащихся.

Задание 2.

Решите самостоятельно с помощью средства Поиск решения следующую задачу: найти максимум функции у = 4х1 + 3х2 при системе ограничений:

Тема: Решение задач оптимизации с помощью пакета MathCAD.

Пакет MathCAD обладает простым интерфейсом. Данная среда не специальная изобретенная программа для решения узкого круга школьных задач, а математический пакет, предназначенный для решения серьезных научных и технических проблем.

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

MathCAD позволяет выполнять как численные, так и аналитические вычисления, имеет удобный математико-ориентированный интерфейс и средства графики.

Пакет MathCAD имеет встроенную программу поиска минимумов и максимумов функций при наличии ограничений на их аргументы. Частным случаем этой ситуации являются задачи линейного программирования.

Функции, реализующие минимизацию и максимизацию, выглядят так:

Minimize (<список аргументов>)

Maximize (<список аргументов>)

Их использование покажем на примерах, рассматриваемых на прошлых занятиях.

Лабораторная работа №4.

Задание 1.

Оптимизация  работы станции технического обслуживания.

Необходимо найти максимум функции f(x,y) = x+2y при наличии системы ограничений  и стандартных систем ограничений, связанных с неотрицательностью переменных

Реализация задачи.  

1. установим указатель мыши и введем целевую функцию, набрав на клавиатуре f(x,y): = x+2*y

2. введем некоторые начальные значения переменных. Введем, например, х: = 0   y:=0

3. сформируем блок данных. Для этого ведем слово Given, щелкнем ниже и введем поочередно ограничения-неравенства. Ввод знаков  осуществляется с помощью кнопки Панель инструментов булево (Логические действия) панели Математика .

4. продолжим формирование блока данных. Введем задание на максимизацию, набрав P:=Maximize (f, x, y). Обозначение Р выбрано произвольно, оно будет восприниматься системой как массив, элементам которого по окончании работы программы будут присвоены значения переменных х и y, найденные в ходе решения задачи.

5. сформируем запрос к системе о результатах решения задачи. Для этого введем с клавиатуры Р. После этого появится текст  - искомые значения переменных х и у. Продолжим запрос: наберем f (P0, P1)= и получим ответ f (P0, P1) =160.

Задание 2. Решите самостоятельно с помощью MathCAD следующую задачу: найти максимум функции у = 4х1 + 3х2

при системе ограничений                

Тема: Решение задач оптимизации с помощью пакета MathCAD.

Лабораторная работа №5.

Задание.  Планирование экскурсионных поездок.

Программы Minimize и Maximize не воспринимают переменные в виде двумерного массива. Поэтому необходимо вытянуть это массив в линейный. Директива ORIGIN:=1 означает, что индексы массивов начинаются с единицы (по умолчанию MathCAD начинает отсчет индексов с нуля). Запись i:=1..20 x(i): =0 реализует задание нулевых значений всем элементам массива х.

Ввод символа «..» осуществляется нажатием клавиши «;».

Чтобы получить знак суммы, надо нажать одновременно три клавиши: Ctrl + Shift + 4.

Ввод символа “: =” (присвоить) осуществляется сочетанием клавиш Ctrl + “;” или нажатием на кнопку   на панели Арифметика.

Знак равенства в выражениях осуществляется нажатием кнопки  на панели Булево.

 Тема: Симплекс-метод.

Для решения некоторых типов задач линейного программирования существуют специальные методы. Но существует и общий метод решения таких задач – симплекс-метод. Он состоит из алгоритма отыскивания какого-нибудь (произвольного) допустимого решения и алгоритма последовательного перехода от этого решения к другому допустимому решению, для которого функция f изменяется в нужном направлении (для получения оптимального решения или вывода, что его не существует).

Пусть система ограничений состоит из уравнений:

и требуется отыскать минимум линейной функции.  

Переменные х1, х2, … хr называются базисными переменными, набор { х1, х2, … хr} – базисом, а остальные переменные { хr+1, xr+2 … хn }– свободными переменными. Выразим функцию f через свободные переменные:

f = c0 + c’r+1xr+1 + c’r+2xr+2 +…+ c’nxn

Положим все свободные переменные равными 0:

хr+1 = xr+2 =…=xn = 0

и найдем из системы уравнений значения базисных переменных:

x1 = b’1  x2 = b’2 …xr = b’r

Полученное таким образом частное решение  b’1,  b’2, … b’r, 0,…,0, соответствующее базису  x1,  x2, …xr, называется базисным решением. Идея симплекс метода заключается в том, чтобы от одного базиса перейти к другому базису с таким результатом, чтобы значение целевой функции f при этом изменялось в нужном направлении (при поиске минимума – уменьшалось, при поиске максимума – увеличивалось).

Пример.

Дана система ограничений:

Требуется минимизировать целевую функцию

В качестве свободных переменных выберем х2 и х3. Тогда данная система ограничений преобразуется к виду:

Таким образом, базисное решение (3, 0, 0, 1). Так как целевая функция уже записана в свободных переменных, то ее значение для данного базисного решения равно нулю. Для уменьшения этого значения можно уменьшить х2 или увеличить х3. Но х2 в данном базисе равно 0, и поэтому его уменьшать нельзя. Попробуем увеличить х3. Первое из уравнений ограничивает х3 значением 1 (из условия ), второе вообще не ограничивает. Таким образом, берем х3 = 1, х2 не меняем и получаем новое допустимое решение (0, 0, 1, 3), для которого f = -1, т. е. значение f уменьшилось.

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

а целевая функция в новых свободных переменных имеет вид:

Для уменьшения f нужно уменьшить либо х1, либо х2, но это невозможно, т. к. в этом базисе х2 = 0 и х2 = 0. Таким образом, данное базисное решение является оптимальным, и минимум функции f равен -1 при х1 = 0, х2 = 0, х3 = 1, х4 = 3.

Алгоритм симплекс-метода в общем виде (для минимизации целевой функции).

Запишем систему ограничений в виде:

причем ,

и функцию f в виде:

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

Составим так называемую симплекс-таблицу.

Сформулируем алгоритм симплекс-метода применительно к данным, внесенным в таблицу.

1. Выяснить имеются ли среди γr+1, … , γn положительные числа. Если все эти числа отрицательны, о процесс закончен; базисное решение (b1, b2,… br, 0,…0) является оптимальным; соответствующее значение целевой функции f = γ0.

Если среди γr+1 ,…, γn имеется хотя бы одно положительное число, перейти к п. 2.

2. Просмотреть столбец, соответствующий положительному числу из указанных выше, и выяснить, имеются ли в нем положительные числа aij. Если ни в одном из таких столбцов положительных чисел нет, то оптимального решения не существует. Если найден столбец, содержащий хотя бы один положительный элемент (если таких столбцов несколько взять любой из них), пометить этот столбец и перейти к п.3.

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

4. Разделить элементы выделенной строки исходной таблицы на разрешающий элемент (на месте разрешающего элемента появится единица). Полученная таким образом строка записывается на место прежней в новой таблице. Перейти к п. 5.

5. Каждая следующая строка новой таблицы образуется сложением соответствующей строки исходной таблицы и строки, полученной в п. 4, которая предварительно умножается на такое чичло, чтобы в ячейках выбранного столбца при сложении появлялись нули. На этом процесс заполнения новой таблицы заканчивается, и переходим к п. 1.

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

Отыскивание начального базиса

Для использования симплекс-метода требуется, чтобы система ограничений  

была приведена к виду 

где , т. е чтобы был получен начальный базис х1, …, хr. Один из методов получения начального базиса – метод искусственного базиса.

Рассмотрим систему . Если в ней некоторые из свободных членов в правой части отрицательны, то умножим соответствующее уравнение на (-1), и после этого окажется, что все . Введем искусственные переменные у1, у2, …, уm:

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

Введем вспомогательную линейную форму: F = у1+ у2+ …+ уm и займемся ее минимизацией с использованием системы ограничений:

Поскольку величины у1, у2, …, уm считаются неотрицательными, то минимум формы очевиден – это ноль, причем он достигается при у1=0, у2=0, …, уm = 0. Достигнув его в ходе симплекс-преобразований и устранив искусственные переменные, мы получим стартовый вид симплекс-метода исходной задачи линейного программирования.

Если в ходе решения вспомогательной задачи выяснится, что min F >0, то это свидетельствует о несовместимости исходной системы ограничений (и, тем самым, об отсутствии решения исходной задачи).

Пример.

Требуется привести систему ограничений к виду, пригодному для использования симплекс-метода (т. е. выделить некоторый базис).

Система имеет вид:

Выделим искусственные переменные:

Введем вспомогательную линейную форму:

        F = у1+ у2 + у3 = 10-(-2x3+4x4)

Заполним первую симплекс-таблицу:

Поскольку в последней строке есть лишь дин положительный коэффициент, то ищем разрешающий элемент в соответствующем столбце. Отношения свободных членов к (положительным) коэффициентам в этом столбце равны, соответственно, 1/2, 4/1, 5/1. Согласно алгоритму, разрешающий элемент соответствует наименьшему из этих отношений, он выделен в таблице жирным шрифтом – это элемент 2.

Далее переходим  новому базису, в котором переменная у1 замещена на x4. Для этого выполним пункты 4 и 5 приведенного выше алгоритма, после чего получаем следующую симплекс-таблицу. С ней выполняем аналогичные операции.

В последней таблице достигнут минимум формы F (равный нулю), а в базисе – лишь исходные переменные из набора {x}. Таким образом, опуская значения переменных {y}, получаем систему уравнений, пригодную для применения симплекс-метода по отношению к исходной задаче:        

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

Тема: Алгоритмическая реализация симплекс-метода.

Для начала сформулируем алгоритм симплекс-метода на естественном языке.

1. Найти первое базисное решение.
2. Проанализировать его на оптимальность.
3. Если оно не является оптимальным, то проанализировать является ли ограниченной линейная форма.
4. Если линейная форма является ограниченной, то найти в таблице разрешающий элемент и произвести симплекс-преобразование (переход к другому базису и, соответственно, к другой таблице).

Описанную процедуру представить  в виде схемы.

На этой схеме фигурирует логическая величина Р, по значению которой определяется, повторять тело цикла или выйти из него. Тело цикла (действия симплекс-метода) повторяется до тех пор, пока либо не будет получено оптимальное решение, либо вывод, что его не существует. Те фрагменты алгоритма, которые изображены в виде, означают необходимость детализации.

Для большей детализации необходимо условиться, как расположена информация в обрабатываемых объектах. Учитывая структуру симплекс-таблиц, расположим эту информацию в виде матрицы (двумерного массива). Матрица будет иметь следующий вид:

Нумерация строк матрицы указана слева от нее (от 1 до r + 2), столбцов – над ней (от 1 до п + 2). В первом столбце матрицы числа – номера переменных, обозначающих первый базис (по мере симплекс преобразований они замещаются на номера других переменных).

Для записи алгоритм удобнее более единообразная система обозначений элементов матрицы. Введем двумерный массив di,j (i – номер строки,  j – столбца).

Анализ оптимальности базисного решения удобно совместить с анализом того, является ли линейная форма ограниченной. Если по завершении исполнения алгоритма р=’да’, то решение оптимально, если р=’нет’ и q=’нет’, то оптимального решения не существует, если р=’нет’ и q=’да’, то m -  номер столбца, в котором можно искать разрешающий элемент, а k – номер строки, в которой в столбце m  находится положительный элемент.

Разрешающий элемент ищется в столбце номер m, при этом используется то, что элемент dkm положителен. Результат работы – числа k (номер строки) и m (номер столбца), определяющие местонахождение разрешающего элемента.

Тема: Программная реализация симплекс-метода в VBA.

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

Реализуем программу симплекс-метода на VBA. Эта программа реализует циклическое преобразование симплекс-таблиц до тех пор, пока не будет получен результат: либо оптимальное значение линейной формы, либо тот факт, что оптимального решения не существует.

Обсудим некоторые технические детали программы, связанные с особенностями взаимодействия VBA и Excel.

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

Привязка переменных, используемых в программе на VBA, к ячейкам Excel может делаться по-разному. Для простой переменной директива a=Range(“d3”) означает, что переменной а будет присвоено значение, находящееся в ячейке d3. При этом подразумевается, что мы работаем с текущим листом Excel; если это не так, то используется уточняющая инструкция a = Range(“Лист№! d3”). Для того чтобы после завершения работы программы отобразить значение некоторой переменной в ячейке Excel, необходимо записать аналогичную директиву, но в обратном порядке:  Range (“Лист№! d3”) = k

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

For i = 1 To 5

For j = 1 To 9

        d (i, j) = Range (“a6:i10”).Cells (i, j). Value

Next j

Next i

Значения элементов массива будут взяты из прямоугольного блока ячеек Excel a6:i10

Лабораторная работа №6.

Программная реализация симплекс-метода на языке Visual Basic.

1. Запустить приложение Ms Excel и заполнить исходную таблицу.

2. Выполнить команду Вид – Панель инструментов – Элементы управления

Программа

Option Explicit

Option Base 1

Private Sub CommandButton1_Click ()

Dim d (5, 9) As Variant

Dim I, j, r, n, k, m As integer

Dim p, q, t As String

Dim a, b As Double

For I = 1 To 5

For j = 1 To 9

        d (i, j) = Range (“a6:i10”).Cells (i, j). Value

Next j

Next i

n = 7: r = 3

‘ Анализ оптимальности текущего решения и существования оптимального решения

t = “далее”

Do While t = “далее”

        p = “да”: q = “нет”

                For j = 3 To n + 2

                        if d (r + 2, j) > 0 Then

                                                                p = “нет”

                                For I = 2 To r + 1

                                                if d (I, j) > 0 Then

                                                                                        q = “да”: m = j: k = i

                                                End if

                                        Next i

                        End if

                Next j

if p = “да” Then

        Range (“a12”)        = “Данное решение является оптимальным:”:

        t = “конец”

        End if

        if (p = “нет” And q = “да”) Then

        Range (“a12”)        = “Оптимального решения не существует:”:

        t = “конец”

End if

if t = “далее” Then

        ‘Поиск разрешающего элемента

                a = d (k, 2) / d (k, m)

        For I =2 to r + 1

                if d (i, m) >0 Then

                        b = d (i, 2) / d (i, m)

                                if b

                                        a = b: k = i

                                End if

                End if

        Next i

‘Симплекс-преобразование

        d (k, 1) = d (1, m): a = d (k, m)

        For j = 2 to n + 2

                        d (k, j) = d (k, j) / a

        Next j

        For I = 2 to r + 2

                a = d (i, m)

                if i <> k Then

                        For j = 2 to n + 2

                                        d (i, j) = d (i, j) – a * d (k, j)

                        Next j

                End if

        Next i

        For i = 1 To 5

        For j = 1 To 9

                                Range (“a14:i18”). Cells (i, j). Value = d (i, j)

        Next i

        Next j

End if

Loop

End Sub

6. Сохранить программу

7. Выполнить команду Сервис – Макрос – Начать запись. Щелкнуть по кнопке и остановить запись

8. Выполнить команду Сервис – Макрос – Макросы

9. В появившемся окне выделить необходимый макрос нажать на кнопку Выполнить.

10. Запустите программу на выполнение. Сохраните.

Тема: Реализация симплекс-метода на языке Turbo Pascal.

Лабораторная работа №7.

Program Simplex;

{Решение задач линейного программирования симплекс-методом. Число переменных n, в базисе переменных r, симплекс таблица  r + 2  x  n + 2}

Const n=7; r =3;

Var c, d: array [1..r+2, 1..n+2] of real;

        i, j, k, m: integer;

        p, g, t: string;

        a, b: real;

begin

c[1,1]: = 0; c[1,2]: = 0; c[1,3]: = 1; c[1,4]: = 2; c[1,5]: = 3; c[1,6]: = 4;

c[1,7]: = 5; c[1,8]: = 6; c[1,9]: = 7;

c[2,1]: = 1; c[2,2]: = 1; c[2,3]: = 1; c[2,4]: = 0; c[2,5]: = 0; c[2,6]: = 3;

c[2,7]: = -5; c[2,8]: = 1; c[2,9]: = 2;

c[3,1]: = 2; c[3,2]: = 4; c[3,3]: = 0; c[3,4]: = 1; c[3,5]: = 0; c[3,6]: = 2;

c[3,7]: = 2; c[3,8]: = -1; c[3,9]: = 1;

c[4,1]: = 3; c[4,2]: = 5; c[4,3]: = 0; c[4,4]: = 0; c[4,5]: = 1; c[4,6]: = -1;

c [4,7]: = 3; c[4,8]: = -2; c[4,9]: = 1;

c[5,1]: = 0; c[5,2]: = 10; c[5,3]: = 0; c[5,4]: = 0; c[5,5]: = 0; c[5,6]: = 0;

c [5,7]: = 0; c[5,8]: = -2; c[5,9]: = 4;

For i: = 1 to r + 2 do

For j: = 1 to n + 2 do

        d [i, j]: = c[i, j];

t: = ‘далее’;

While t = ‘далее’do

        begin

                p: = ‘да’; q: = ‘нет’;

                {Анализ оптимальности текущего решения и существования                                                 оптимального решения}

For j: = 3 to n + 2 do

        if d[r + 2, j] >0 then

                begin

                        p: = ‘нет’;

For i: = 2 to r + 1 do

        if d [i, j]>0 then

                begin

                q: =’да’; m: = j; k: = i;

                end;

end;

if p = ‘да’ then

        begin

                Writeln (‘Данное решение является оптимальным’);

                t: = ‘конец’;

        end;

if ((p = ‘нет’) and (q = ‘нет’)) then

        begin

                Writeln (‘Оптимального решения не существует’);

                t: = ‘конец’;

        end;

if t = ‘далее’ then

        begin

        {Поиск разрешающего элемента}

                a: = d[k, 2]/ d[k, m];

        For i: = 2 to r + 1 do

                if d [i, m]>0 then

                        begin

                                b: = d [i, 2]/d [i, m];

                                if b

                                        begin

                                                a: = b;

                                                k: = i;

                                        end;        

                        end;

{Симплекс-преобразование}

d [k, 1]: =d[1, m];

a: = d[k, m];

For j: = 2 to n+2 do

        d [k, j]: =d[k, j]/a;

For i: = 2 to r + 2 do

        begin

                a: = d[i, m];

                if i<>k then

                        For j: = 2 to n+2 do

                                d [i, j]: = d[i, j]-a*d[k, j];

        end;

Writeln; Writeln (‘Преобразованная матрица’);

Writeln;

        For i: =1 to r+2 do

                        begin

                                For j: =1 to n+2 do Writeln (d [i, j]: 6:3,’’);

                                Writeln;

                        end;

                end;

        end;

end;

end. 

Контрольные вопросы по итогам курса.

1. Как ставится в общем виде задача линейного программирования?
2. В каких случаях возможно решить задачу линейного программирования геометрически (т. е. с помощью графика)?
3. Как перейти от ограничений-уравнений к ограничениям-неравенствам и наоборот?
4. Какие существуют варианты наличия решения задачи линейного программирования?
5. В чем состоит суть симплекс-метода?
6. Как решается задача отыскивания начального базиса для «запуска» симплекс-метода?
7. Какие средства можно использовать для решения задач линейного программирования в табличном процессоре Excel?
8. Есть ли в пакете MathCAD встроенные программы для решения задач оптимизации, если да, то какие?
9. В чем состоят удобства применения языка программирования Visual Basic for Applications (VBA) для решения задач, содержащих большие массивы данных?
10. Как в VBA реализуется привязка переменных к ячейкам электронной таблицы?

К урокам были разработаны следующие приложения:

Приложение 1. Презентации к занятиям.

Приложение 2. Практические работы для индивидуального выполнения.

Приложение 3. Контрольный тест.

Приложение 4. Исполняемые файлы заданий из лабораторных работ.

СПИСОК ЛИТЕРАТУРЫ

1. Абчук В.А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций. – СПб.: Союз, 1999.
2. Агальцов В.П., Волдайский И.П. Математические методы в программировании. – М.: ИД “ФОРУМ” – ИНФА – М, 2006.
3. Зубрилин А.А., Капралова М. Г. Решение задачи о выборе оптимального маршрута средствами Ms Excel //Информатика и образование. – 2008, №7.
4. Красе М. С. Математика для экономистов / М. С. Красе, Б. П. Чупрынов. - СПб.: Питер, 2004.
5. Красе М. С. Математика для экономических специальностей: учебник / М. С. Красе. - М.: ИНФРА-М, 1998.
6. Красе М. С. Основы математики и ее приложения в экономическом образовании: учебник / М. С. Красе, Б. П. Чупрынов. - М.: Дело, 2003.
7. Кузнецов Ю. Н. Математическое программирование / Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Велощенко. - М.: Высшая школа, 1980.
8. Куликов Ю.Г., Шеховцева Н.Ф., Зикеева Л.П. Экономико-математические методы  и модели (раздел «Линейное программирование»): Учебное пособие для практических занятий. – М.: НПО «МОДЭК», 2000.
9. Любимов, Л. Л. Основы экономических знаний: учебник для 10 и 11 классов школы и классов с углубленным изучением экономики /Л. Л. Любимов, Н. А. Раннева. - М.: Вита-Пресс, 2002.
10. Мажукин В. И. Математическое моделирование в экономике: Часть 1. Численные методы и вычислительные алгоритмы. – М.: Флинта: МПСИ, 2005.
11. Мажукин В. И. Математическое моделирование в экономике: Часть 2. Лабораторный практикум по численным методам и вычислительным алгоритмам. – М.: Флинта: МПСИ, 2005.
12.  Малыхин В.И. Математика в экономике: Учебное пособие. –    М.: ИНФОА-М, 2001.
13. Семакин И. Г. Информационные системы и модели. Элективный курс: Практикум/ И. Г. Семакин, Е. К Хеннер. – М.: БИНОМ. Лаборатория знаний, 2006.
14. Семакин И.Г. Информационные системы и модели. Элективный курс: Учебное пособие. – М.: БИНОМ. Лаборатория знаний, 2005.
15. Солодовников А. С. Математика в экономике: учебник /А. С. Солодовников, В. А. Бабайцев, А. В. Браилов и др. - М.: Финансы и статистика, 1999.
16. Угринович Н.Д. Информатика и информационные технологии. – М.: БИНОМ. Лабораторий знаний, 2007.
17. Шапкин А. С. Задачи с решениями по высшей математике, теории вероятностей, математической статистике, математическому программированию: учебное пособие / А. С. Шапкин. - М.: Издательско-торговая корпорация «Дашков и К». 2006.
18. Шапкин, А. С. Математические методы и модели исследования операций: учебник / А. С. Шапкин, Н. П. Мазаева. - М.: Издательско-торговая корпорация «Дашков и К», 2003.
19. Штепа Ю.П. Решение задач прогнозирования и планирования в школьном курсе информатики // Информатика и образование. -2008, №9-10.
20. Штепа Ю.П. Решение задач прогнозирования и планирования в школьном курсе информатики // Информатика и образование. – 2008, №11.