Факультет экономики и управления
Кафедра математических методов и моделей в экономике
ОТЧЕТ
по лабораторной работе
по курсу «Исследование операций»
на тему: «Решение задач линейного программирования»
Постановка задачи
На предприятии имеются три группы станков. Нужно изготовить два вида изделий – А и В. Фонд рабочего времени по первой группе станков составляет 400 часов, по второй- 360 часов, по третьей- 1320 часов. Время на обработку одного изделия вида А составляет для первой группы станков- 0,4 час., для второй – 0,84 час., для третьей- 8,0 часов. Соответственно для одного изделия группы В- 2,0; 1,2; 4,0 час. Каждое изделие вида А при его реализации дает прибыль предприятию в 1,2 ед., а изделие В- 4,8 ед. Найти план при котором прибыль будет максимальна.
Решить задачу:
- Симплекс- методом с помощью программного обеспечения DV SIMP;
- В МПП Excel с помощью надстройки «Поиск решения».
1 Обоснование симплекс- метода
Симплекс метод - это характерный пример итерационных вычислений, используемых при решении большинства оптимизационных задач. В вычислительной схеме симплекс-метода реализуется упорядоченный процесс, при котором, начиная с некоторой исходной допустимой угловой точки (обычно начало координат), осуществляются последовательные переходы от одной допустимой экстремальной точки к другой до тех пор, пока не будет найдена точка, соответствующая оптимальному решению.
Пусть имеется задача линейного программирования в канонической форме:
F=c1x1+c2x2+…+cnxn→max(min), (1)
a11x1+a12x2+…+a1nxn=b1,
…………………………, (2)
am1x1+am2x2+…+amnxn≤bm;
xi ≥0, i=1,…,n;
Введем в рассмотрение вектора , j=1,…,n.
Тогда задачу можно переписать в следующем виде:
F=<c,x>→max(min), (3)
A1x1+A2x2+…+Anxn=b,
,
и трактовать следующим образом: из всех разложений вектора b по векторам с неотрицательными коэффициентами, требуется выбрать хотя бы одно такое, коэффициенты xi которого доставляют целевой функции F оптимальной значение. Не ограничивая общности, считаем ранг матрицы А: r=m и n>m.
Ненулевое допустимое решение называется опорным, если вектора , соответствующие отличным от нуля координатам , линейно независимы.
Ненулевое опорное решение называется невырожденным, если оно имеет m- положительных координат.
Если число положительных координат опорного решения меньше m, то оно называется вырожденным.
Упорядоченный набор из m- линейно независимых векторов , соответствующих положительным координатам опорного решения, назовем базисом.
Теорема: вектор тогда и только тогда является опорным решением задачи, когда точка является вершиной допустимого множества. Таким образом, задача нахождения вершины допустимого множества свелась к задаче нахождения опорного решения, а, следовательно, к нахождению базиса.
Будем считать, что исходный базис Ai1,…,Aim, тогда вектор b разложим по этому базису:
b==
.
Аналогично можно представить любой вектор :
В частности, в качестве исходного базиса могут быть взяты вектора, образующие единичную матрицу:
если они присутствуют в канонической форме задачи; в противном случае, исходный базис нужно строить, то есть имеет место задача с искусственным базисом.
Используя разложение вектора по базису векторами можно сформулировать утверждения:
- Если для данного базиса все оценки
неотрицательны, то опорное решение является оптимальной точкой задачи;
- Если для данного базиса существует хотя бы одна оценка для нее все то это означает, что целевая функция данной задачи линейного программирования не ограничена сверху на допустимом множестве;
- Если для данного базиса есть такая отрицательная оценка что среди координат вектора в данном базисе
координаты все векторов в новом базисе могут быть найдены через координаты векторов в старом базисе по формулам:
Алгоритм решения задачи симплекс методом.
Исходные данные:
- Вычисляем координаты разложения векторов по базису ;
- Рассчитываем оценки по формулам (1) и проверяем, являются ли они положительными. Если да, то алгоритм заканчивает свою работу, опорное решения является оптимальным, если нет, то проверяем, существуют ли такие , что все . Если существуют, то алгоритм заканчивает свою работу, задача неразрешима. Если нет, находим и находим
Далее производим замену в базисе вектора на вектор и снова выполняем разложение по новому базису.
В случае небольшого числа ограничений переменных указанный алгоритм легко реализовать без помощи ЭВМ, оформляя решение в виде симплекс-таблиц.
Пусть дана задача в канонической форме и найден исходный базис . Находим разложение всех векторов по базису. Результат оформляем в виде таблицы.
|
№ |
Базис |
В |
… |
||||
|
… |
|||||||
|
1 |
… |
||||||
|
2 |
… |
||||||
|
… |
… |
… |
… |
… |
… |
… |
… |
|
M |
… |
||||||
|
|
… |
|
|||||
2 Практическая часть
Представим данную задачу в виде таблицы 1.
Таблица 1- Исходные данные
|
Группа станков |
Фонд рабочего времени, час. |
Время на реализацию ед. продукции |
|
|
А |
В |
||
|
1 |
400 |
0,4 |
2 |
|
2 |
360 |
0,84 |
1,2 |
|
3 |
1320 |
8 |
4 |
Обозначим:
х1- количество произведенных изделий вида А;
х2 – количество произведенных изделий вида В.
Таким образом, целевая функция имеет следующий вид:
F=1,2*x1+4,8*x2→max;
Система ограничений запишется в виде:
0,4*х1+2*х2 ≤ 400;
0,84*х1+1,2*х2 ≤ 360;
8*х1+4*х2 ≤ 1320;
х1 ≥ 0, х2 ≥ 0.
Решим задачу с помощью программы DV SIMP. Введем исходные данные (рисунок 1).
Рисунок 1- Исходные данные
На следующем шаге необходимо привести систему к каноническому виду (рисунок 2).
Рисунок 2- Приведение к каноническому виду
После чего в целевой функции появятся переменные х3, х4, х5, и коэффициенты системы ограничений имеют следующий вид (рисунок 3):
Рисунок 3- Коэффициенты
Видим, что начальный базис можно указать. Он будет состоять из векторов А3, А4, А5 , которые образуют единичную матрицу.
Таким образом, на начальном этапе симплекс-таблица имеет следующий вид (рисунок 4):
Рисунок 4- Симплекс таблица
Для данной таблицы рассчитали оценки, среди которых оказались отрицательные, следовательно, решение не оптимально.
Так как решение не найдено, продолжаем решение, определяем новый базис (рисунок 5).
Рисунок 5- Определение базиса
По рисунку 5 видно, что ввести в базис нужно вектор А2, так как ему минимальная оценка.
Для определения вектора, который нужно вывести из базиса, рассчитаем ϴ для каждого вектора текущего базиса.
ϴ1=400/2=200;
ϴ2=360/1,2=300;
ϴ3=1320/4=330.
Минимальное значение ϴ соответствует вектору А3, следовательно, его выводим из базиса.
Для нового базиса симплекс- таблица представлена на рисунке 6.
Рисунок 6- Симплекс-таблица
Среди оценок текущей симплекс- таблицы есть отрицательная, следовательно, оптимальное решение не найдено, и нужно продолжать решение.
Минимальное значение оценки соответствует вектору А1, который введем в базис. Рассчитаем ϴ:
ϴ1=200/0,2=1000;
ϴ2=120/0,6=200;
ϴ3=520/7,2=72.222.
Минимальное значение ϴ соответствует вектору А5, следовательно, его выводим из базиса.
Для нового базиса симплекс- таблица представлена на рисунке 7.
Рисунок 7- Симплекс-таблица
Видим, что среди оценок нет отрицательных, а значит, оптимальное решение найдено (рисунок 8).
Рисунок 8- Решение задачи
В базис вошли вектора А2, А4, А1. Оптимальное значение целевой функции F=977,333. Соответственно оптимальные значения х1= 72,222; х2= 185,556.
Найдем решение данной задачи с помощью функции «Поиск решения» в МПП Excel.
Результат представлен на рисунке 9.
Рисунок 9- Решение задачи в МПП Excel
Получили аналогичный результат, то есть оптимально производить 72 изделия вида А и 185 изделий вида В. При этом максимальная прибыть будет равна 977,333 ед.
Скачать: