| Страница: 4 из 5 <-- предыдущая следующая --> | Перейти на страницу: |
| Сб | Хб | В | 10 = С1 | 8 = С2 | 0 = С3 | 0 = С4 | 0 = С5 |
|
| | | Х1 | Х2 | Х3 | Х4 | Х5 |
| 0 | Х3 | 80 | 4 | 2 | 1 | 0 | 0 |
| 0 | Х4 | 60 | 1 | 3 | 0 | 1 | 0 |
| 0 | Х5 | 100 | 2 | 3 | 0 | 0 | 1 |
| Zj -Сj | Z0= 0 | -10 | -8 | 0 | 0 | 0 |
Ключевой столбец Генеральный элемент Ключевая строка
В отправной симплексной таблице введены следующие значения:
Сб– коэффициенты при базисных переменных целевой функции.
Хб- базисные переменные.
В - столбец свободных членов.
Zj- определяется как сумма попарных произведений коэффициентов Сбна элементы столбца В.
Z0= 0*80+0*60+0*100 = 0
Сj- коэффициент целевой функции при переменной.
Zj -Сj- индексная строка.
Z1– С1ЮZ1= 0*4+0*1+0*2-10 = -10
Z2= 0*2+0*3+0*3-8 = -8
Получение второго базисного решения, и решения вообще, надо преобразовать, первую таблицу во вторую получив улучшенное (решение) значения.
Z - значение целевой функции для данного решения.
Правила определения оптимального решения:
- Полученное значение в симплексной таблице целевой функции считается максимальным (минимальным), если в индексной строке (последней) нет ни одного значения меньше (максимального) 0;
- Если нет ни одного значения больше 0 (минимальное);
- Наибольшее по абсолютной величине отрицательное число в индексной строке указывает на новую базисную переменную (в нашем случае это (– 10) х1).
- Определение старой базисной переменной, которая должна в новом решении уступить место новой базисной переменной, производится следующем образом:
свободные члены столбца В делятся на коэффициенты столбца при новой базисной переменной и минимальное значение в столбце укажет номер старой базисной переменной.
80/4=20; 60/1=60; 100/2=50.
Составляем вторую базисную таблицу:
| Сб | Хб | В | 3 = С1 | 2 = С2 | 0 = С3 | 0 = С4 | 0 = С5 |
|
| | | Х1 | Х2 | Х3 | Х4 | Х5 |
| 4 | Х1 | 20 | 1 | | 4 | 0 | 0 |
| 0 | Х4 | 40 | 0 | 5/2 | -1/4 | 1 | 0 |
| 0 | Х5 | 60 | 0 | 2 | -1/2 | 0 | 1 |
| Zj –Сj | Z= 200 | 0 | -3 | 5/2 | 0 | 0 |
Столбец новой базисной переменной называется ключевым столбцом. Строка куда попадает новая базисная переменная, называется ключевой строкой. На пересечении ключевой строки и ключевого столбца стоит генеральный элемент.
Правила заполнения таблиц после отправной:
1) Старый ключевой столбец переписывают в новую таблицу в виде нулей, кроме элемента стоящего на пересечении ключевого столбца и ключевой строки, здесь ставится единица – этот элемент называется генеральным.
2) Элементы новой строки соответствующие старой ключевой строке находятся путем деления элементов старой ключевой строки на генеральный элемент.
3) Столбцы старой таблицы, содержащие в ключевой строке ноль, переписываются в новую таблицу без изменения.
4) Все остальные элементы новой таблицы определяются расчетом по формуле:
Новый элемент = старый элемент – Элемент ключевой стоки * элемент ключевого столбца / генеральный элемент.
Для столбца свободных членов (В):
60-80*1/4=60-20=40
100-80*2/4=100-40=60
Для столбца х2по тому же правилу:
3-2*1/4=3-1/2=5/2
3-2*2/4=3-1=2
Для столбца х3:
0-1*1/4=0-1/4=-1/4
0-1*2/4=0-1/2=-1/2
Определяем индексную строку:
0-80*(-10)/4=0+200=200=Z
-8-2*(-10)/4=-8-(-5)=-3
0-1*(-10)/4=0-(-5/2)=5/2
Определяем ключевой столбец таблицы №2 и ключевую строку используем ранее изложенные правила.
Используя правила выделяем генеральный элемент и определяем новую базисную переменную, так как в индексной строке есть отрицательный элемент и решение нуждается в улучшении.
Х4заменит Х2
Составляем третью таблицу:
| Сб | Хб | В | 3 = С1 | 2 = С2 | 0 = С3 | 0 = С4 | 0 = С5 |
|
| | | Х1 | Х2 | Х3 | Х4 | Х5 |
| 4 | Х1 | 12 | 1 | 0 | 81/20 | -1/5 | 0 |
| 5/2 | Х2 | 16 | 0 | 1 | -1/10 | 5/2 | 0 |
| 0 | Х5 | 28 | 0 | 0 | -3/10 | -4/5 | 1 |
| Zj –Сj | Z= 248 | 0 | 0 | 11/5 | 6/5 | 0 |
40/5/2=40*8/5=16; -1/4/5/2= -1/10
Для столбца свободных членов (В):
20-40*1/2 / 5/2=20-8=12; 60-40*2 / 5/2=60-32=28
Для столбца х3:
4-(-1/4)*1/2 / 5/2=4+1/20=81/20; -1/2-(-1/4)*2 / 5/2=-1/2+1/5=-3/10
Для столбца х4по тому же правилу:
0-1*1/2 / 5/2=0-1/5=-1/5; 0-1*2 / 5/2=0-4/5=-4/5
Определяем индексную строку:
200-40*(-3) / 5/2=200+40*3*2/5=200+48=248=Z
5/2-(-1/4)*(-3) / 5/2=5/2-3/10=22/10=11/5
0-1*(-3) / 5/2=0+6/5=6/5
Из таблицы №3 видно, что в индексной строке отсутствуют отрицательные значения и, следовательно, невозможно дальнейшее назначение итерационных процедур. Полученное значение прибылиZ0= 248 рублей прибылив час, является оптимальным.
Пример №2:
Условие задачи (постановка):
Найти план производства предприятия обеспечивающий максимум прибыли.
Предприятие производит два вида продукции в трех цехах:
А 28
Б 20
В 10
Установлено соответственно: 28;20 и 10 единиц оборудования.
Нормы использования оборудования для производства за 1 час единицы продукции представлены в таблице в машино/часах:
| ЦЕХ | ВИДЫ ПРОДУКЦИИ |
| | 1 | 2 |
| А | 3 | 2 |
| Б | 2 | 1 |
| В | 1 | 0 |
Прибыль первого вида продукции 4 рубля
Прибыль единицы второй продукции 2 рубля
Требуется определить объем выпуска первого и второго вида продукции доставляющего максимум прибыли.
Решение:
1. Составляем модель.
Пусть х1искомый объемu1продукции первого вида;
х2-u2объем выпуска второго вида продукции.
Цель: максимальная прибыль.
Модель:
4х1– прибыль от реализацииuпервого вида продукции
2х2– прибыль от реализацииuвторого вида.
Целевая функцияL(х1х2) = С1х1+ С2х2= 4х1+ 2х2
С1= 4; С2= 2 – коэффициенты при переменных в целевой функции.
Планируемое использование машин по цехам не должно превышать наличие этого оборудования в цехах (по цехам)Юотсюда система неравенств.
А – 3х1+ 2х2Ј28 ограничение по
Б – 2х1+ 1х2Ј20 использованию
В – 1х1+ 0х2Ј10 оборудования,
условие не отрицательности.
х1і0; х2і0.
Для решения задачи симплексным методом в условиях ограничений принимается работа каждой машины в цехе в машино/часах.
Система неравенств приводится к каноническому виду, путем добавления дополнительных переменных и перевода неравенств в уравнение:
3х1+ 2х2+ х3Ј28
2х1+ х2+ х4Ј20
х1+ х5Ј10
Переведем систему неравенств в уравнение:
х3= 28 – (3х1+ 2х2) сколько машин
х4= 20 – (2х1+ х2) нужно
х5= 10 – х1(машино/часов)
Дополнительные переменные должны быть введены в целевую функцию, которая будет иметь вид:
L(х1х2) = С1х1+ С2х2+ С3х3+ С4х4+ С5х5= 4х1+ 2х2+ 0х3+ 0х4+ 0х5
стремится к максимуму
х1>0; х2>0; х3= 0; х4= 0; х5= 0.
Выразим х3;х4их5через х1и х2
х3= 28 – 3х1- 2х2
х4= 20 – 2х1- х2
х5= 10 – х1
Модель составлена и в этой модели имеются: х1; х2– независимые (свободные) переменные; х3; х4; х5– базисные переменные.
По составленной модели используют итерационные процедуры метода, составим альтернативные варианты решения системы уравнений с пятью неизвестными.
Первым решением будет х1= 0; х2= 0; х3= 28; х4= 20; х5= 10.
Целевая функция будет равняться:L = 4*0 + 2*0 + 0*28 + 0*20 + 0*10=0
Используя систему уравнений, составим отправную таблицу:
| Сб | Хб | В | 4 = С1 | 2 = С2 | 0 = С3 | 0 = С4 | 0 = С5 |
|
| | | Х1 | Х2 | Х3 | Х4 | Х5 |
| 0 | Х3 | 28 | 3 | 2 | 1 | 0 | 0 |
| 0 | Х4 | 20 | 2 | 1 | 0 | 1 | 0 |
| 0 | Х5 | 10 | 1 | 0 | 0 | 0 | 1 |
| Zj -Сj | Z0= 0 | -4 | -2 | 0 | 0 | 0 |
Z0= 0*28+0*20+0*10 = 0
Z1– С1ЮZ1= 0*3+0*2+0*1-4 = -4
Z2= 0*2+0*1+0*0-2 = -2
| Страница: 4 из 5 <-- предыдущая следующая --> | Перейти на страницу: |
| © 2007 ReferatBar.RU - Главная | Карта сайта | Справка |