פתרון של טבלאות סימפלקס באינטרנט בפירוט. דוגמה לפתרון בעיות

11.4. שיטה DUAL SIMPLEX

מתוצאות הסעיפים הקודמים עולה כי על מנת לקבל פתרון לבעיה המקורית, נוכל לעבור לבעיה הכפולה ובאמצעות הערכות לתכנון האופטימלי שלה, לקבוע את הפתרון האופטימלי לבעיה המקורית.

המעבר לבעיה הכפולה אינו הכרחי, שכן אם ניקח בחשבון את טבלת הסימפלקס הראשונה עם בסיס יחידה נוסף, אז קל לראות שהעמודות מכילות את הבעיה המקורית, והבעיה הכפולה כתובה בשורות.

כפי שהוצג, כאשר פותרים את הבעיה הישירה בכל איטרציה, ההבדל, כלומר עוצמה -מקדם עם משתנה, שווה להפרש בין הצד הימני והשמאלי של האילוץ המקביל של הבעיה הכפולה. אם, בעת פתרון בעיה ישירה עם פונקציית אובייקטיבית הניתנת למיצוי, איטרציה אינה מובילה לפתרון אופטימלי, אז לפחות עבור משתנה אחד ורק באופטימום עבור כולםהבדל .

בהתחשב במצב זה עם דואליות נלקחת בחשבון, אנו יכולים לכתוב

.

לפיכך, אם, לאחר מכן . המשמעות היא שכאשר הפתרון לבעיה הראשונית אינו מיטבי, הפתרון לבעיה הכפולה אינו חוקי. מצד שני בשעה . מכאן משתמע שהפתרון האופטימלי של הבעיה הראשונית מתאים לפתרון קביל של הבעיה הכפולה.

זה איפשר לפתח שיטה חדשה לפתרון בעיות תכנות ליניאריות, שבהן מתקבל בתחילה פתרון לא מקובל, אך "טוב מאופטימלי" (בשיטת הסימפלקס הרגילה, ראשית קָבִיל, אבל לא אופטימליפִּתָרוֹן). שיטה חדשה בשם שיטת דו סימפלקס, מבטיח את קיום תנאי אופטימיות הפתרון ו"קירובו" שיטתי לתחום הפתרונות הישימים. כאשר הפתרון שהושג מתברר כקביל, מסתיים התהליך האיטרטיבי של החישובים, שכן גם פתרון זה הוא אופטימלי.

שיטת הדו-סימפלקס מאפשרת פתרון בעיות תכנות ליניאריות שמערכות האילוץ שלהן, עם בסיס חיובי, מכילות מונחים חופשיים של כל סימן. שיטה זו מאפשרת לצמצם את מספר הטרנספורמציות של מערכת אילוצים וכן את גודל טבלת הסימפלקס. שקול את היישום של שיטת הדו-סימפלקס באמצעות דוגמה.

דוגמא. מצא את המינימום של פונקציה

תחת הגבלות

.

נעבור לצורה הקנונית:

תחת הגבלות

לטבלת הסימפלקס הראשונית יש את הצורה

בסיסי משתנים	איקס 1	איקס 2	איקס 3	איקס 4	איקס 5	פִּתָרוֹן
איקס 3 איקס 4 איקס 5	–3 –4	–1 –3				–3 –6
	–2	–1

פתרון בסיסי ראשוניאופטימלי, אבל לא מקובל.

בדומה לשיטת הסימפלקס הרגילה, שיטת הפתרון הנבחנת מבוססת על שימוש בתנאי קבילות ואופטימליות.

תנאי קבילות. המשתנה הבסיסי השלילי הגדול ביותר בערך המוחלט נבחר כמשתנה הבלתי נכלל (אם יש חלופות, הבחירה נעשית באופן שרירותי). אם כל המשתנים הבסיסיים אינם שליליים, תהליך החישוב מסתיים, מכיוון שהפתרון המתקבל הוא בר ביצוע ואופטימלי.

מַצָב אופטימליות. המשתנה הנכלל בבסיס נבחר מבין המשתנים הלא-בסיסיים כדלקמן. היחסים של המקדמים של הצד השמאלי מחושבים-משוואות למקדמים המתאימים של המשוואה הקשורה למשתנה הבלתי נכלל. יחסים עם מכנים חיוביים או אפס אינם נלקחים בחשבון. בבעיית מזעור משתנה הקלט, הקטן מבין היחסים המצוינים חייב להתאים, ובבעיית המקסום היחס בעל הערך המוחלט הקטן ביותר (אם יש חלופות, הבחירה נעשית באופן שרירותי). אם המכנים של כל היחסים הם אפס או חיובי, לבעיה אין פתרונות אפשריים.

לאחר בחירת המשתנים להיכלל בבסיס ולהחריג, מתבצעת הפעולה הרגילה של הפיכת השורות של טבלת הסימפלקס כדי לקבל את הפתרון הבא.

בדוגמה זו, המשתנה שלא נכלל הוא. היחסים המחושבים לקביעת משתנה הבסיס החדש מוצגים בטבלה הבאה:

משתנים	איקס 1	איקס 2	איקס 3	איקס 4	איקס 5
המשוואה איקס 4 - משוואה	–2 –4	–1 –3
יַחַס

המשתנה שיש לכלול הוא איקס 2. המרת מחרוזת הבאה מביאה לטבלת סימפלקס חדשה:

בסיסי משתנים	איקס 1	איקס 2	איקס 3	איקס 4	איקס 5	פִּתָרוֹן
איקס 3 איקס 2 איקס 5						–1 –1

פתרון חדש גם אופטימלי, אבל עדיין לא חוקי. כמשתנה חדש שלא נכלל, אנו בוחרים (באופן שרירותי) איקס 3 . בואו נגדיר משתנה כלול.

משתנים	איקס 1	איקס 2	איקס 3	איקס 4	איקס 5
המשוואה איקס 4 - משוואה
יַחַס

שיטה פשוטה - זוהי שיטה של ​​מעבר עוקב מפתרון בסיסי אחד (הקודקוד של פוליהדרון הפתרון) של מערכת האילוצים של בעיית תכנות ליניארית לפתרון בסיסי אחר עד שפונקציית המטרה מקבלת את הערך האופטימלי (מקסימום או מינימום).

שיטת הסימפלקס היא שיטה אוניברסלית שיכולה לפתור כל בעיית תכנות ליניארית, בעוד השיטה הגרפית מתאימה רק למערכת אילוצים של שני משתנים.

שיטת הסימפלקס הוצעה על ידי המתמטיקאי האמריקאי ר' דנציג ב-1947, מאז, לצרכי התעשייה, שיטה זו פותרת פעמים רבות בעיות תכנות ליניאריות עם אלפי משתנים ואילוצים.

לפני שנעבור לאלגוריתם של שיטת הסימפלקס, כמה הגדרות.

כל פתרון לא שלילי למערכת של אילוצים נקרא פתרון מקובל .

שתהיה מערכת Mהגבלות מ נמשתנים ( Mנ).

פתרון בסיסי קביל הוא פתרון המכיל Mלא שלילי גדול (בסיסי ) משתנים ו נ - M ללא ליבה . (לא בסיסי, או חינם ) משתנים. משתנים לא בסיסיים בפתרון הבסיסי שווים לאפס, בעוד שהמשתנים העיקריים, ככלל, הם לא אפס, כלומר הם מספרים חיוביים.

כל Mמשתני מערכת Mמשוואות ליניאריות עם נמשתנים נקראים רָאשִׁי , אם הקובע של המקדמים אצלם שונה מאפס. ואז השאר נ - Mמשתנים נקראים ללא ליבה (אוֹ חינם ).

אלגוריתם שיטה פשוטה

• שלב 1. הביאו את בעיית התכנות הליניארית לצורה הקנונית. לשם כך, העבר את המונחים החופשיים לצד ימין (אם בין המונחים החופשיים הללו הם שליליים, הכפל את המשוואה או אי השוויון המתאימים ב-1) והכנס משתנים נוספים לכל אילוץ (עם סימן פלוס, אם ב- אי השוויון המקורי הסימן קטן או שווה ל", ועם סימן מינוס אם "גדול או שווה ל").
• שלב 2. אם במערכת המתקבלת Mמשוואות, אם כן Mקחו את המשתנים כעיקריים, הביטו את המשתנים העיקריים במונחים של המשתנים הלא-בסיסיים, ומצאו את הפתרון הבסיסי המתאים. אם מתברר שהפתרון הבסיסי שנמצא קביל, עבור אל הפתרון הבסיסי הקביל.
• שלב 3. הביעו את פונקציית המטרה במונחים של המשתנים הקטנים של הפתרון הבסיסי האפשרי. אם נמצא המקסימום (המינימום) של הצורה הליניארית ואין משתנים לא בסיסיים עם מקדמים שליליים (חיוביים) בביטוי שלו, אזי קריטריון האופטימליות מתקיים והפתרון הבסיסי המתקבל הוא אופטימלי - הפתרון נגמר. אם, בעת מציאת המקסימום (המינימום) של צורה לינארית, הביטוי שלה מכיל משתנה אחד או יותר לא-בסיסי עם מקדמים שליליים (חיוביים), עבור לפתרון בסיסי חדש.
• שלב 4. מתוך המשתנים הלא-בסיסיים הכלולים בצורה הליניארית עם מקדמים שליליים (חיוביים), בחרו את המתאים למקדם (מודולו) הגדול ביותר, והעבירו אותו לעיקריים. עבור לשלב 2.

תנאים חשובים

כמה מקרים מיוחדים נדונים במאמרים נפרדים: מתי פונקציה אובייקטיבית מקסימלית - אינסוף, מתי למערכת אין פתרון, ומתי הפתרון האופטימלי אינו היחיד .

לאחר מכן, ננתח דוגמה טיפוסית, כאשר מערכת האילוצים עקבית ויש אופטימום סופי, ורק אחד. וריאציה של שיטת הסימפלקס היא שיטת הפצה לפתרון בעיית התחבורה .

שיטת סימפלקס עם טבלאות סימפלקס

על ידי בניית טבלאות סימפלקס, קל הרבה יותר לפתור בעיית תכנות ליניארית מאשר על ידי טרנספורמציות אלגבריות, שמוצגות בפסקה הבאה. שולחנות Simplex הם מאוד חזותיים. ישנם מספר סוגי כללים לעבודה עם טבלאות סימפלקס. ננתח את הכלל, הנקרא לרוב עמודה מובילה וכלל שורה מובילה.

זה יהיה שימושי לפתוח את הפעולות הידניות עם שברים בחלון חדש: יש מספיק כאלה, שברים בבעיות בשיטת הסימפלקס, בלשון המעטה.

דוגמא.

אנו מציגים משתנים נוספים שאינם שליליים ומצמצמים את מערכת אי השוויון הזו למערכת מקבילה של משוואות

.

הדבר נעשה בהתאם לכלל הבא: אם הסימן באילוץ המקורי הוא "קטן או שווה ל", יש להוסיף את המשתנה הנוסף, ואם "גדול או שווה ל", אז המשתנה הנוסף חייב להיות מְחוּסָר.

המשתנים הנוספים שהוצגו נלקחים כעיקריים (בסיסיים). ואז והם משתנים לא בסיסיים (חופשיים).

מבטאים את המשתנים העיקריים (הבסיסיים) במונחים של לא בסיסיים (חינם), אנו מקבלים

אנו מבטאים גם את פונקציית המטרה במונחים של משתנים לא בסיסיים (חופשיים):

ממקדמי המשתנים (לא ידועים) אנו בונים את טבלת הסימפלקס הראשונה.

שולחן 1
אלמונים בסיסיים	חברים חינם	אלמונים רופפים		מקדמי עזר
		X1	X2
X3	-2	1	-2
X4	-4	-1	-1
X5	2	1	-1
X6	6	0	1
ו	0	-1	-2

השורה האחרונה של הטבלה, המכילה את פונקציית המטרה ואת מקדמי המשתנים החופשיים בה, תיקרא שורת האינדקס.

הפתרון המתקבל אינו אופטימלי, שכן המקדמים של המשתנים החופשיים בשורת המדד הם שליליים. כלומר, הפתרון האופטימלי יהיה זה שבו המקדמים של המשתנים החופשיים בשורת המדד יהיו גדולים או שווים לאפס.

כדי לעבור לטבלה הבאה, מצא את הגדול ביותר (מודולו) של המספרים ו-. מספר זה הוא 2. לכן, העמודה המובילה היא העמודה שבה הוא כתוב

כדי לקבוע את השורה המובילה, נמצא את המינימום של היחסים של האיברים החופשיים למרכיבי העמודה המובילה, ואם למונה יש מספר חיובי והמכנה שלילי, היחס נחשב שווה לאינסוף.

.

לכן, הקו המוביל הוא זה שבו הוא כתוב

האלמנט המוביל הוא אפוא -2.

אנו מרכיבים את טבלת הסימפלקס השנייה.

נכניס את האלמנט הבסיסי החדש בשורה הראשונה, ונכנס לעמודה שבה הוא עמד, נכניס משתנה חופשי חדש

מלא את השורה הראשונה. לשם כך, נחלק את כל המספרים בשורה המובילה של טבלה 1 באלמנט המוביל ונכתוב אותו בעמודה המתאימה של השורה הראשונה של טבלה 2, למעט המספר בעמודה המובילה, שם ההדדיות של הקודמת נכתב אלמנט (כלומר אחד מחולק באלמנט המוביל).

מלא את עמודת מקדמי העזר. עבור מספר זה של העמודה המובילה של טבלה 1, בנוסף לאלמנט המוביל, אנו כותבים עם סימנים מנוגדים בעמודת מקדמי העזר של טבלה 2.

שולחן 2
אלמונים בסיסיים	חברים חינם	אלמונים רופפים		מקדמי עזר
		X1	X3
X2	1	-1/2	-1/2
X4	-3	-3/2	-1/2	1
X5	3	1/2	-1/2	1
X6	5	1/2	1/2	-1
ו	2	-2	-1	2

מי שעדיין לא פתח בחלון חדש את הפעולות הידניות עם שברים, יכול לעשות זאת עכשיו, כי הגיע הזמן.

כדי לקבל את השורות הנותרות בטבלה 2, את המספרים שכבר בשורה הראשונה של טבלה זו מכפילים במקדם העזר בשורה המילוי, ולתוצאה נוסיף את המספר מטבלה 1, שנמצאת באותה שורה עם המשתנה המקביל.

לדוגמה, כדי לקבל את האיבר החופשי בשורה השנייה, נכפיל את המספר 1 ב-1 ונוסיף את המספר -4 מטבלה 1. אנחנו מקבלים -3. אנו מוצאים את המקדם עבור בשורה השנייה באותו אופן: . מכיוון שאין עמודה עם משתנה חופשי חדש בטבלה הקודמת, מקדם השורה השנייה בעמודה של המשתנה החופשי החדש יהיה (כלומר, מטבלה 1 נוסיף 0, מכיוון שאין עמודה c בטבלה 1).

שורת האינדקס ממולאת באותו אופן:

הפתרון המתקבל כך שוב אינו אופטימלי, שכן המקדמים של המשתנים החופשיים בשורת המדד הם שוב שליליים.

כדי לעבור לטבלת הסימפלקס הבאה, נמצא את הגדול (מודולו) של המספרים, כלומר את המודולים של המקדמים בקו האינדקס. מספר זה הוא 2. לכן, העמודה המובילה היא העמודה המכילה .

כדי לחפש את השורה המובילה, בואו נמצא את היחס המינימלי של חברים חופשיים לרכיבי השורה המובילה. אנחנו מקבלים:

.

לכן, הקו המוביל הוא זה שבו כתוב, והאלמנט המוביל הוא -3/2.

הידור של טבלת הסימפלקס השלישית

נכתוב את המשתנה הבסיסי החדש בשורה הראשונה. בעמודה שבה זה היה, נזין משתנה חופשי חדש .

שורה ראשונה:

מקדמי עזר:

שולחן 3
אלמונים בסיסיים	חברים חינם	אלמונים רופפים		מקדמי עזר
		X4	X3
X1	2	-2/3	1/3
X2	2	-1/3	-1/3	1/2
X5	2	1/3	-2/3	-1/2
X6	4	1/3	1/3	-1/2
ו	6	-4/3	-1/3	2

הפתרון המתקבל שוב אינו אופטימלי, שכן המקדמים של הלא ידועים החופשיים בשורת המדד הם שוב שליליים.

כדי לעבור לטבלת הסימפלקס הרביעית, הבה נמצא את הגדול מבין המספרים ו-. זהו מספר.

לכן, העמודה המובילה היא זו עם .

מודול היחסים המינימלי של חברים חופשיים לאלמנטים של העמודה המובילה:

.

לכן, הקו המוביל הוא זה שבו כתוב, והאלמנט המוביל הוא 1/3.

בטבלת הסימפלקס הרביעית נכתוב את המשתנה הבסיסי החדש בשורה הראשונה. בעמודה שבה הוא היה, אנו כותבים משתנה חופשי חדש .

שורה ראשונה:

מקדמי עזר:

טבלה 4
אלמונים בסיסיים	חברים חינם	אלמונים רופפים		מקדמי עזר
		X5	X3
X4	6	3	-2
X1	6	2	-1	2/3
X2	4	1	-1	1/3
X6	2	-1	1	-1/3
ו	14	4	-3	4/3

חישוב השורות הנותרות באמצעות הדוגמה של השורה השנייה:

גם הפתרון המתקבל אינו אופטימלי, אך הוא כבר טוב יותר מהקודמים, שכן אחד המקדמים למשתנים חופשיים בשורת המדד אינו שלילי.

כדי לשפר את התוכנית, הבה נעבור לטבלת הסימפלקס הבאה.

מצא את הגדול מבין המספרים 4 ו. מספר זה הוא 4. לכן, העמודה המובילה היא .

כדי למצוא את השורה המובילה, מצא

.

לכן, הקו המוביל הוא זה שמכיל . אבל הם כבר היו ביחד בין המשתנים החופשיים. לכן, כדי להעביר את המשתנה הבא מחופשי לבסיסי, נבחר עמודה מובילה נוספת - זו שבה כתוב.

כדי למצוא את השורה המובילה, מצא

.

לכן, שורת המפתח היא זו שבה כתוב, והאלמנט המוביל הוא 1.

בטבלת הסימפלקס החמישית, המשתנה הבסיסי החדש נכתב בשורה הראשונה. בעמודה שבה הוא היה, אנו כותבים משתנה חופשי חדש .

שורה ראשונה:

מקדמי עזר:

טבלה 5
אלמונים בסיסיים	חברים חינם	אלמונים רופפים		מקדמי עזר
		X5	X6
X3	2	-1	1
X4	10			2
X1	8			1
X2	6			1
ו	20	1	3	3

בואו ננסה לברר מיד האם הפתרון אינו מיטבי. לכן, עבור השורות הנותרות, אנו מחשבים רק את המונחים החופשיים (כדי לברר את ערכי המשתנים הבסיסיים כאשר המשתנים החופשיים שווים לאפס) ואת המקדמים עבור המשתנים החופשיים בשורת המדד.

חברים בחינם:

בשורה השנייה;

בשורה השלישית;

בקו הרביעי.

שורת אינדקס:

אנו מסתכלים על טבלת הסימפלקס 5. אנו רואים שהפתרון האופטימלי התקבל, שכן המקדמים לא ידועים חופשיים בשורת האינדקס אינם שליליים.

שיטה פשוטה עם טרנספורמציות אלגבריות

בואו נפתור על ידי טרנספורמציות אלגבריות את אותה דוגמה כמו בפסקה הקודמת. יש לציין שכאשר פותרים שיטת סימפלקס מסוג זה, עדיף לא לכתוב את פונקציית המטרה בטופס , שכן קל להתבלבל בשלטים. אבל במקרה זה, נקודת האלגוריתם הקובעת את קריטריון האופטימליות תשתנה באופן הבא.

אם נמצא המקסימום (המינימום) של הצורה הליניארית ואין משתנים לא-בסיסיים עם מקדמים חיוביים (שליליים) בביטוי שלו, אזי קריטריון האופטימליות מתקיים והפתרון הבסיסי המתקבל הוא אופטימלי - הפתרון נגמר. אם, בעת מציאת המקסימום (המינימום) של צורה לינארית, הביטוי שלה מכיל משתנה אחד או יותר לא-בסיסי עם מקדמים חיוביים (שליליים), עבור לפתרון בסיסי חדש.

דוגמא.מצא את המקסימום של פונקציה תחת אילוצים

שלב I. אנו מציגים משתנים נוספים שאינם שליליים ומצמצמים את מערכת אי השוויון הזו למערכת מקבילה של משוואות

.

המשתנים הנוספים שהוצגו נלקחים כעיקריים, שכן במקרה זה ניתן למצוא בקלות את הפתרון הבסיסי של המערכת. ואז והם משתנים מינוריים.

ביטוי המשתנים העיקריים במונחים של המשתנים הלא בסיסיים, אנו מקבלים

כתוצאה מכך, חלוקה זו של משתנים לבסיס ולא בסיסי תואמת את הפתרון הבסיסי , שאינו חוקי (שני משתנים שליליים), ולכן אינו אופטימלי. בואו נעבור מהפתרון הבסיסי הזה לפתרון משופר.

כדי להחליט איזה משתנה יש להעביר מהלא-עיקרי לעיקרי, שקול אחת משתי המשוואות הזמינות של המערכת האחרונה עם איברים חופשיים שליליים, למשל, השנייה. הוא מראה כי וניתן לתרגם למשתנים העיקריים, שכן במשוואה זו יש להם מקדמים חיוביים (לכן, כאשר הם גדלים, וזה יקרה אם נתרגם אחד מהם למשתנים העיקריים, המשתנה יגדל).

בואו ננסה לתרגם למשתנה הראשי . כדי לקבוע איזה משתנה יש להעביר מהראשי אל הלא-בסיסי, נמצא את הערך המוחלט של היחס הקטן ביותר בין האיברים החופשיים של המערכת למקדמים ב. יש לנו . הוא מתקבל מהמשוואה השלישית, שמראה שיש להמיר את המשתנה לא-בסיסי, שהוא חיובי בפתרון הבסיסי המקורי. כתוצאה מכך, הפתרון הבסיסי המתקבל, כמו הפתרון המקורי, מכיל שני מרכיבים שליליים, כלומר, לא יהיה שיפור במעבר לפתרון בסיסי שכזה.

שיטה פשוטה- זוהי שיטה לספירה מסודרת של תוכניות ייחוס (הסדר מובטח על ידי שינוי מונוטוני בערך הפונקציה האובייקטיבית במהלך המעבר לתכנית הבאה). במקרה זה, יש צורך לשמור על העיקרון: כל שלב הבא צריך לשפר או, במקרים קיצוניים, לא להחמיר את הערך של הפונקציה האובייקטיבית.

כדי לפתור את ה-LLP שיטת סימפלקסהוא מצטמצם לצורה קנונית, כלומר. מהגבלות - אי שוויון יש צורך לעשות הגבלות - שוויון. לשם כך, כל אילוץ מתווסף עם אי-שלילי נוסף משתנה מאזניעם הסימן "+" אם סימן אי השוויון הוא "£", ועם הסימן "-" אם סימן אי השוויון הוא "³".

בפונקציית המטרה, משתנים נוספים אלו נכנסים עם אפס מקדמים, כלומר. ערך פונקציית היעד לא ישתנה. כל משתנה שאינו כפוף לתנאי אי-שליליות יכול להיות מיוצג כהבדל של שני משתנים לא-שליליים: .

אם אילוצי המשימה משקפים את הנוכחות והצריכה של משאבים, אזי הערך המספרי של המשתנה הנוסף בתוכנית המשימה, הכתוב בצורה קנונית, שווה לכמות המשאב שלא נעשה בו שימוש.

כדי לפתור את הבעיה בשיטת הסימפלקס, נשתמש טבלאות סימפלקס מקוצרות של מערכת משוואות ליניאריות ושיטת חיסול ג'ורדן שונה.

1. אנחנו מכינים את התוכנית הבסיסית הראשונה

המשימה נשארת זהה. הבה נביא את הצורה הסטנדרטית של מערכת אי השוויון (1) לצורה הקנונית של מערכת המשוואות על ידי הכנסת משתני איזון נוספים איקס 3 , איקס 4 , איקס 5 ,איקס 6 .

במובן הכלכלי, ערכי משתנים נוספים איקס 3 , איקס 4 , איקס 5 לקבוע את יתרת חומרי הגלם לאחר מכירת מוצרים.

למטריצה ​​של מערכת המשוואות המתקבלת יש את הצורה:

אפשר לראות את זה במטריצה אהמינור הבסיסי של הסדר הרביעי הוא הקובע, המורכב ממקדמי יחידות למשתנים נוספים איקס 3 , איקס 4 , איקס 5 ,איקס 6, מכיוון שהוא אינו אפס ושווה ל- 1. פירוש הדבר שוקטורי העמודות עבור משתנים אלו הם בלתי תלויים ליניארית, כלומר. טופס בָּסִיס, והמשתנים המתאימים איקס 3 , איקס 4 , איקס 5 ,איקס 6 הם בסיסי(בסיסי). משתנים איקס 1 , איקס 2 ייקרא חינם(קַטִין).

אם משתנים חופשיים איקס 1 ו איקס 2 כדי להגדיר ערכים שונים, ואז, בפתרון המערכת ביחס למשתנים הבסיסיים, נקבל קבוצה אינסופית של פתרונות מסוימים. אם רק ערכים אפס מוגדרים למשתנים חופשיים, אז מתוך קבוצה אינסופית של פתרונות מסוימים, פתרונות בסיסיים- תוכניות בסיסיות.

כדי לברר האם המשתנים יכולים להיות בסיסיים, יש צורך לחשב את הקובע המורכב מהמקדמים של משתנים אלו. אם הקובע הזה אינו שווה לאפס, משתנים אלה יכולים להיות בסיסיים.

מספר הפתרונות הבסיסיים והמספר המקביל של קבוצות של משתנים בסיסיים יכולים להיות לא יותר מ , שבו נהוא המספר הכולל של המשתנים, רהוא מספר המשתנים הבסיסיים, ר≤ M≤ נ.

למשימה שלנו ר = 4; נ= 6. לאחר מכן , כלומר. אפשריות 15 קבוצות של 4 משתנים בסיסיים (או 15 פתרונות בסיסיים).

הבה נפתור את מערכת המשוואות ביחס למשתנים הבסיסיים איקס 3 , איקס 4 , איקס 5 ,איקס 6:

בהנחה שהמשתנים החופשיים איקס 1 = 0, איקס 2 = 0, נקבל את הערכים של המשתנים הבסיסיים: איקס 3 = 312; איקס 4 = 15; איקס 5 = 24;איקס 6 = -10, כלומר. הפתרון הבסיסי יהיה = (0; 0; 312; 15; 24; -10).

הפתרון הבסיסי הזה הוא לא מקובל, כי איקס 6 = –10 ≤ 0, ולפי תנאי האילוץ איקס 6 ≥ 0. לכן, במקום המשתנה איקס 6 כבסיס, אתה צריך לקחת משתנה נוסף מבין החופשיים איקס 1 או איקס 2 .

נבצע את הפתרון הנוסף באמצעות טבלאות סימפלקס מקוצרות, ונמלא את שורות הטבלה הראשונה במקדמי המערכת באופן הבא (טבלה 1):

שולחן 1

ו- קוראים למחרוזת אינדקס. הוא מלא במקדמי פונקציה אובייקטיבית שנלקחו עם סימנים מנוגדים, שכן ניתן לייצג את משוואת הפונקציה כ ו = 0 – (– 4איקס 1 – 3איקס 2).

בטור החברים החופשיים ב אנייש אלמנט שלילי ב 4 = -10, כלומר. הפתרון של המערכת אינו חוקי. כדי לקבל פתרון תקף (תוכנית בסיס), האלמנט ב 4 חייב להיות לא שלילי.

בחר איקס 6 - שורה עם חבר חופשי שלילי. שורה זו מכילה אלמנטים שליליים. בחר כל אחד מהם, למשל, "-1" ב איקסעמודה 1, ו איקס 1 - עמודה קבל כ עמודת ההרשאה(זה יקבע שהמשתנה איקס 1 יעבור מחינמי לבסיסי).

אנו חולקים חברים בחינם ב אניעל המרכיבים הרלוונטיים א הואפתרון עמודה, אנחנו מקבלים יחסים מעריכיםΘ אני==(24, 15, 12, 10). מבין אלה, אנו בוחרים את החיוב הקטן ביותר (minΘ אני=10), שיתאים ל שורת ההרשאה. מחרוזת הרשאה מגדירה משתנה x j, שבשלב הבא בולט מהבסיס והופך לחופשי. בגלל זה איקס 6 -קו הוא קו מתירני, והאלמנט "-1" הוא אלמנט מאפשר. אנחנו מקיפים אותו. משתנים איקס 1 ו איקס 6 מוחלפים.

יחסים משוערים Θ אניבכל שורה נקבעים לפי הכללים:

1) Θ אני= אם ב אניו א הואיש סימנים שונים;

2) Θ אני= ∞ אם ב אני= 0 ו א הוא < 0;

3) Θ אני= ∞ אם א הוא = 0;

4) Θ אני= 0 אם ב אני= 0 ו א הוא > 0;

5) Θ אני= אם ב אניו א הואיש את אותם סימנים.

אנו עושים את הצעד של חיסול ירדני שונה (MJJI) עם אלמנט מתירני ומרכיבים טבלה חדשה (טבלה 2) לפי הכלל הבא:

1) במקום האלמנט הפותר (RE), נקבע ערך, הפוך שלו, כלומר. ;

2) מרכיבי הקו המתיר מחולקים ל-RE;

3) האלמנטים של העמודה הפותרת מחולקים ל-RE והסימן משתנה;

4) האלמנטים הנותרים נמצאים על פי כלל המלבן:

מתוך טבלה. 2 מראה שהחברים החופשיים ב ב אני-העמודות אינן שליליות, לכן, הפתרון הקביל הראשוני מתקבל - תוכנית בסיס ראשונה= (10; 0; 182; 5; 4; 0). במקרה זה, הערך של הפונקציה ו() = 40. מבחינה גיאומטרית, זה מתאים לחלק העליון ו(10; 0) מצולע פתרון (איור 1).

שולחן 2

2. אנו בודקים את התוכנית לאופטימיות.תוכנית הבסיס אינה אופטימלית, כי ב ו-קו יש מקדם שלילי "-4". אנחנו משפרים את התוכנית.

3. מציאת קו בסיס חדש

אנו בוחרים את האלמנט המאפשר לפי הכלל:

אנו בוחרים את המקדם השלילי הקטן ביותר ב ו-שורה "-4", הקובעת את העמודה המאפשרת - איקס 6; מִשְׁתַנֶה איקס 6 לתרגם לבסיסי;

נמצא את היחסים Θ אני, ביניהם אנו בוחרים את החיובי הקטן ביותר, המתאים למחרוזת המתירנית:

דקה Θ אני = דקה(14, 5, 2, ∞) = 2, ומכאן איקס 5 - קו - מתירני, משתנה איקס 5 אנו מתרגמים לחופשי (משתנים איקס 5 ו איקס 6 מוחלפים).

בצומת השורה והעמודה המתירנית נמצא האלמנט המתירני "2";

אנו מבצעים את השלב SHMZhI, אנו בונים את הטבלה. 3 לפי הכלל לעיל וקבל תוכנית ייחוס חדשה = (12; 0; 156; 3; 0; 2).

שולחן 3

4. בדיקת התכנית הבסיסית החדשה לאופטימיות

גם תוכנית הבסיס אינה אופטימלית, שכן ב ו-קו יש מקדם שלילי "-1". ערך פונקציה ו() = 48, המתאים מבחינה גיאומטרית לחלק העליון ה(12; 0) מצולע פתרון (איור 1). אנחנו משפרים את התוכנית.

5. מציאת קו בסיס חדש

איקס 2 עמודות הוא מתירני, שכן ב ו-קו המקדם השלילי הקטן ביותר "-1" נמצא בתוכו איקס 2 עמודות (Δ 2 = -1). מציאת ה-Θ הקטן ביותר אני: דקה Θ אני = דקה(≈ 9, 6, ∞, 24) = 6, ומכאן איקסקו 4 - מתירני. אלמנט מתירני "1/2". החלפת משתנים איקס 2 ו איקסארבע . אנו מבצעים את השלב SHMZhI, אנו בונים את הטבלה. 4, אנו מקבלים תוכנית ייחוס חדשה = (9; 6; 51; 0; 0; 5).

6. בדיקת התוכנית הבסיסית לאופטימיות

בְּ ו-שורה, כל המקדמים אינם שליליים, לכן, תוכנית הייחוס היא אופטימלית. מתאים מבחינה גיאומטרית לנקודה ד(9;6) (ראה איור 1). התוכנית האופטימלית נותנת את הערך המקסימלי של פונקציית המטרה c.u.

רָאשִׁי הרעיון של שיטת סימפלקס לפתרון ה-LLPמורכב משיפור עקבי של פתרונות התמיכה ב-LLP.

ישנן מספר דרכים לכתוב את שיטת הסימפלקס.

1. הצורה הבסיסית של שיטת הסימפלקס;
2. שיטת סימפלקס בצורה של טבלת סימפלקס;
3. שיטת סימפלקס שונה;
4. שיטת סימפלקס בצורת עמודים;
5. שיטה פשוטה בצורת שורה.

הבה נגדיר את הערך המקסימלי של פונקציית המטרה F(X) = 3x 1 +5x 2 +4x 3 בתנאי האילוץ הבאים.
0.1x 1 +0.2x 2 +0.4x 3 ≤1100
0.05x 1 +0.02x 2 +0.02x 3 ≤120
3x1 +x2 +2x3 ≤8000

כדי לבנות את תוכנית ההתייחסות הראשונה, אנו מצמצמים את מערכת אי השוויון למערכת של משוואות על ידי הכנסת משתנים נוספים (מעבר לצורה הקנונית).
0.1x1 + 0.2x2 + 0.4x3 + 1x4 + 0x5 + 0x6 = 1100
0.05x1 + 0.02x2 + 0.02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000

סימון בסיסי של שיטת הסימפלקס

הפתרון מתבצע על ידי ביטוי המשתנים הבסיסיים באמצעות משתנים לא בסיסיים: x0 = 3x1 +5x2 +4x3 x 4 = 1100-0.1x 1 -0.2x 2 -0.4x 3 x 5 = 120-0.05x 1 -0.02x 2 -0.02x 3 x 6 = 8000-3x 1 -x 2 -2x 3

שיטת סימפלקס בצורה של טבלת סימפלקס

הפתרון מתבצע בצורה של טבלת סימפלקס. הטופס מיועד למחשוב במחשב. כאשר משתמשים בבסיס מלאכותי, משתמשים במספר מיוחד M (בדרך כלל 10000).

לְתַכְנֵן	בָּסִיס	בְּ	x 1	x2	x 3	x4	x5	x6	דקה
1	x4	1100	0.1	0.2	0.4	1	0	0	5500
	x5	120	0.05	0.02	0.02	0	1	0	6000
	x6	8000	3	1	2	0	0	1	8000
שורת אינדקס	F(X1)	0	-3	-5	-4	0	0	0	0
2	x2	5500	0.5	1	2	5	0	0	11000
	x5	10	0.04	0	-0.02	-0.1	1	0	250
	x6	2500	2.5	0	0	-5	0	1	1000
שורת אינדקס	F(X2)	27500	-0.5	0	6	25	0	0	0
3	x2	5375	0	1	2.25	6.25	-12.5	0	11000
	x1	250	1	0	-0.5	-2.5	25	0	250
	x6	1875	0	0	1.25	1.25	-62.5	1	1000
שורת אינדקס	F(X3)	27625	0	0	5.75	23.75	12.5	0	0

שיטת סימפלקס שונה

מטריצת מקדם A = a ij מטריקס ב. איטרציה מס' 1. = (4, 5, 6) מטריקס ג. c = (-3, -5, -4, 0, 0, 0) c B = (0, 0, 0) c N = (-3, -5, -4) אנו מחשבים: המטריצה ​​B -1 מחושבת באמצעות תוספות אלגבריות. u = c B B -1 = (0, 0, 0)

שיטה פשוטה בצורת עמודים

אנו עוברים לצורת העמודים של שיטת הסימפלקס. אנו מבטאים כל משתנה במונחים לא בסיסיים. x 0 = 0-3(-x 1)-5(-x 2)-4(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 1 = 0-1(-x 1)+0(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 2 = 0+0(-x 1)-1(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 3 = 0+0(-x 1)+0(-x 2)-1(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 4 = 1100+0.1(-x 1)+0.2(-x 2)+0.4(-x 3)+1(-x 4)+0(-x 5)+0(-x 6) x 5 = 120+0.05(-x 1)+0.02(-x 2)+0.02(-x 3)+0(-x 4)+1(-x 5)+0(-x 6) x 6 = 8000+3(-x 1)+1(-x 2)+2(-x 3)+0(-x 4)+0(-x 5)+1(-x 6) מערכת זו מתאימה לטבלה T 0 . 0 -1 0 0 0 0 -1 0 0 0 0 -1 1100 0.1 0.2 0.4 120 0.05 0.02 0.02 8000 3 1 2 0 -3 -5 -4

שיטה פשוטה בצורת מחרוזת

כבסיס הקביל הראשוני, נוכל לקחת את B 0 =<4, 5, 6>. זה יתאים לטבלה הבאה. 1100 0.1 0.2 0.4 1 0 0 120 0.05 0.02 0.02 0 1 0 8000 3 1 2 0 0 1 0 -3 -5 -4 0 0 0

המטריצה ​​Q, המורכבת מהמקדמים של המערכת, נקראת שולחן סימפלקסהמקביל לבסיס B. טבלה סימפלקס נקראת קָבִיל, או קביל ישירות, אם q i0 ≥ 0. האלמנטים q i0 של השורה האחרונה של טבלת הסימפלקס Q נקראים הערכות יחסיות.

צורות פתרון בשיטת בסיס מלאכותי

על השימוש במשתנים מלאכותיים המוכנסים לפונקציה האובייקטיבית, מוטל מה שנקרא עונש של M, מספר חיובי גדול מאוד, שבדרך כלל לא מצוין.
הבסיס המתקבל נקרא מלאכותי, ושיטת הפתרון נקראת שיטת הבסיס המלאכותי.
יתרה מכך, משתנים מלאכותיים אינם קשורים לתוכן המשימה, אך הם מאפשרים לבנות נקודת התחלה, ותהליך האופטימיזציה מאלץ את המשתנים הללו לקחת אפס ערכים ולהבטיח את קבילות הפתרון האופטימלי.

צורות פתרון בשיטת הבסיס המלאכותי:

1. M-method (טבלה פשוטה);
2. שיטת סימפלקס דו-שלבית או דו-פאזית (סימון בסיסי, שיטת סימפלקס שונה, שיטת סימפלקס בצורת טור, שיטת סימפלקס בצורת שורה).

אם יש הגבלות עם הסימן ≥ במצב הבעיה, אז ניתן לצמצם אותן לצורה ∑a ji b j על ידי הכפלת שני חלקי אי השוויון ב-1. אנו מציגים m משתנים נוספים x n+j ≥0(j =1,m ) והופכים את האילוצים לצורת השוויון

(2)

הבה נניח שכל המשתנים הראשוניים של הבעיה x 1 , x 2 ,..., x n הם לא בסיסיים. אז המשתנים הנוספים יהיו בסיסיים, ולפתרון מסוים למערכת האילוצים יש את הצורה

x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m . (3)

מכיוון שבמקרה זה הערך של פונקציית המטרה F 0 = 0, נוכל לייצג את F(x) באופן הבא:

F(x)=∑c i x i + F 0 =0 (4)

טבלת הסימפלקס הראשונית (טבלה סימפלקס 1) מורכבת על סמך משוואות (2) ו-(4). אם לפני המשתנים הנוספים x n+j סימן "+", כמו ב-(2), אז כל המקדמים לפני המשתנים x i והאיבר החופשי b j מוזנים לטבלת הסימפלקס ללא שינוי. המקדמים של פונקציית המטרה במהלך המקסום שלה מוזנים בשורה התחתונה של טבלת הסימפלקס עם סימנים מנוגדים. חברים חופשיים בטבלת הסימפלקס קובעים את פתרון הבעיה.

האלגוריתם לפתרון הבעיה הוא כדלקמן:

שלב 1. הרכיבים של עמודת החברים החופשיים נבדקים למעלה. אם כולם חיוביים, אז נמצא פתרון בסיסי מקובל ויש להמשיך לשלב 5 של האלגוריתם, שמתאים למציאת הפתרון האופטימלי. אם יש מונחים חופשיים שליליים בטבלת הסימפלקס הראשונית, אז הפתרון אינו תקף ועליכם לעבור לשלב 2.

שלב 2. כדי למצוא פתרון בר ביצוע, מתבצע, תוך כדי שיש צורך להחליט איזה מהמשתנים הלא-בסיסיים לכלול בבסיס ואיזה משתנה לסגת מהבסיס.

שולחן 1.

x n

משתני בסיס	חברים חינם בהגבלות	משתנים לא בסיסיים
		x 1	x2	...	x l	...
xn+1	ב 1	א 11	א 12	...	a 1l	...	a 1n
xn+2	ב 2	א 21	א 22	...	a 2l	...	a 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+r	ב2	r1	r2	...	rl	...	rn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+m	ב מ	m1	m2	...	aml	...	amn
F(x)max	F0	-ג 1	-ג 2	...	-ג 1	...	-ג נ

כדי לעשות זאת, בחר כל אחד מהרכיבים השליליים של העמודה של איברים חופשיים (תנו לו להיות b 2 מוביל, או מאפשר. אם אין אלמנטים שליליים בשורה עם איבר חופשי שלילי, אז מערכת ההגבלות אינה עקבית ו לבעיה אין פתרון.

יחד עם זאת, המשתנה שהוא הראשון לשנות את הסימן עם עלייה ב-NP x l שנבחר אינו נכלל ב-BP. זה יהיה x n+r, שהאינדקס r שלו נקבע מהתנאי

הָהֵן. המשתנה המתאים ליחס הקטן ביותר של האיבר החופשי לאלמנט של העמודה המובילה שנבחרה. מערכת יחסים זו נקראת יחס סימפלקס. יש לקחת בחשבון רק יחסי סימפלקס חיוביים.

המחרוזת המתאימה למשתנה x n+r נקראת מוביל, או מאפשר. האלמנט של טבלת הסימפלקס a rl , שנמצא במפגש בין השורה המובילה והעמודה המובילה, נקרא אלמנט מוביל או פותר.מציאת האלמנט המוביל מסיימת את העבודה עם כל טבלת סימפלקס הבאה.

שלב 3. מחושב טבלת סימפלקס חדשה, שהרכיבים שלה מחושבים מחדש ממרכיבי טבלת הסימפלקס של השלב הקודם ומסומנים בראשית, כלומר. b" j , a" ji , c" i , F" 0 . האלמנטים מחושבים מחדש לפי הנוסחאות הבאות:

ראשית, השורה והעמודה שהיו מובילים בטבלת הסימפלקס הקודמת ימולאו בטבלת הסימפלקס החדשה. ביטוי (5) פירושו שהאלמנט a "rl במקום האלמנט המוביל שווה להדדיות של האלמנט של טבלת הסימפלקס הקודמת. האלמנטים של השורה a ri מחולקים באלמנט המוביל, והאלמנטים של ה- טור a jl מחולקים גם הם באלמנט המוביל, אך נלקחים עם הסימן ההפוך. היסודות b" r ו-c" l מחושבים לפי אותו עיקרון.

את שאר הנוסחאות ניתן לכתוב בקלות באמצעות .

המלבן בנוי לפי טבלת הסימפלקס הישנה באופן שאחד מאלכסוניו נוצר על ידי האלמנטים המחושבים מחדש (a ji) והאלמנטים המובילים (a rl) (איור 1). האלכסון השני נקבע באופן ייחודי. כדי למצוא אלמנט חדש a "ji, המכפלה של אלמנטים באלכסון הנגדי, חלקי היסוד המוביל, מופחת מיסוד a ji (זה מסומן על ידי הסימן" - "בתא). באופן דומה, אלמנטים b" j, (j≠r) ו-c" i מחושבים מחדש, (i≠l).

שלב 4. הניתוח של טבלת סימפלקס חדשה מתחיל מהשלב הראשון של האלגוריתם. הפעולה נמשכת עד שנמצא פתרון בסיסי אפשרי, כלומר. כל הרכיבים בעמודת החברים החופשיים חייבים להיות חיוביים.

שלב 5. אנו מאמינים כי נמצא פתרון בסיסי מקובל. אנו מסתכלים על המקדמים של הקו של פונקציית המטרה F(x) . סימן לאופטימליות של טבלת סימפלקס הוא אי השליליות של המקדמים עבור משתנים לא בסיסיים בשורת F.

אורז. 1. כלל מלבן

אם בין המקדמים של שורת F יש שליליים (למעט המונח החופשי), אז אתה צריך ללכת לפתרון בסיסי אחר. בעת מקסום פונקציית המטרה, הבסיס כולל את זה של המשתנים הלא-בסיסיים (לדוגמה, x l), שהעמודה שלהם מתאימה לערך המוחלט המרבי של המקדם השלילי c l בשורה התחתונה של טבלת הסימפלקס. זה מאפשר לבחור את המשתנה שהגידול שלו מוביל לשיפור בפונקציית המטרה. העמודה המקבילה למשתנה x l נקראת העמודה המובילה. יחד עם זאת, אותו משתנה x n+r אינו נכלל מהבסיס, שהמדד r שלו נקבע על ידי יחס הסימפלקס המינימלי:

השורה המקבילה ל-x n+r נקראת השורה המובילה, והאלמנט של טבלת הסימפלקס a rl , שנמצא במפגש בין השורה המובילה והעמודה המובילה, נקרא אלמנט מוביל.

שלב 6. לפי הכללים שנקבעו בשלב השלישי. ההליך נמשך עד שנמצא פתרון אופטימלי או שמגיעים למסקנה שהוא לא קיים.

אם בתהליך של אופטימיזציה של הפתרון בעמודה המובילה כל האלמנטים אינם חיוביים, אז לא ניתן לבחור את השורה המובילה. במקרה זה, הפונקציה בתחום הפתרונות הקבילים של הבעיה אינה מוגבלת מלמעלה ו- F max ->&∞.

אם בשלב הבא של החיפוש אחר קיצון אחד מהמשתנים הבסיסיים הופך להיות שווה לאפס, אז הפתרון הבסיסי המקביל נקרא מנוון. במקרה זה מתרחשת מה שנקרא לולאה, המתאפיינת בכך שאותו שילוב של BP מתחיל לחזור על עצמו בתדירות מסוימת (ערך הפונקציה F נשמר במקרה זה) ואי אפשר לעבור ל פתרון בסיסי מקובל חדש. לולאה היא אחד החסרונות העיקריים של שיטת הסימפלקס, אך היא נדירה יחסית. בפועל במקרים כאלה מסרבים בדרך כלל להכניס לבסיס את המשתנה שהעמודה שלו תואמת את הערך המוחלט המקסימלי של המקדם השלילי בפונקציית המטרה, ומתבצעת בחירה אקראית של פתרון בסיסי חדש.

דוגמה 1. פתרו בעיה

max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1.2 ≥0)

שיטה פשוטה ולתת פרשנות גיאומטרית לתהליך הפתרון.

פרשנות גרפית של פתרון הבעיה מוצגת באיור. 2. הערך המרבי של פונקציית המטרה מושג בחלק העליון של ה-ODZP עם קואורדינטות. בואו נפתור את הבעיה באמצעות טבלאות סימפלקס. נכפיל את האילוץ השני ב-(-1) ונכניס משתנים נוספים כדי להביא את אי השוויון לצורת השוויון, ואז

המשתנים ההתחלתיים x 1 ו- x 2 נלקחים כלא-בסיסיים, וה-x 3, x 4 ו-x 5 הנוספים נחשבים בסיסיים ואנו מרכיבים טבלה סימפלקסית (טבלה פשוטה 2). הפתרון המתאים לטבלת הסימפלקס. 2, אינו תקף; האלמנט המוביל מתואר ונבחר בהתאם לשלב 2 של האלגוריתם לעיל. לשונית הסימפלקס הבאה. 3 מגדיר פתרון בסיסי קביל; 2 האלמנט המוביל מתואר ונבחר בהתאם לשלב החמישי של האלגוריתם לפתרון הבעיה. כרטיסייה. 4 מתאים לפתרון האופטימלי של הבעיה, לכן: x 1 = x 5 = 0; x 2 \u003d 4; x 3 \u003d 3; x 4 = 8; F max = 20.

אורז. 2. פתרון גרפי של הבעיה