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

Составим математическую модель задачи. Обозначим планируемый выпуск карамели через x1, помадные конфеты через x2, зефир через x3 и шоколадные изделия через x4.

Тогда математическая постановка задачи состоит в определении максимального значения функции:

F(X) = 16x1 + 10x2 + 13x3 + 26x4.

Таблица 3.2

Математическая постановка задачи в таблице

При следующих условиях-ограничениях:

2x1 + 3x2 + 2x3 + 4x4≤700

4x1 + 5x2 + 2x3 + 3x4≤440

3x1 + 4x2 + 4x3 + 5x4≤400

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

В 1-м неравенстве смысла (≤) вводим базисную переменную x₅. В 2-м неравенстве смысла (≤) вводим базисную переменную x₆. В 3-м неравенстве смысла (≤) вводим базисную переменную x₇.

2x1 + 3x2 + 2x3 + 4x4 + 1x5 + 0x6 + 0x7 = 700

4x1 + 5x2 + 2x3 + 3x4 + 0x5 + 1x6 + 0x7 = 440

3x1 + 4x2 + 4x3 + 5x4 + 0x5 + 0x6 + 1x7 = 400

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Таблица 3.3

Матрица коэффициентов

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

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

Решим систему уравнений относительно базисных переменных: x5, x6, x7. Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,700,440,400)

Базисное решение называется допустимым, если оно неотрицательно.

Таблица3.4

Первая симплекс-таблица

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

В качестве ведущего берем столбец, соответствующий переменной A4, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai4

и из них выберем наименьшее: min (700: 4, 440: 3, 400: 5) = 80

Следовательно, 3-я строка является ведущей.

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

Таблица 3.5

Симплекс-таблица (Определение новой свободной переменной)

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. Вместо переменной x7 в план 1 войдет переменная x4.

Строка, соответствующая переменной x4 в плане 1, получена в результате деления всех элементов строки x7 плана 0 на разрешающий элемент РЭ=5. На месте разрешающего элемента получаем 1. В остальных клетках столбца x4 записываем нули.

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

НЭ = СЭ - (А*В)/РЭ

ТЭ - элемент старого плана, РЭ - разрешающий элемент (5), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. [6].

Представим расчет каждого элемента в виде таблицы 3.6:

Таблица 3.6

Симплекс-таблица (Расчёт элементов)

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

Таблица 3.7

Новая симплекс-таблица (получен первый опорный план)

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

Итерация №1. Проводится аналогичным образом.

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

Таблица 3.8

Новая симплекс-таблица (получен второй опорный план)

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

Оптимальный план можно записать так:

x1 = 9010/11, x2 = 0, x3 = 0, x4 = 255/11

F(X) = 16•9010/11 + 10•0 + 13•0 + 26•255/11 = 21164/11

ЗАКЛЮЧЕНИЕ

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

На втором этапе выполнения курсовой работы была обоснована целесообразность применения методов исследования операций для разработки схемы перевозки грузов от складов в различные города. Построена математическая модель транспортной задачи в виде дискретной бинарной распределительной задачи. Проведённый анализ методов решения такого рода математических задач позволил сделать вывод о целесообразности сведения исследуемой задачи к дискретной транспортной задаче линейного программирования с последующим её решением методом дифференциальных рент. Рассмотрен пример решения задачи. И получены соответствующие результаты.

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

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

1. Акуличь И. А. Математическое программирование в примерах и задачах / И.А. Акуличь. - М.: «Высшая школа», 2012. - 319 с.

2. Волков И.К. Исследование операций: Учеб. для вузов. 2-е узд./ В.С. Зарубина, А.П.Крищенко. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2012. - 436 с.

3. Вычислительная математика для экономических специальностей под редакцией Кремера Н.Ш. - М.: ВШ, 2005.

4. Голштейн Е. Г. Задачи линейного программирования транспортного типа/ Е.Г. Гольштейн, Д.Б. Юдин. - М.: Наука, ФИЗМАТЛИТ, 2009. - 384 с.

5. Гореликов В.А. Исследование операций и методы оптимизации: учебник / В.А. Гореликов. – М.: Академия, 2013. – 272с.

6. Конюховский П. В. атематические методы исследования операций в экономике: учебное пособие / П. В. Конюховский. - М.: Питер, 2000. - 208 с.

7. Осипова Г. И., Миронова Г. В. Экономика и организация производства. Учебное пособие. — М.: МГУП, 2011. — 322 с. — 500 экз

8. Пантелеев А.В. Методы оптимизации в примерах и задачах: Учеб. пособие / А.В.Пантелеев, Т.А. Летова – М: Высш. Школа, 2002. - 544с.

9. Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие/ В.А. Пантелеев - Мн.: Выш. шк., 2014. - 256с.

10. Тахан Х. Введение в исследование операций / Х. Тахан – М.: Издательский дом “Вильямс”, 2011. - 300с.

11. Федеральный закон от 26.12.1995 № 208-ФЗ «Об акционерных обществах»

12. Хазанова Л.Э. Математическое программирование в экономике/ Л.Э Хазанова. Учебное пособие. - М.: Издательство БЕК, 2013. - 141с.

13. Шапкиен, А.С. Математические методы / А. Шапкиен. Учебник. - М.: Издательство «Дашков и К», 2011. - 104 с.

14. Экономико-математические методы и модели. Высшая математика для экономистов: учебник для бакалавров [по специальностям экономики и управления] / А. М. Попова, В. Н. Сотников; под ред. А.М. Попова. - 2-е изд., испр. и доп. - М.: Юрайт, 2013. - 479 с. - (Бакалавр. Базовый курс). - ISBN 978-5-9916-2377-3.