Оптимизация использования производственной мощности

ВВЕДЕНИЕ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...4

1ОБЩЕЕ РЕШЕНИЕ ЗАДАЧИ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 5
1.1 Выделение элементарных актов, выбор и обоснование
целевой функции ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 5
1.2 Разработка общей математической модели и формулирование задачи оптимизации ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..5
1.3 Модифицированные жордановы исключения (МЖИ) ... ... ... ... ... ... ... ... ..6
1.4 Алгоритм прямого симплекс.метода ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 6
1.5 Алгоритм двойственного симплекс.метода ... ... ... ... ... ... ... ... ... ... ... ... ... ... 8

2 РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 10
2.1Содержательная формулировка задачи ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...10
2.2Построение математической модели ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 10
2.3Выбор метода и разработка вычислительного алгоритма решения задачи ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 11
2.3.1Решение прямым симплекс.методом ... ... ... ... ... ... ... ... ... ... ... ... .. 11
2.3.2Решение двойственным симплекс.методом ... ... ... ... ... ... ... ... ... .13
3 ПРОГРАММНАЯ РАЗРАБОТКА ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 15
3.1Общие сведения ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...15
3.2 Функциональное назначение ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..15
3.3Описание программного продукта ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...15
3.4 Описание программы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 15

ЗАКЛЮЧЕНИЕ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 17
СПИСОК ЛИТЕРАТУРЫ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...18
ПРИЛОЖЕНИЕ А ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 19
ПРИЛОЖЕНИЕ В ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .21

Совершенствование управления системами самого различного вида является одной из наиболее актуальных проблем во все времена.
Естественный ход развития науки управления - от простого к сложному. Сначала автоматическое управление простейшими техническими системами, затем оптимальное управление сложнейшими технологическими процессами и такими сложными системами, как современный самолет, корабль, космический аппарат. И только в последнее время наука управления организационными системами сильно шагнула вперед в своем развитии, благодаря целенаправленной деятельности самих элементов организационных систем, бурному применению ЭВМ и применениям новых информационных технологий.
К настоящему времени управление организационными системами в большей мере рассматривается в экономике и производстве. Под механизмами функционирования таких систем понимаются, как правило, процедуры формирования информации для управления, методы формирования управляющих переменных (объем ресурсов, продукции, цен, нормативов), методы финансового управления и экономического стимулирования, административные и финансовые ограничения на деятельность фирм и их дочерних предприятий, методы оперативного управления, методы создания конкуренции и т.д.-в общем, набор организационных, правовых, экономических, финансовых правил, регламентирующих функционирование фирм в экономике и производстве.[2]
К задачам управления организационными системами относятся задачи оптимизации, которые можно решить с помощью симплекс-метода, разработанного Дж. Данцигом в 1947 г. Необходимость создания методов решения опти¬мизационных задач достаточно ясно осознавалась уже и раньше, в частности экономистами и военными специалистами, которым во время второй мировой войны приходилось искать пути реше¬ния сложных задач, возникавших при планировании стратегиче¬ских операций.
Важность разработанного Данцигом симплекс-метода стала еще более очевидной после того, как основоположником теории игр Дж. Нейманом в 1947 г. была развита концепция двойствен¬ности. Это открыло путь исследованиям по многим направле¬ниям ЛП, что обеспечило в дальнейшем увеличение практиче¬ской ценности и расширение сферы применения методов ЛП. Пяти¬десятые годы явились периодом интенсивного развития данной дисциплины в части разработки новых алгоритмов и теоретиче¬ских исследований. В настоящее время ЛП с точки зрения уровня теоретических разработок, сферы приложений и реализации вычислительных методов является одним из наиболее развитых направлений в области решения оптимизационных задач. Дости-жения в области ЛП содействовали прогрессу в разработке алго¬ритмов решения других задач математического программирова¬ния, в том числе в области целочисленного, стохастического и нелинейного программирования.[3]

1. Герчук Я.П. Математические методы в планировании отраслей и предприятий. М.: Наука, 1993.
2. Волобуева О.П. Теоретические основы компьютерных систем. Алматы, 2001
3. Таха Х. Введение в Исследование операций. В 2-х книгах. Кн. 1. - Москва: Мир, 1985
4. Конторович Л.В., Горстко А.Б. Оптимальные решения в экономике. М.: Наука, 1992.
5Сборник задач по курсу "Организация, планирование и управление деятельностью промышленных предприятий" / под ред. Конторовича В.Г. М.: Высшая школа, 1986.
6Сборник задач по курсу "Организация, планирование и управление машиностроительным предприятием" / под ред. В.А. Летенко, Б.Н. Родионова. М.: Высшая школа, 1990.

Дисциплина: Информатика, Программирование, Базы данных
Тип работы: Реферат
Бесплатно: Антиплагиат
Объем: 25 страниц
В избранное:

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РК

Казахский национальный технический университет
им. К.И.Сатпаева

кафедра технической кибернетики

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе по дисциплине
Теоретические основы компьютерных систем

Тема: Оптимизация использования производственной мощности

Руководитель
профессор
_________О.П. Волобуева
“____”___________2004г.
Нормоконтроллер
______________________Ф.И.О.

“____”___________2004г.
Студентка ___Габдуалиева
Н.М.
Специальность 370140
Группа КСУ-01-3
“____”___________2004г.

Алматы 2004
Индивидуальное задание

на курсовую работу по дисциплине

"Теоретические основы компьютерных систем".

На металлургическом заводе изготавливается сталь n марок
{X1,X2,...,Xn}; сталь изготавливается последовательно в m цехов
завода. Производственная мощность каждого из цехов определяется
временем обработки одной тонны каждой марки стали и общим временем
возможной работы конкретного цеха в определенном периоде. По ней
определяются ограничения, составляющие основу модели задачи.
Критерием оптимальности является максимальный общий объём
выпуска продукций в денежном выражении:

Z (X) =
При ограничениях:
Xi0, ;
(1)
вида В
(2)

1) Найти оптимальные значения объёма выпуска марок стали Xi
, .
2) Провести моделирование на PC и сравнить полученные результаты с
расчетными.
Исходные данные приведены в таблице.

Таблица 1-Данные для решения задачи

Коэффициенты № Количество
целевой варианта марок стали Ограничения вида B
Функции аi n
5 4 x1 + 2x2 + x3 + 4x4 ≤ 30;
x1 ≤ 3;
2x1 + 2x2 + x3 + x4 ≤ 40;
2x2 ≤ 7;
2x1 + x2 + 2x3 + x4 ≤ 50;
3x3 ≤ 18;
x1 + x2 + x3 + 2x4 ≤ 60;
x4 ≤ 2;

Руководитель работы Волобуева О.П. И.О.Ф.
__________

подпись
Задание приняла к исполнению Габдуалиева Н.М.
И.О.Ф.
"__" _____________ 2004 г. ____________
подпись

Дата предоставления готовой работы к защите "____"___________2004г.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..4

1ОБЩЕЕ РЕШЕНИЕ ЗАДАЧИ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . ... ... ... ... ... 5
1.1 Выделение элементарных актов, выбор и обоснование
целевой функции ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 5
1.2 Разработка общей математической модели и формулирование задачи
оптимизации ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..5
1.3 Модифицированные жордановы исключения (МЖИ) ... ... ... ... ... ... ... ... ..6
1.4 Алгоритм прямого симплекс-метода ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 6
1.5 Алгоритм двойственного симплекс-метода ... ... ... ... ... ... ... ... ... ... ... ... ... ... 8

2 РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. ... . 10
2.1Содержательная формулировка задачи ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...10
2.2Построение математической модели ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 10
2.3Выбор метода и разработка вычислительного алгоритма решения задачи
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ...11
2.3.1Решение прямым симплекс-методом ... ... ... ... ... ... ... ... ... ... ... ... .. 11
2.3.2Решение двойственным симплекс-методом ... ... ... ... ... ... ... ... ... .13
3 ПРОГРАММНАЯ РАЗРАБОТКА ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 15
3.1Общие сведения ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 15
3.2 Функциональное назначение ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...15
3.3Описание программного продукта ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 15
3.4 Описание программы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... ... ... ... ... 15

ЗАКЛЮЧЕНИЕ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . ... ... ... ... ... ... ... .. 17
СПИСОК ЛИТЕРАТУРЫ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 18
ПРИЛОЖЕНИЕ А ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... ..19
ПРИЛОЖЕНИЕ В ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... ...21

ВВЕДЕНИЕ

Совершенствование управления системами самого различного вида является
одной из наиболее актуальных проблем во все времена.
Естественный ход развития науки управления - от простого к сложному.
Сначала автоматическое управление простейшими техническими системами, затем
оптимальное управление сложнейшими технологическими процессами и такими
сложными системами, как современный самолет, корабль, космический аппарат.
И только в последнее время наука управления организационными системами
сильно шагнула вперед в своем развитии, благодаря целенаправленной
деятельности самих элементов организационных систем, бурному применению ЭВМ
и применениям новых информационных технологий.
К настоящему времени управление организационными системами в большей
мере рассматривается в экономике и производстве. Под механизмами
функционирования таких систем понимаются, как правило, процедуры
формирования информации для управления, методы формирования управляющих
переменных (объем ресурсов, продукции, цен, нормативов), методы финансового
управления и экономического стимулирования, административные и финансовые
ограничения на деятельность фирм и их дочерних предприятий, методы
оперативного управления, методы создания конкуренции и т.д.-в общем, набор
организационных, правовых, экономических, финансовых правил,
регламентирующих функционирование фирм в экономике и производстве.[2]
К задачам управления организационными системами относятся задачи
оптимизации, которые можно решить с помощью симплекс-метода, разработанного
Дж. Данцигом в 1947 г. Необходимость создания методов решения
оптимизационных задач достаточно ясно осознавалась уже и раньше, в
частности экономистами и военными специалистами, которым во время второй
мировой войны приходилось искать пути решения сложных задач, возникавших
при планировании стратегических операций.
Важность разработанного Данцигом симплекс-метода стала еще более
очевидной после того, как основоположником теории игр Дж. Нейманом в 1947
г. была развита концепция двойственности. Это открыло путь исследованиям по
многим направлениям ЛП, что обеспечило в дальнейшем увеличение практической
ценности и расширение сферы применения методов ЛП. Пятидесятые годы явились
периодом интенсивного развития данной дисциплины в части разработки новых
алгоритмов и теоретических исследований. В настоящее время ЛП с точки
зрения уровня теоретических разработок, сферы приложений и реализации
вычислительных методов является одним из наиболее развитых направлений в
области решения оптимизационных задач. Достижения в области ЛП
содействовали прогрессу в разработке алгоритмов решения других задач
математического программирования, в том числе в области целочисленного,
стохастического и нелинейного программирования.[3]
1 ОБЩЕЕ РЕШЕНИЕ ЗАДАЧИ

1.1Выбор и обоснование целевой функции

При постановке задачи организационного управления прежде всего важно:
1)определить цель, преследуемую субъектом управления, и 2) установить,
значениями каких характеристик (переменных) исследуемой системы (или
процесса) можно варьировать.
Под целью будем понимать тот конечный результат, который необходимо
получить путем выбора и реализации тех или иных управляющих воздействий на
исследуемую систему. В производственно-коммерческой сфере цель, как
правило, заключается в том, чтобы либо максимизировать прибыль, либо
минимизировать расходы. Цель должна быть представлена в виде функции от
управляемых переменных[2].
Пример.
Пусть имеются i (i=1..m) сортов взаимозаменяемого сырья в количестве
ai, которое используется при производстве j (j=1..n)продуктов в количестве
bj единиц. Матрица C характеризует производственные затраты на единицу
продукта (в руб). Составить оптимальный план посева, если расход сырья (в
кг) на единицу продукта (в руб) составляет λij.
Обозначим через xlp – количество i- го сорта сырья, используемого при
производстве j – го продукта.
Тогда стоимость рассматриваемой единицы продукта оценивается величиной
clpxlp, а общая стоимость всех затрат – величиной ΣΣ clpxlp.
Таким образом математическая задача формулируется так: найти x11, x12,
...,xkr, доставляющие минимум функциипри ограничениях:

2. Разработка общей математической модели и формулирование задачи
оптимизации
Математической моделью называются формальные соотношения,
устанавливающие связь принятого критерия эффективности с действующими
факторами операции.
Чтобы построить математическую модель, необходимо оценить
количественно проявления рассматриваемых факторов и указать группы
изменяемых параметров, формально представляющих эти факторы. Однако следует
иметь в виду, что никаких правил построения математических моделей не
существует. Каждая модель есть проявление знаний, опыта, искусства
оперирующей стороны. Процесс создания модели требует четкого осознания цели
операции, проникновения в существо моделируемых явлений, умения отделить
главное от второстепенного. Математические модели могут иметь вид формул,
систем уравнений или неравенств, а также таблиц, числовых
последовательностей, геометрических образов, отражающих зависимости между
критерием эффективности операции и теми параметрами, которые представляют
учтенные действующие факторы[1].
Пусть математическая модель задачи линейного программирования задана в
следующем виде:

, (1)
, (2)
.
(3)

1.3 Модифицированные жордановы исключения (МЖИ).
Основы вычисления схемы симплекс-метода составляют модифицированные
жордановы исключения (МЖИ). Один шаг МЖИ с разрешающим элементом
переводит исходную таблицу в новую по следующим 5 правилам:

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

5. Все элементы новой таблицы делятся на разрешающий элемент.

1.4Алгоритм прямого симплекс-метода.

Заполнение симплекс-таблицы:

Таблица 1.1- Исходная симплекс таблица
-x1 -x2 ... -xn 1
Y1 a11 a12 ... a1n a1
Y2 a21 a22 ... a23 a2
... ... ... ... ... ...
ym am1 am2 ... amn an
z -p1 -p2 ... -pn 0

1) Исключение свободных переменных:

Таблица 1.2- Симплекс таблица, перед исключения свободных переменных
-y1 -y2 ... -yn 1
x1 b11 b12 ... b1n b1
x2 b21 b22 ... b23 a2
... ... ... ... ... ...
Xn bn1 bn2 ... bnn bn
Yn+1 bn+1,1bn+1,2... bn+1,nbn+1
... ... ... ... ... ...
Ym bm1 bm2 ... bmn bn
z q1 q2 ... qn Q

Выписываем выражения для :
.( )(5)

Вычеркиваем их из таблицы 1.1 .Работу продолжаем в таблице 1.2.

Таблица 1.3- Симплекс таблица, после исключения свободных переменных

-y1 -y2 ... -yn 1
Yn+1 bn+1,1bn+1,2... bn+1,nbn+1
... ... ... ... ... ...
Ym bm1 bm2 ... bmn bn
z q1 q2 ... qn Q

2) Исключение нулевых строк.
Правило выбора разрешающего элемента:
1. В качестве разрешающего выбирается столбец, содержащий
положительные коэффициенты ().
2. Выбор разрешающей строки: вычисляются положительные отношения
свободных членов к коэффициентам разрешающего столбца. Среди всех
отношений выбирается наименьшее. Таким образом, находится
разрешающий элемент. Еще раз выполняется шаг МЖИ.

3) Нахождение опорного решения.
1. Если все свободные члены таблицы 4 положительные, то опорное
решение задается :
y1 = y2 = ... = yn = 0
yn+1 = bn+1
ym = bm

Значение подставляем в систему и получаем значение х:
хоп = {x1оп, x2оп, . . . , xnоп }
zоп = Q

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

4) Нахождение оптимального решения.
Если все коэффициенты z-ой строки положительны, то оптимальное решение
найдено.
q1≥0, . . ., qn≥0; y1* = y2* = yn* = 0
yn+1* = bn+1; z* = Q; ym* = bm
x* = { x1*, x2*, . . . , x n*}
Если среди свободных членов есть отрицательные, то применяется
следующее правила выбора разрешающего элемента:
1. В качестве разрешающего выбирается столбец с отрицательным
коэффициентом z-ой строки, если отрицательных коэффициентов
несколько, то выбирается наибольший по модулю.
2. Отбираются все положительные коэффициенты разрешающего столбца и
соответствующие свободные члены делятся на них. Среди всех
отношений выбирается наименьшее выполняется шаг МЖИ и так до тех
пор пока есть отрицательные коэффициенты z-ой строки, либо не
установиться неограниченная z.[3]

1.5Алгоритм двойственного симплекс-метода.

1)Заполнение симплекс-таблицы (см. 1.4)

2)Исключение свободных переменных (см.1.4)

3)Исключение нулевых строк (см.1.4).

4)Нахождение оптимального решения.
Если все коэффициенты строки положительны, то 0 является оценкой
сверху и осуществляется переход к шагу 5). Иначе применяется
следующее правило выбора разрешающего элемента:
1Рассматривается столбец с отрицательным коэффициентом z-ой строки.
2 В s-столбце находится некоторый элемент, больший нуля, ars и строка
r считается разрешающей (если все коэффициенты отрицательны, то
функция либо неограниченная сверху, либо условия задачи
противоречивы).
3 Вычисляются неположительные отношения коэффициентов z строки к
соответствующим коэффициентам разрешающей строки. Среди всех отношений
выбирается наибольшее (наименьшее по модулю). Выполняется шаг МЖИ.
5) Нахождение опорного одновременно оптимального решения.
Если все свободные члены положительны, то опорное одновременно
оптимальное решение найдено.
Если среди свободных членов есть отрицательные, то применяется
следующее правила выбора разрешающего элемента:
1В качестве разрешающего выбирается строка с отрицательным свободным
членом.
2Отбираются все отрицательные коэффициенты этой строки (если среди
коэффициентов разрешающей строки нет отрицательных, то условия задачи
противоречивы.)
3Вычисляются неположительные отношения коэффициентов z строки к
отобранным коэффициентам. Среди всех отношений выбирается наибольшее
(наименьшее по модулю).Выполняется шаг МЖИ.[3]

2 РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ

2.1Содержательная формулировка задачи
На металлургическом заводе изготавливается сталь n марок
{X1,X2,...,Xn}; сталь изготавливается последовательно в m цехов
завода. Производственная мощность каждого из цехов определяется
временем обработки одной тонны каждой марки стали и общим временем
возможной работы конкретного цеха в определенном периоде.
Критерием оптимальности является максимальный общий объём выпуска
продукций в денежном выражении:

Z (X) =
При ограничениях:
Xi0, ; вида В

1) Найти оптимальные значения объёма выпуска марок стали Xi
, .
2) Провести моделирование на PC и сравнить полученные результаты с
расчетными.
Исходные данные приведены в таблице.

Таблица 1-Данные для решения задачи

Коэффициенты № Количество
целевой варианта марок стали Ограничения вида B
Функции аi n
5 4 x1 + 2x2 + x3 + 4x4 ≤ 30;
x1 ≤ 3;
2x1 + 2x2 + x3 + x4 ≤ 40;
2x2 ≤ 7;
2x1 + x2 + 2x3 + x4 ≤ 50;
3x3 ≤ 18;
x1 + x2 + x3 + 2x4 ≤ 60;
x4 ≤ 2;

2.2Построение математической модели
Пусть заданы:
1. количество марок стали n;
2. количество цехов, в которых последовательно изготавливается сталь m;
3. время обработки одной тонны каждой марки стали;
4. общее время возможной работы конкретного цеха в определенном
периоде.

Необходимо максимизировать общий объем выпуска продукции в денежном
выражении:
Z (X) =
при ограничениях:
xi0, ;
x1 + 2x2 + x3 + 4x4 ≤ 30;
x1 ≤ 3;
2x1 + 2x2 + x3 + x4 ≤ 40;
2x2 ≤ 7;
2x1 + x2 + 2x3 + x4 ≤ 50;
3x3 ≤ 18;
x1 + x2 + x3 + 2x4 ≤ 60;
x4 ≤ 2;

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

2.3.1Решение прямым симплекс-методом.
Таблица 2.1- Исходная симплекс таблица
-x1 -x2 -x3 -x4 1
y1 1 2 1 4 30
y2 1 0 0 0 3
y3 2 2 1 1 40
y4 0 2 0 0 7
y5 2 1 2 1 50
y6 0 0 3 0 18
y7 1 1 1 2 60
y8 0 0 0 1 2
z -300 -245 -390 -550 0

Таблица 2.2 – Симплекс таблица (итерация №1)
-x1 -x2 -x3 -y8 1
y1 1 2 1 -4 22
y2 1 0 0 0 3
y3 2 2 1 -1 38
y4 0 2 0 0 7
y5 2 1 2 -1 48
y6 0 0 3 0 18
y7 1 1 1 -2 56
x4 0 0 0 1 2
z -300 -245 -390 550 1100

Таблица 2.3 – Симплекс таблица (итерация №2)
-x1 -x2 -y6 -y8 1
y1 1 2 -13 -4 16
y2 1 0 0 0 3
y3 2 2 -13 -1 32
y4 0 2 0 0 7
y5 2 1 -23 -1 36
x3 0 0 13 0 6
y7 1 1 13 -2 50
x4 0 0 0 1 2
z -300 -245 130 550 3440

Таблица 2.4 – Симплекс таблица (итерация №3)

- y2 - x2 -y6 -y8 1
y1 -1 2 -13 -4 13
x1 1 0 0 0 3
y3 -2 2 -13 -1 26
y4 0 2 0 0 7
y5 -2 1 -23 -1 30
x3 0 0 13 0 6
y7 -1 1 13 -2 47
x4 0 0 0 1 2
z 300 -245 130 550 4340

Таблица 2.5 – Симплекс таблица (итерация №4)

- y2 - y4 ... продолжение

Вы можете абсолютно на бесплатной основе полностью просмотреть эту работу через наше приложение.