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

Задание. Для приведенных задач экономико-математического моделирования построить математическую модель. Решить задачи графическим методом. Выполнить проверку по помощи встроенного приложения в Excel Solver.

Задача1. Задача оптимального производства

Для изготовления изделий А и В имеем в наличии 100 кг металла. На изготовление изделия А нужно 2 кг металла, а изделия В соответственно 4 кг. Составить план производства, который обеспечит получение наибольшей прибыли от продажи изделий, если цена изделия А - 3 у.е., а изделия В - 2 у.е. Известно, что изделия А нужно изготовить не более чем 40, а изделия В - не более чем 20.

Задача 2. Задача об оптимальном ассортименте

Предприятие изготовляет 2 вида продукции. Цена единицы продукции 1-го вида 25000 грн., продукции 2-го вида – 50 000 грн. Для изготовления продукции используется три вида сырья, запасы которого 37, 57 и 7 у.е. соответственно. Нормы затрат каждого сырья на единицу продукции приведены в следующей таблице.

Продукция	Запасы сырья, в у.ед.
1-й вид продукции, в у.ед.	2-и вид продукции, в у.ед.
1,2	1,9
2,3	1,8	57,6
0,1	0,7

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

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

2. Особенности и принципы математического моделирования.

3. Основные дефиниции экономико-математического моделирования.

4. Особенности экономических наблюдений и измерений.

5. Этапы экономико-математического моделирования.

6. Общая экономико-математическая модель задачи линейного программирования.

7. Геометрическая интерпретация задачи линейного программирования.

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

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

ТРЕБОВАНИЯ К ОТЧЕТУ

1. Записать в тетради условия задач.

2. Построить математическую модель.

3. Решить графическим методом в тетради.

4. Выполнить проверку в Excel

5. Результаты продемонстрировать преподавателю.

6. Ответить на контрольные вопросы.

ТЕМА 2. СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Аннотация

Начальный опорный план. Переход от одного опорного плана к другому. Оптимальное решение. Критерий оптимальности плана. Решение задачи линейного программирования симплексным методом. Метод искусственного базиса.

Графический метод для определения оптимального плана задач линейного программирования целесообразно применять лишь для задач с двумя переменными. При большом количестве переменных необходимо применять другой метод. Из свойств решений задачи линейного программирования известно: оптимальное решение задачи должно находиться в одной из угловых точек многогранника допустимых решений. Поэтому простейший способ отыскания оптимального плана нуждается в переборе всех угловых точек (допустимых планов задачи, которые еще называют опорными). Сравнение вершин многогранника можно осуществлять только после отыскания какой-то одной из них, т.е. найдя начальный опорный план. Каждый опорный план определяется системой m линейно независимых векторов, которые содержатся в системе ограничений задачи с n векторов . Итак, общее количество опорных планов определяется количеством комбинаций . Задачи, которые описывают реальные экономические процессы, имеют большую размерность, и простой перебор всех опорных планов таких задач существует очень много, даже при условии применения современных ЭВМ. Поэтому необходимое использование метода, который делал бы возможным сокращение количества вычислений. 1949 года такой метод был предложен американским ученым Дж.Данцигом – так называемый симплексный метод, или симплекс- метод.

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

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

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

2.1 Начальный опорный план

Рассмотрим задачу линейного программирования, записанную в канонической форме:

.

Не нарушая общности, допустим, что система уравнений содержит первые m единичных векторов. Получим:

(2.1)

(2.2)

(2.3)

Система ограничений (2.2) в векторной форме будет иметь вид:

,(2.4)

где

, ,..., ,

, …, , ,

– линейно независимые единичные векторы m- мерного пространства, которые образуют единичную матрицу и представляют базис этого пространства. Поэтому в уравнении (2.4) базисными переменными будут , а остальные переменные – свободные. Приравняем все свободные переменные к нулю, т.е. . Поскольку , а векторы – единичные, то получим одно из решений системы ограничений (2.2):

(2.5)

т.е. допустимый план.

Такому плану отвечает уравнение

(2.6)

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

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

Необходимо указать, что для случая, когда вектор подлежит включению в базис, а в его представлении (2.7) все , то, очевидно, не существует такого значения , которое исключало бы один из векторов. В таком случае план содержит m +1 положительных компонент, т.е., система векторов будет линейно зависимой и не определяет угловую точку многогранника решений. Функционал не может в ней достигать максимального значения. Это означает, что функционал является неограниченным на многограннике решений.

2.2. Оптимальное решение. Критерий оптимальности плана

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

Рассмотрим задачу линейного программирования (2.1)-(2.3).

Допустим, что она имеет опорные планы и они являются невырожденными. Рассмотрим начальный опорный план вида (2.5):

Такому плану отвечает Разложение базисными векторами

(2.10)

и значение функционала:

(2.11)

Каждый из векторов можно разложить по векторам базиса, причем единственным образом:

,(2.12)

поэтому такому представлению будет отвечать и единственное значение функционала:

.(2.13)

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

,(2.14)

этот план является оптимальным решением задачи линейного программирования (2.1)-(2.3).

Аналогично формулируется условие оптимальности плана задачи на отыскание минимального значения функционала: если для некоторого плана Разложение всех векторов в данном базисе удовлетворяют условию

,(2.15)

этот план Х ₀ является оптимальным решением задачи линейного программирования.

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